피보나치 수열이란?
피보나치 수열은 첫 두 항을 제외한 모든 항이 바로 앞의 두 항의 합으로 이루어지는 수열입니다. 수열은 1, 1로 시작하며 다음과 같습니다.
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
단순 재귀로 구현하기
n번째 피보나치 수를 구하는 가장 직관적인 방법은 재귀 함수를 사용하는 것입니다.
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
다음과 같이 테스트해 볼 수 있습니다.
console.log(fibNaive(7)); console.log(fibNaive(8)); console.log(fibNaive(9)); console.log(fibNaive(4));
실행 결과는 다음과 같습니다.
13 21 34 3
함수 호출 과정 살펴보기
f(5)를 호출했을 때 실제로 어떤 일이 일어나는지 호출 트리를 통해 확인해 보겠습니다.
/** * f(5) * / \ * f(4) f(3) * / \ / \ * f(3) f(2) f(2) f(1) * / \ .......... * f(2) f(1) .......... */
f(5)를 호출하면 f(2)가 거의 4번 호출되고, 동일한 코드가 여러 번 반복 실행됩니다. 이것이 바로 중복되는 하위 문제(Overlapping Subproblem)의 전형적인 사례입니다. 실제로 이 함수에 500을 넣어 실행해 보면, 수많은 호출로 인해 결과를 얻는 데 매우 오랜 시간이 걸리거나 프로그램이 멈춘 것처럼 보일 것입니다.
동적 프로그래밍으로 개선하기
5번째 피보나치 수가 필요할 때, 우리는 낮은 순서의 피보나치 수들을 각각 한 번씩만 계산하면 되는데도 불구하고 훨씬 많은 횟수로 반복 계산하게 됩니다. 한 번 계산한 값을 어딘가에 저장해 두면 이러한 불필요한 중복 계산을 줄일 수 있습니다. 이것이 바로 동적 프로그래밍(Dynamic Programming)의 핵심 아이디어입니다.
한 번 계산하고, 나중에 재활용한다.
메모이제이션(Memoization)을 적용한 피보나치 함수 구현을 살펴보겠습니다.
let fibStore = {};
function fibDP(n) {
if (n <= 1) return n;
if (fibStore[n]) {
return fibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
return fibStore[n];
}
이제 이미 계산된 값을 추적하기 위해 저장소 역할을 하는 fibStore 객체를 사용합니다. 이를 통해 과도한 중복 계산을 제거하고 함수의 효율성을 크게 높일 수 있습니다.
다음과 같이 테스트해 볼 수 있습니다.
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
실행 결과는 다음과 같습니다.
13 21 34 3
메모이제이션 덕분에 이제 훨씬 큰 값으로도 빠르게 테스트해 볼 수 있습니다.