동적 프로그래밍으로 피보나치 수열 생성하기

피보나치 수열(Fibonacci Sequence)은 다음과 같은 형태를 가지는 수열입니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……

이 수열에서 n번째 항은 바로 앞의 두 항, 즉 (n-1)번째 항과 (n-2)번째 항의 합으로 정의됩니다.

피보나치 수열을 생성하는 방법에는 재귀(recursion)를 사용하는 접근법도 있지만, 동적 프로그래밍(Dynamic Programming)을 활용하면 훨씬 더 간단하고 효율적으로 처리할 수 있습니다. 지금까지 계산한 모든 피보나치 수를 배열(테이블)에 저장해 두면, 이미 구한 값을 다시 계산하지 않고도 그 테이블을 참조해 다음 항들을 손쉽게 만들어 낼 수 있습니다.

입력 및 출력

프로그램은 항의 개수를 입력받고, 해당 위치의 피보나치 값을 출력합니다.

Input:
항의 개수 입력 (예: 10)
Output:
Enter number of terms: 10
10th Fibonacci Terms: 55

알고리즘

의사코드(pseudo-code)는 다음과 같습니다.

genFiboSeries(n)

입력: 최대 항의 개수 n

출력: n번째 피보나치 항

Begin
    define array named fibo of size n+2
    fibo[0] := 0
    fibo[1] := 1

    for i := 2 to n, do
        fibo[i] := fibo[i-1] + fibo[i-2]
    done
    return fibo[n]
End

단계별 설명

1. 크기가 n+2인 배열 fibo를 선언합니다.
2. 초기값으로 fibo[0] = 0, fibo[1] = 1을 설정합니다.
3. i를 2부터 n까지 반복하면서 fibo[i] = fibo[i-1] + fibo[i-2] 공식으로 각 항을 차례대로 계산합니다.
4. 모든 반복이 끝나면 fibo[n]을 반환합니다.

C++ 예제 코드

#include<iostream>
using namespace std;

int genFibonacci(int n) {
    int fibo[n+2];              // 피보나치 값을 저장할 배열

    // 수열의 0번째와 1번째 값은 각각 0과 1
    fibo[0] = 0;
    fibo[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];   // 이전 두 항을 이용해 i번째 항 생성
    }
    return fibo[n];
}

int main () {
    int n;
    cout << "Enter number of terms: "; cin >>n;
    cout << n<<" th Fibonacci Terms: "<<genFibonacci(n)<<endl;
}

실행 결과

Enter number of terms: 10
10th Fibonacci Terms: 55

복잡도 분석

위 동적 프로그래밍 방식의 시간 복잡도는 O(n)이며, 배열에 값을 저장하므로 공간 복잡도 역시 O(n)입니다. 반면 단순 재귀로 구현하면 같은 항을 여러 번 중복 계산하게 되어 시간 복잡도가 지수적으로 증가할 수 있습니다. 따라서 n이 커질수록 동적 프로그래밍 기반의 구현이 훨씬 효율적이라는 점을 알 수 있습니다.