[프로그래머스/JAVA] 피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

 

입출력 예

n	return
3	2
5	5

 

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

---

 

아래 코드로 코드 실행하면 통과는 되지만, 채점하면 시간초과로 실패가 뜬다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        answer = fiboNum(n);
        return answer%1234567;
    }
    
    public int fiboNum(int n) {
        
        if(n == 0) return 0; // F(0) = 0
        else if(n == 1) return 1; // F(1) = 1
        else return fiboNum(n-1) + fiboNum(n-2); // F(n) = F(n-1) + F(n-2)
    }
}

 

실행 결과

채점 결과

 

fiboNum 함수를 재귀 호출하여 시간복잡도가 O(2^n) 으로, 입력값이 커질수록 시간 비용이 많이 든다고 한다.

 

문제점 : 기존 코드의 시간 초과
기존 코드는 재귀 함수(fiboNum)를 사용해서 피보나치 수를 구하고 있습니다. 예를 들어, fiboNum(5)를 계산에서, 이 함수는 다음과 같은 방식으로 작동합니다:

1. fiboNum(5)는 fiboNum(4)와 fiboNum(3)을 계산.
2. fiboNum(4)는 fiboNum(3)과 fiboNum(2)를 계산.
3. fiboNum(3)는 fiboNum(2)와 fiboNum(1)을 계산.

이렇게 계속해서 작은 숫자들로 나눠서 계산을 하는데, 여기서 문제가 생긴다. 이미 계산한 값을 계속 반복해서 계산한다는는 점이다. 예를 들어, fiboNum(3)을 여러 번 계산하게 된다는 말이다. 이로 인해 시간이 오래 걸리게 되어 큰 숫자를 입력하면 시간 초과가 발생한다.

---

해결 방법: 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍은 한 번 계산한 값을 저장해서 나중에 또 사용할 때 다시 계산하지 않고 저장된 값을 바로 가져오는 방법이다. 이를 메모이제이션 (Memoization)이라고 부른다.

 

예를 들어, fiboNum(5)를 계산할 때:

fiboNum(4)와 fiboNum(3)을 계산한 뒤 결과를 저장한다.
다음에 fiboNum(4)나 fiboNum(3)이 필요하면, 이미 계산한 값을 재사용한다.

public class Solution {
    public static int solution(int n) {
        // 피보나치 수를 저장할 배열 생성
        int[] fibo = new int[n + 1];
        
        // 초기값 설정: F(0) = 0, F(1) = 1
        fibo[0] = 0;
        fibo[1] = 1;
        
        // 2부터 n까지의 피보나치 수를 계산하고 배열에 저장
        for (int i = 2; i <= n; i++) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
        }
        
        // F(n)을 반환
        return fibo[n];
    }
}

 

1. 배열 준비 (int[] fibo = new int[n + 1];):

fibo라는 배열을 만들어서, 각 자리마다 피보나치 수를 저장한다.
예를 들어, fibo[5]에는 F(5)의 값이 들어가게 된다.

 

2. 초기값 설정 (fibo[0] = 0;, fibo[1] = 1;):
피보나치 수열의 시작값인 0번째와 1번째 값을 설정한다.
피보나치 수열은 F(0) = 0, F(1) = 1로 시작.

 

3. 반복문 사용:
for문을 사용해서 2부터 n까지 순차적으로 계산한다.
예를 들어, F(2)는 F(1) + F(0)이고, F(3)는 F(2) + F(1)이다.
이렇게 계산한 값을 fibo 배열에 저장해 두면, 다음 계산에 바로 사용할 수 있다.

 

4. 모듈러 연산 (% 1234567):
피보나치 수가 커질 수 있기 때문에, 매번 계산할 때마다 1234567로 나눈 나머지를 구해서 저장한다. 이렇게 하면 계산 결과가 너무 커지는 것을 방지할 수 있다.

 

예시로 살펴보기

만약 n = 5라면:
1. 초기 상태: fibo = [0, 1, 0, 0, 0, 0]
2. i = 2일 때: fibo[2] = (fibo[1] + fibo[0]) % 1234567 = 1
결과: fibo = [0, 1, 1, 0, 0, 0]
3. i = 3일 때: fibo[3] = (fibo[2] + fibo[1]) % 1234567 = 2
결과: fibo = [0, 1, 1, 2, 0, 0]
4. i = 4일 때: fibo[4] = (fibo[3] + fibo[2]) % 1234567 = 3
결과: fibo = [0, 1, 1, 2, 3, 0]
5. i = 5일 때: fibo[5] = (fibo[4] + fibo[3]) % 1234567 = 5
결과: fibo = [0, 1, 1, 2, 3, 5]

마지막으로 fibo[5]의 값 5를 반환한다.

 

채점결과