동적 계획법 (Dynamic Programming - 피보나치)
복잡한 문제를 여러 개의 간단한 하위 문제(Sub-problem)로 나누어 푸는 방법입니다. 하위 문제들의 계산 결과를 저장(Memoization)하여 중복 계산을 방지하는 것이 핵심입니다.
일반 재귀호출의 시간 복잡도 O(2^n)을 O(n) 수준으로 최적화할 수 있습니다.
// 메모이제이션을 위한 객체 (캐시)
const memo = {};
function fibonacci(n) {
if (n <= 1) return n;
// 이미 계산한 적이 있다면 캐시된 값을 즉시 반환
if (memo[n]) {
console.log(`F(${n})은 캐시에서 가져옴: ${memo[n]}`);
return memo[n];
}
console.log(`F(${n}) 계산 중...`);
// 계산 결과를 캐시에 저장
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
console.log("피보나치 5번째 수 구하기:");
console.log("결과:", fibonacci(5));