피보나치 수열은 다음과 같은 형태를 가지는 수열입니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……
이 수열에서 n번째 항은 바로 앞의 두 항, 즉 (n-1)th 항과 (n-2)th 항의 합으로 정의됩니다.
피보나치 수를 구하는 가장 직관적인 방법은 재귀(recursion)를 사용하는 것이지만, 재귀 방식은 같은 값을 여러 번 반복해서 계산하게 되어 항이 커질수록 실행 시간이 급격히 늘어나는 단점이 있습니다. 반면 동적 프로그래밍(Dynamic Programming)을 활용하면 이러한 비효율을 제거하고 훨씬 빠르게 결과를 얻을 수 있습니다.
동적 프로그래밍의 원리
동적 프로그래밍은 한 번 계산한 결과를 테이블(배열)에 저장해 두었다가, 이후 동일한 값이 필요할 때 다시 계산하지 않고 저장된 값을 그대로 재사용하는 기법입니다. 피보나치 수열의 경우 이미 계산한 수들을 배열에 차례대로 저장하고, 이를 활용해 다음 항을 손쉽게 생성할 수 있습니다. 덕분에 재귀 방식의 지수 시간 복잡도 O(2n) 대신 선형 시간 복잡도 O(n)만으로 문제를 해결할 수 있습니다.
입력 및 출력
- 입력 − 구하고자 하는 항의 번호를 입력받습니다. 예를 들어 10을 입력한다고 가정합니다.
- 출력 − 10번째 피보나치 항인 55가 출력됩니다.
알고리즘
genFiboSeries(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
알고리즘의 흐름을 정리하면 다음과 같습니다. 먼저 크기가 n+2인 배열을 준비하고, 초깃값으로 0번째 항은 0, 1번째 항은 1을 저장합니다. 이후 2번째 항부터 n번째 항까지 반복문을 돌며 이전 두 항의 합을 차례로 채워 넣고, 마지막에 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;
}코드 설명
함수 genFibonacci(int n)는 크기가 n+2인 배열 fibo를 선언하여 피보나치 값을 저장합니다. 배열의 첫 두 요소에는 각각 0과 1이라는 초깃값을 넣고, 반복문을 통해 2번째 항부터는 fibo[i-1]과 fibo[i-2], 즉 바로 앞의 두 항을 더한 값을 저장합니다. 모든 항이 채워지면 fibo[n]을 반환하여 원하는 n번째 피보나치 수를 구합니다. main 함수에서는 사용자로부터 항의 번호를 입력받아 결과를 화면에 출력합니다.
실행 결과
Enter number of terms: 10 10th Fibonacci Terms: 55
마무리
이처럼 동적 프로그래밍을 활용하면 단순 반복문 몇 줄만으로 피보나치 수를 효율적으로 계산할 수 있습니다. 재귀 호출에 따른 스택 오버플로 위험도 없고, 시간 복잡도 역시 O(n)으로 매우 효율적이므로, 큰 n값을 다루어야 하는 경우에도 안정적으로 동작합니다. 추가로 공간까지 절약하고 싶다면 배열 전체 대신 최근 두 항의 값만 유지하는 변수 두 개만으로도 같은 결과를 얻을 수 있습니다.