[실전 문제] fibonacci

1. 문제

피보나치 수열은 수학에서 아주 유명한 수열이다. 피보나치 수열을 이루는 수들을 피보나치 수라고 한다.

 

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

이를 식으로 써보면 F(n)= F(n-1) + F(n-2), (n>=2)가 된다.

 

n이 0 ~ 15일때 까지 피보나치 수를 써보면 다음과 같다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 n이 주어진다. (0 ≤ n ≤ 45)

출력

첫째 줄에 n번째 피보나치 수를 출력한다. 

예제 입력

10

예제 출력

55

 

 

 

2. 풀이

이 문제는 재귀로 접근하면 시간 초과 문제가 발생한다. 시간복잡도를 생각하면 큰 차이를 확인할 수 있다.

 

우선, 재귀(Top-Down)의 점화식은 다음과 같이 정의할 수 있다.

T(n)은 n을 계산하기 위해 피보나치 함수가 호출되는 횟수
n	fb(n)	T(n)
0	fb(0)	1
1	fb(1)	1
2	fb(2) / fb(1), fb(0)	3
3	fb(3) / fb(2), fb(1) / fb(1), fb(0)	5
4	fb(4) / fb(3), fb(2) / fb(2), fb(1) / fb(1), fb(0) / fb(1), fb(0)	9
5	fb(5) / fb(4), fb(3) / fb(3), fb(2) / fb(2), fb(1) / fb(2), fb(1) / fb(1), fb(0) / fb(1), fb(0) / fb(1), fb(0)	15
T(n) = T(n-1) + T(n-2) + 1

 

T(n) = T(n-1) + T(n-2) + 1 점화식을 귀납적으로 계산하면 다음과 같다.

• T(n-1) + T(n-2)
• T(n-2) + T(n-2) (T(n-1)이 T(n-2)보다 크기 때문, T(n-1) + T(n-2) > T(n-2) + T(n-2))
• 2 x T(n-2)
• 2 x T(n-2)
• 2 x 2 x T(n-4)
• 2 x 2 x 2 x T(n-6)
• 2^(n/2) x T(0)
• 2^(n/2)
• 즉, O(2^n/2)의 시간이 소요되는 것을 알 수 있다.

 

반대로 재귀가 아닌 단순 반복문으로 계산한다면, O(n)의 시간복잡도가 걸린다. 따라서 재귀적 접근이 아닌, 단순 반복문을 이용하여 이 문제를 풀 수 있다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        bw.write(fibonacci(n) + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static int fibonacci(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else {
            int result = 0;
            int prev1 = 1;
            int prev2 = 0;
            for(int i = 2; i <= n; i++) {
                result = prev1 + prev2;
                prev2 = prev1;
                prev1 = result;
            }
            return result;
        }
//        return fibonacci(n-1) + fibonacci(n-2);
    }
}