JavaScript로 피보나치 수 계산하기: 동적 프로그래밍 활용
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
웹 개발
대상자
- JavaScript 개발자, 알고리즘 초보자 및 중급자
- 난이도: 중급 (재귀 최적화와 메모화 개념 이해 필요)
핵심 요약
- 동적 프로그래밍(DP)을 통해 피보나치 수 계산의 시간 복잡도를 O(n)으로 최적화
- 메모화(Memoization) 기법을 사용해 중복 계산 제거 및 성능 향상
- 재귀 함수 대신 반복 구조로 구현하여 스택 오버플로우 예방
섹션별 세부 요약
1. 문제 정의
- 피보나치 수열의 n번째 항을 계산하는 문제
- 재귀적 접근 시 O(2^n) 시간 복잡도로 비효율적
- 예:
fib(5) = fib(4) + fib(3)
→ 중복된 계산 발생
2. 동적 프로그래밍 적용
- 메모화를 통해 이전 계산 결과 저장
- 하향식 접근 (Top-down)으로 캐시 사용
- 예:
const memo = {};
→memo[n] = fib(n)
3. 구현 예시
- 이터레이션 기반으로 구현 가능
- 코드 예시:
function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
4. 성능 분석
- 재귀 vs 동적 프로그래밍
- 재귀:
fib(10)
→ 144회 호출 - DP:
fib(10)
→ 10회 호출 - 시간 복잡도: O(n) → 선형 시간 보장
결론
- 메모화 기법을 통해 재귀의 비효율성 극복
- 이터레이션 구현이 더 안정적 (스택 오버플로우 방지)
- 동적 프로그래밍은 중복 계산이 반복되는 문제에 필수적