어려움
Fibonacci Number
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 피보나치(n):2 F[0] = 0, F[1] = 13 반복 k = 2 … n:4 F[k] = F[k-1] + F[k-2]5 반환 F[n]
변수
- F[0]
- 0
- F[1]
- 1
1 / 7F(0)=0, F(1)=1을 기저로 둡니다.
F(n)=F(n-1)+F(n-2)를 표에 한 번씩만 채워 지수 재귀를 O(n)으로 접는다.
왜 헷갈리는가
순진한 재귀는 같은 F(k)를 지수적으로 다시 계산한다(O(2^n)). '이미 구한 값을 저장'하는 메모이제이션/DP로 O(n)이 되는데, 사실 직전 두 값만 있으면 되어 O(1) 공간으로도 된다.
핵심 아이디어
겹치는 하위 문제(F(k)가 여러 번 필요)를 한 번만 계산해 표에 남긴다. 바닥(F0, F1)부터 위로 쌓으면 재귀 호출 폭발이 사라진다.
복잡도
시간 O(n)·공간 O(n)(표) 또는 O(1)(변수 두 개). 순진한 재귀는 O(2^n) — DP의 위력을 가장 극적으로 보여주는 예.
실무에서 어디에 쓰나
피보나치 자체보다, '겹치는 하위 문제를 저장'하는 DP·메모이제이션 사고가 핵심 자산이다.
- 메모이제이션: 반복 계산을 캐시로 접는 모든 곳(렌더·쿼리·비용함수)
- 점화식 모델: 성장/상환/확률의 순차 상태 계산
- 알고리즘 설계: '지수 → 다항'으로 접는 최적화의 원형
- 실무 캐싱 설계의 사고 틀(무엇을 저장해 재사용할까)
흔한 실수
기저(F0, F1) 오설정. 표 없이 재귀로 지수 시간 태우기. 큰 n에서 정수 오버플로(언어별).
기억할 것
- 겹치는 하위 문제 = DP 신호.
- O(2^n) → O(n)의 대표 예.
- 직전 두 값이면 O(1) 공간.
- 메모이제이션=캐싱 사고.