언제 쓰나
- “경우의 수를 구하라”, “최대/최소 비용을 구하라” — 그런데 완전 탐색은
O(2^n)으로 터질 때 - 지금의 선택이 이후 선택지에 영향을 주는 최적화 문제 (그리디가 깨지는 자리)
- 같은 부분 문제가 반복 계산되는 재귀 — 피보나치가 원형이다
두 가지 성질이 보이면 DP다. 겹치는 부분 문제(같은 계산이 반복됨)와 최적 부분 구조(작은 문제의 최적해로 큰 문제의 최적해를 만들 수 있음).
핵심 아이디어
단순 재귀 피보나치는 같은 값을 셀 수 없이 다시 계산한다. 한 번 구한 답을 표에 저장하면 각 문제를 정확히 한 번만 푼다.
단순 재귀: fib(5) DP 표 채우기:
/ \
fib(4) fib(3) i : 0 1 2 3 4 5
/ \ / \ dp[i]: 0 1 1 2 3 5
fib(3) fib(2) ... └──┴─→ dp[i] = dp[i-1] + dp[i-2]
fib(2)가 3번, fib(1)이 5번… 각 칸을 한 번씩만 계산 → O(n)
→ O(2^n)풀이 순서는 늘 같다. ① 상태 정의(dp[i]가 무엇을 뜻하는가) → ② 점화식(작은 답들로 dp[i]를 어떻게 만드는가) → ③ 초기값 → ④ 채우는 방향.
코드 템플릿
바텀업(반복문) — 표를 작은 문제부터 채운다. 코테에서는 재귀 한도 걱정이 없는 이쪽이 기본이다.
def fib(n):
if n < 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]탑다운(메모이제이션) — 점화식을 재귀 그대로 옮기고 캐시만 붙인다. 상태 전이가 복잡할 때 편하다.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)실전 꼴 — “계단 오르기: 한 칸 또는 두 칸씩, i번째 계단까지 점수 최대” 같은 문제는 상태 정의만 바뀐다.
# dp[i] = i번째 계단을 밟았을 때의 최대 점수
dp[i] = max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i]풀이 과정 따라가기
피보나치 DP 표가 채워지는 과정이다. 각 칸은 정확히 한 번만 계산된다.
함정
- 상태 정의가 절반이다. 막히면 점화식이 아니라
dp[i]의 의미부터 다시 쓴다. “i번째까지의 최대”인지 “i번째를 반드시 포함한 최대”인지에 따라 점화식이 완전히 달라진다. - 초기값과 작은 입력.
n = 1, 2같은 경계에서 인덱스 에러나 틀린 초기값이 가장 흔한 오답 원인이다. - 파이썬 재귀 탑다운. 깊이가 수만이면
RecursionError—setrecursionlimit을 올리거나 바텀업으로 바꾼다. - 메모리 초과.
dp[i]가 직전 몇 개만 참조하면 배열 전체 대신 변수 2~3개로 줄일 수 있다(토글링).