DP 점화식은 문제를 작은 상태로 나누고, 그 상태 사이의 관계를 식으로 적은 것입니다. DP를 어려워하는 이유는 코드가 아니라 상태를 어떻게 잡아야 할지에서 막히기 때문입니다.
핵심은 상태, 선택, 초기값, 계산 순서를 따로 보는 것입니다. 이 네 가지가 맞아야 점화식이 실제 코드로 내려옵니다.
DP는 왜 반복 계산을 줄이는 알고리즘일까
동적 계획법은 같은 부분 문제를 여러 번 풀지 않기 위해 결과를 저장합니다. 피보나치처럼 f(n)을 구할 때 f(n-1), f(n-2)가 계속 반복된다면, 한 번 계산한 값을 저장해서 다시 쓰는 것이 DP의 출발점입니다.
1단계: 상태를 정의한다
상태는 답을 구하는 데 필요한 최소 정보입니다. 예를 들어 계단 오르기 문제라면 dp[i]를 ‘i번째 계단까지 왔을 때의 최대 점수’로 정의할 수 있습니다.
상태가 너무 작으면 필요한 정보를 잃고, 너무 크면 테이블이 커져서 풀기 어려워집니다.
2단계: 선택을 찾는다
선택은 현재 상태로 오기 직전에 무엇을 했는지입니다. i번째 계단에 오려면 i-1에서 왔는지, i-2에서 왔는지처럼 이전 상태 후보를 찾습니다.
dp[i] = max(
dp[i - 1] + cost_from_i_minus_1,
dp[i - 2] + cost_from_i_minus_2
)3단계: 초기값을 정한다
점화식은 이전 상태를 참조하므로 시작점이 필요합니다. dp[0], dp[1]처럼 직접 계산 가능한 값이 초기값입니다. 초기값이 틀리면 뒤의 값이 모두 맞아도 전체 답이 흔들립니다.
4단계: 계산 순서를 정한다
dp[i]가 dp[i-1]과 dp[i-2]를 필요로 한다면 작은 i부터 큰 i로 채워야 합니다. 반대로 뒤 상태를 참조하는 문제라면 역순이나 재귀 메모이제이션이 더 자연스러울 수 있습니다.
def climb(n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]예제로 보는 상태 정의: 동전 만들기
여러 동전으로 금액 x를 만드는 최소 동전 개수를 구한다고 해봅니다. 이때 상태는 dp[x]로 둘 수 있습니다. 의미는 ‘금액 x를 만드는 데 필요한 최소 동전 수’입니다.
dp[x] = 금액 x를 만드는 최소 동전 수
선택:
마지막에 coin을 하나 사용했다면
이전 상태는 dp[x - coin]
점화식:
dp[x] = min(dp[x], dp[x - coin] + 1)이렇게 쓰면 점화식은 갑자기 나온 공식이 아니라 ‘마지막에 어떤 동전을 선택했는가’에서 자연스럽게 나옵니다.
def min_coins(coins: list[int], amount: int) -> int:
INF = 10**9
dp = [INF] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
for coin in coins:
if x - coin >= 0:
dp[x] = min(dp[x], dp[x - coin] + 1)
return -1 if dp[amount] == INF else dp[amount]top-down과 bottom-up은 무엇이 다를까
top-down은 필요한 상태를 재귀로 내려가며 계산하고 memo에 저장합니다. 문제를 그대로 함수로 옮기기 쉬운 장점이 있습니다. bottom-up은 작은 상태부터 테이블을 채웁니다. 순서가 보이면 반복문으로 깔끔하게 쓸 수 있습니다.
- top-down: 상태 전이가 복잡하고 필요한 상태만 계산하고 싶을 때 편하다
- bottom-up: 계산 순서가 명확하고 전체 테이블을 채워도 부담이 적을 때 편하다
- 둘 다 핵심은 같은 상태를 반복 계산하지 않는 것이다
DP에서 자주 틀리는 지점
- dp[i]의 의미를 말로 설명하지 못한 채 코드를 먼저 쓴다
- 초기값을 문제의 가장 작은 입력과 맞추지 않는다
- 현재 값이 이전 값을 참조해야 하는데 순회를 반대로 한다
- 0/1 선택 문제와 무제한 선택 문제의 순회 방향을 섞는다
- 정답 상태가 dp[n]인지 max(dp)인지 확인하지 않는다
점화식을 검증하는 작은 입력 테스트
DP는 작은 입력을 손으로 계산해보는 과정이 중요합니다. n=1, n=2, n=3처럼 아주 작은 값을 직접 써보고, 점화식이 그 값을 재현하는지 확인하면 초기값과 전이 오류를 빠르게 찾을 수 있습니다.
검증 순서
1. 가장 작은 입력의 답을 손으로 쓴다.
2. 점화식이 그 답을 만들 수 있는지 본다.
3. 중간 입력 하나를 직접 계산한다.
4. 코드 결과와 손계산 결과를 비교한다.상태 차원이 늘어나는 신호
dp[i] 하나로 답이 안 나오면 상태에 정보가 더 필요하다는 뜻일 수 있습니다. 예를 들어 마지막 선택이 무엇이었는지, 몇 번 연속으로 골랐는지, 남은 용량이 얼마인지가 다음 선택에 영향을 준다면 상태 차원을 늘려야 합니다.
- 위치만 알면 된다: dp[i]
- 위치와 남은 용량이 필요하다: dp[i][w]
- 마지막 선택 여부가 필요하다: dp[i][used]
- 두 문자열의 위치가 필요하다: dp[i][j]
점화식이 안 떠오를 때 보는 질문
- 이 문제의 답을 한 문장으로 정의하면 무엇인가
- 답을 구하는 데 필요한 최소 정보는 무엇인가
- 마지막 선택은 무엇인가
- 이전 상태 중 어떤 것에서 현재 상태로 올 수 있는가
- 가장 작은 입력에서는 답이 무엇인가
정리
DP 점화식은 외워서 나오는 공식이 아니라 상태와 선택을 정확히 나누면 생기는 관계식입니다. 상태 정의가 먼저이고, 그다음 선택과 초기값, 계산 순서를 맞춰야 합니다.
DP의 기본 원리는 CP-Algorithms 동적 계획법 입문에서 확인할 수 있습니다. 메모리 최적화는 DP 테이블 1차원 최적화 글과 이어서 보면 좋습니다.
