피보나치 DP 시각화
재귀 트리 폭발 vs 메모이제이션/테이블레이션의 효율 비교로 배우는 DP 입문
동적 프로그래밍★☆☆
속도
1 / 1호출 횟수: 0결과: -단계 수: 0
알고리즘 모드
fib(8)
현재 노드방문 완료메모 적중기저 조건
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
피보나치 DP란?
피보나치 수열(0, 1, 1, 2, 3, 5, 8, ...)을 계산하는 3가지 방법을 비교합니다. 나이브 재귀는 동일한 부분 문제를 반복 계산하여 O(2^n)이 되고, 메모이제이션(탑다운)과 테이블레이션(바텀업)은 중복 계산을 제거하여 O(n)으로 최적화합니다.
사용 방법
- 1알고리즘 모드(나이브/메모이제이션/테이블레이션)를 선택합니다
- 2슬라이더로 N 값을 조절합니다 (나이브: 0~10, DP: 0~15)
- 3실행 버튼을 누르거나 재생 버튼으로 애니메이션을 시작합니다
- 4단계 전진/후퇴 버튼으로 한 단계씩 확인합니다
- 5코드 탭에서 현재 실행 중인 코드 라인을 확인합니다
동작 원리
- 1나이브 재귀: fib(n) = fib(n-1) + fib(n-2)를 그대로 호출. 호출 트리가 지수적으로 폭발합니다 (fib(10)에 177번 호출)
- 2메모이제이션: 이미 계산한 값을 memo 객체에 캐싱. 같은 fib(k) 재호출 시 O(1)로 반환하여 가지를 쳐냅니다
- 3테이블레이션: dp[0]=0, dp[1]=1부터 시작하여 dp[i] = dp[i-1] + dp[i-2]로 테이블을 순차 채웁니다
- 4메모이제이션과 테이블레이션 모두 O(n) 시간, O(n) 공간. 테이블레이션은 재귀 스택이 없어 스택 오버플로가 없습니다
실무 활용
- •동적 프로그래밍의 가장 기본적인 입문 예제로 코딩 테스트에 자주 출제됩니다
- •피보나치 힙, 황금비 관련 알고리즘에 피보나치 수가 등장합니다
- •메모이제이션 패턴은 React.memo, useMemo, Python의 @lru_cache 등에 응용됩니다
- •테이블레이션 패턴은 배낭 문제, LCS, 편집 거리 등 DP 문제의 기본 틀입니다
학습 팁
- •나이브 모드에서 N=8로 실행하면 트리가 얼마나 거대한지 체감할 수 있습니다
- •메모이제이션 모드에서 노란색 'memo' 노드를 주목하세요 — 가지가 잘리는 것을 확인합니다
- •세 모드의 호출 횟수를 비교하면 DP의 위력을 수치로 이해할 수 있습니다
자주 묻는 질문
Q. 메모이제이션과 테이블레이션의 차이는?
A. 메모이제이션은 탑다운(재귀 + 캐싱), 테이블레이션은 바텀업(반복문 + 테이블). 결과는 같지만 테이블레이션은 재귀 스택이 없어 N이 클 때 안전합니다.
Q. 왜 나이브 재귀는 N=10까지만 가능한가요?
A. N=10에서도 177번 호출이 발생합니다. N=20이면 21,891번, N=30이면 약 268만 번으로 브라우저가 멈출 수 있습니다.
Q. O(n) 공간도 줄일 수 있나요?
A. 네, 이전 두 값만 저장하면 O(1) 공간으로 최적화할 수 있습니다. 하지만 DP 테이블 전체가 필요한 역추적이 있는 문제에서는 O(n) 공간이 필요합니다.