DP 점화식은 외워서 끼워 넣는 공식이 아닙니다. 문제마다 값의 의미가 다르기 때문에, 먼저 `dp[i]`가 무엇을 뜻하는지 한 문장으로 고정해야 합니다.
핵심은 상태 정의가 흔들리면 점화식도 흔들린다는 점입니다. 이 글은 DP를 처음 배울 때 가장 많이 막히는 상태 정의, 이전 상태, 초기값, 순회 방향을 쉬운 예제로 설명합니다.
DP 점화식은 상태 정의에서 시작한다
DP 문제를 보면 많은 사람이 바로 공식을 찾습니다. 하지만 공식은 결과입니다. 먼저 정해야 할 것은 `dp[i]`가 무엇을 의미하는지입니다.
예를 들어 계단 오르기 문제에서 `dp[i]`를 ‘i번째 계단에 도착하는 방법의 수’로 볼 수도 있고, ‘i번째 계단까지 왔을 때 얻을 수 있는 최대 점수’로 볼 수도 있습니다. 같은 i라도 의미가 다르면 점화식도 완전히 달라집니다.
상태 정의는 한 문장으로 말할 수 있어야 한다
- `dp[i]`는 i번째 위치까지 고려했을 때의 정답이다
- `dp[i][j]`는 i번째 물건까지 보고 무게 j일 때의 최대 가치다
- `dp[i]`는 i번째 계단에 도착했을 때 얻을 수 있는 최대 점수다
좋은 상태 정의는 나중에 코드 변수명과 주석으로 옮겨도 어색하지 않습니다. 반대로 ‘뭔가 최댓값’처럼 흐리게 잡으면 전이식을 만들 때마다 헷갈립니다.
마지막 선택을 보면 이전 상태가 보인다
점화식은 현재 상태가 어떤 이전 상태에서 왔는지를 쓰는 식입니다. 이때 가장 좋은 질문은 ‘마지막에 무엇을 선택했나?’입니다.
계단을 한 칸 또는 두 칸 오를 수 있고, n번째 계단에 도착하는 방법의 수를 구한다고 해보겠습니다. n번째 계단에 도착하는 마지막 선택은 한 칸 오르기 또는 두 칸 오르기뿐입니다.
dp[i] = i번째 계단에 도착하는 방법의 수
마지막 선택 1: i-1번째에서 한 칸 오른다 -> dp[i-1]
마지막 선택 2: i-2번째에서 두 칸 오른다 -> dp[i-2]
dp[i] = dp[i-1] + dp[i-2]초기값은 점화식이 시작되는 바닥이다
점화식이 맞아도 초기값이 틀리면 전체 답이 틀립니다. 초기값은 더 작은 문제로 내려갈 수 없는 가장 작은 상태입니다.
def climb(n: int) -> int:
if n <= 1:
return 1
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]여기서 `dp[0] = 1`이 낯설 수 있습니다. 하지만 ‘아무 계단도 오르지 않는 방법 1개’로 보면 점화식이 자연스럽게 이어집니다.
순회 방향은 의존 관계를 따른다
DP는 이미 계산한 값을 사용합니다. 그래서 현재 상태가 의존하는 이전 상태가 먼저 계산되어 있어야 합니다. 이것이 순회 방향입니다.
- `dp[i]`가 `dp[i-1]`에 의존하면 앞에서 뒤로 돈다
- `dp[i][j]`가 이전 행에 의존하면 물건 순서대로 돈다
- 1차원으로 압축할 때 같은 값을 중복 사용하지 않으려면 뒤에서 앞으로 돌 때가 있다
0/1 배낭으로 보는 상태와 전이
0/1 배낭 문제는 DP 상태 정의를 연습하기 좋습니다. 각 물건은 한 번만 쓸 수 있고, 무게 제한 안에서 가치 합을 최대로 만들어야 합니다.
dp[i][w] = i번째 물건까지 고려했고,
현재 무게 제한이 w일 때 얻을 수 있는 최대 가치
선택 1: i번째 물건을 담지 않는다
dp[i-1][w]
선택 2: i번째 물건을 담는다
dp[i-1][w - weight[i]] + value[i]
dp[i][w] = max(선택 1, 선택 2)이 식에서 중요한 부분은 `dp[i-1]`입니다. 같은 물건을 여러 번 쓰면 안 되기 때문에 이전 물건까지만 고려한 상태에서 넘어옵니다.
DP 문제인지 판단하는 기준
- 같은 부분 문제가 반복해서 등장한다
- 현재 선택이 이후 결과에 영향을 준다
- 완전탐색으로 모든 경우를 보면 중복 계산이 많다
- 작은 문제의 정답을 이용해 큰 문제의 정답을 만들 수 있다
흔한 실수
- 상태 의미를 정하지 않고 식부터 외운다
- 초기값을 문제의 실제 의미가 아니라 감으로 넣는다
- 이전 상태가 아직 계산되지 않았는데 현재 상태를 계산한다
- 최댓값 문제와 경우의 수 문제를 같은 구조로 착각한다
- 1차원 압축에서 순회 방향을 잘못 잡아 같은 물건을 여러 번 쓴다
정리
DP 점화식은 문제를 푸는 첫 단계가 아니라, 상태 정의와 선택 분석의 결과입니다. `dp[i]`가 무엇인지 한 문장으로 고정하고, 마지막 선택을 기준으로 이전 상태를 찾으면 점화식은 훨씬 덜 막힙니다.
알고리즘 사고 흐름은 이분 탐색은 정렬된 배열에서만 쓰는 걸까, greedy 반례부터 봐야 하는 이유, Dijkstra visited 사용 기준와 함께 보면 좋습니다. 외부 기준은 CP-Algorithms – Introduction to Dynamic Programming, USACO Guide – Dynamic Programming Introduction, Wikipedia – Dynamic programming를 확인했습니다.
