Fibonacci Numbers

상위 문서: Dynamic Programming

개요

피보나치 수열(Fibonacci Numbers)은 동적 프로그래밍(Dynamic Programming)의 대표적인 구현 예시 중 하나이다. 해당 문서에서는 피보나치 수열을 통한 동적 프로그래밍의 구현에 대해 설명한다.

Intuitive Version

피보나치 수열의 점화식 정의는 아래와 같다:

$F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1$

이를 구현하기 위한 기본적인 방법은 아래와 같다:

long fib_r(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_r(n-1) + fib_r(n-2);
}

이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비($\varphi$)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 $n^{1.6}$번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.

Memoization(Top-Down)

Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:

#define MAXN 92
#define UNKNOWN -1
long f[MAXN+1];

long fib_c(int n) {
    if (f[n] == UNKNOWN) {
        f[n] = fib_c(n-1) + fib_c(n-2);
    }
    return f[n];
}

위 코드에서 f[n] 배열은 캐시 기능을 하며, UNKNOWN 값(-1)은 아직 계산되지 않은 상태를 의미한다. 이를 통해서 한 번 계산한 피보나치 수는 저장하여 중복 계산을 방지한다. 재귀 구조에 저장소를 추가한 형태를 top-down 방식의 동적 프로그래밍이라고 한다. 아래는 위의 코드를 실행하기 위해서 f 배열을 초기화한 뒤 fib_c()를 호출하는 드라이버 함수이다:

long fib_c_driver(int n) {
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++) {
        f[i] = UNKNOWN;
    }
    return fib_c(n);
}

이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.

Down-Top Dynamic Programming

Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:

long fib_dp(int n) {
    int i;
    long f[MAXN+1];
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

이는 시간 복잡도와 공간 복잡도가 모두 O(n)으로, 매우 효율적으로 구현되었다.