피보나치 수열 효율적으로 구현하기

컴퓨터공학부 학생들이라면 반드시 자료구조와 알고리즘 시간 때 작성해보는 코드가 있습니다. 그것은 바로 팩토리얼을 구하는 함수와 n번째 피보나치 수열을 구하는 함수입니다. 우리는 재귀함수의 원리를 배우기 위해 피보나치 수열을 사용하여 n번째 항을 구하게 됩니다. 그 소스는 전공자가 아니라 독학으로 프로그래밍을 배우던 분들도 익숙할 것입니다.

int fibonacci(int n)
{
    if (n < 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

이 소스는 n번째 피보나치에 대해 2보다 작을 경우, 즉 $F_0, F_1$ 항에 대해서는 1을 리턴하고, 이외의 수에 대해서는 $F_{n-1} + F_{n-2}$ 항을 더하는 형식으로 호출됩니다. 그래서 프로그래밍을 공부하시던 분들에게 피보나치 수를 구하는 함수를 만들라고 하면 이렇게 작성하시는 분들도 많은 것이 사실입니다.

하지만 어느 기업 코딩 면접에서 다음과 같은 문제가 나왔습니다.

n번째 피보나치 수를 구하는 함수를 작성하세요. n은 1,000 보다 작거나 같은 자연수이며, 숫자가 매우 커질 수 있으므로 답을 10,007로 나눈 나머지를 출력하세요.

우리는 이 문제를 위의 함수를 이용해서 풀 수 있을까요? 답은 풀 수 없다 입니다.

우리는 왜 이 문제를 위의 함수로 풀 수 없을까요? 그것은 위의 함수는 불필요한 중복 호출이 굉장히 많다는 것입니다.

만약 $F_4$ 항을 위의 함수로 이용하여 구하면 어떻게 될까요?

이와 같은 과정을 거치게 됩니다. 사진을 보면, 피보나치 0항과 1항, 2항에 대해 여러 번 계산을 하는 것을 볼 수 있습니다.

어떠한 문제를 풀 때, 작성한 소스가 입력된 값에 대해 문제를 해결하는 데 필요한 시간을 시간복잡도라고 하며, 위의 문제와 같이 풀 경우 이 시간복잡도가 $O(2^n)$ 입니다. 하지만 우리는 n번째 피보나치 항을 여러 번 계산한다고 해서 그 값이 달라지지 않는다는 것을 알고 있습니다. 즉, 한번 구한 항을 기록(memoization) 해 둔 다음, 그 값이 필요할 때 꺼내쓸 수 있다면 굉장히 효율적일 것입니다.

이와 같이, 어떠한 문제에 대해 먼저 더 작은 범위의 부분 정답을 구하고, 그 부분 정답을 이용하여더 큰 정답을 구할 수 있으며, 부분 정답 역시 그 범위에서는 최선의 정답임이 보장되는 풀이 방식을 Dynamic programming 이라고 합니다.

일반적으로 memoization은 배열을 이용해서 합니다. 위의 소스를 다음과 같이 바꾸었습니다.

int fn[1000], MOD = 10007;
int fibonacci(int n)
{
    if (n < 2) return 1;

    if (fn[n] != 0) return fn[n];
    fn[n] = (fibonacci(n - 1) % MOD + fibonacci(n - 2) % MOD) % MOD;
    return fn[n];
}

위의 소스는 한 번 구한 값에 대해서는 다시 구하지 않고 재활용 하므로, n번째 피보나치 항에 대해 시간복잡도가 $O(n)$ 이 됩니다. 시간이 굉장히 단축되었으며, 이렇게 풂으로써 결국 면접문제를 통과할 수 있게 된 것입니다.