DP 문제를 보는 법

"DP의 메커니즘 자체는 쉬워. 점화식을 캐시하면 되니까. 진짜 실력은 두 군데서 갈려. 애초에 '이거 DP네'를 알아채는 눈, 그리고 상태가 뭐여야 하는지 못 박는 손. 이 둘을 잡으면 DP는 더 이상 무섭지 않아."

인식 신호

문제 문구 가운데 머릿속 '동적 계획법' 스위치를 켜야 하는 것들이 있어:

뭔가를 하는 '방법 수를 세라'는 문제. 격자를 지나는 경로 수, 문자열을 디코딩하는 방법 수, 거스름돈을 만드는 방법 수.
선택의 연속 위에서 '최소화하라, 최대화하라'는 문제. 최소 동전 수, 최대 전리품, 최장 부분수열, 최저 비용 경로.
제약을 만족하게 '분할하거나 고르거나 배열할 수 있느냐'는 문제. 부분집합 합, 배낭.
자연스러운 재귀가 있는데 같은 부분 문제를 다시 계산하는 경우. 이 겹침이 가장 큰 신호야.
그리디가 끌리는데 답이 틀리는 경우. 동전 교환에서 '가장 큰 동전부터'가 실패하듯. 그리디가 깨지는 자리엔 DP가 약이 되는 일이 잦아.

다섯 단계 프레임워크

DP가 의심되면 다섯 단계로 설계해. 그리고 진짜 승부는 첫 단계에서 나:

상태를 정의해. 'dp[...]는 ___의 답이다' 문장을 완성해. 어려운 단계는 여기 하나야. 이게 맞으면 나머지는 기계적으로 풀리고, 틀리면 아무것도 안 돌아가.
전이를 써. dp[상태]를 더 작은 상태들로 표현해. 그게 점화식이야.
base case를 찾아. 직접 답할 수 있는 가장 작은 상태들.
순서를 골라. top-down(재귀 메모이제이션)이든 bottom-up(테이블화)이든, 어느 쪽이든 돼.
필요하면 공간을 최적화해. 아직 참조되는 칸만 남기고.

1단계가 단단하면 2–5단계는 일상 업무야. DP의 난이도는 통째로 상태 정의 한 곳에 몰려 있어. 'dp 문장부터 써'가 이 트랙 전체의 관통선이었던 이유지.

DP 레시피: (1) 상태 정의. dp[...]가 나타내는 답을 문장으로, 여기가 어려운 부분. (2) 더 작은 상태로 전이 쓰기. (3) base case. (4) 순서 고르기(메모이제이션 또는 테이블화). (5) 공간 최적화. DP로 향하는 신호는 '방법 수 세기', '선택의 연속 위 최적화', 겹치는 재귀, 그리고 실패하는 그리디야.

그리디의 실패는 어디까지 신호인가

그리디 반례는 그 그리디 규칙 하나가 틀렸음을 증명할 뿐이야. DP가 필요하다는 자동 증명이 아니야. 동전 {1, 3, 4}로 6을 만들 때 가장 큰 동전부터 고르는 규칙은 실패하고, 이 문제엔 금액을 상태로 둔 DP가 잘 맞아. 하지만 다른 문제라면 더 나은 그리디, 그래프 알고리즘, 분기 한정법이 답일 수도 있어. 상태와 겹침은 따로 확인해.

피파의 고백

한참 동안 난 DP 문제 앞에서 전체 테이블을 한 번에 그리려다 얼어붙곤 했어. 아빠가 지시 하나로 그걸 잘라 냈지. "테이블 그리지 마. 이 문장만 끝내: dp of i 쉼표 j 는 뭐의 답이야?" 칸 하나가 뭘 뜻하는지 말할 수 있게 된 순간, 전이는 저절로 쓰였어. 돌아보면 내가 막혔던 DP는 하나같이 분명하게 정의하지 않은 상태가 문제였어. 캐싱 문제였던 적은 한 번도 없어. 언제나 '내가 대체 뭘 계산하고 있는 거야?'의 문제였지.

Code

인식 → 상태 정의 → 전이 → base → 순서·python

# 인식 실습: 격자 통한 '고유 경로 수 세기', 오른쪽이나 아래로만.
# '방법 수 세기' 구절이 DP 라고 외쳐.

# 1단계 - 상태: dp[i][j] = (0,0) 에서 칸 (i,j) 까지 경로 수.
# 2단계 - 전이: (i,j) 에 위 (i-1,j) 나 왼쪽 (i,j-1) 에서 닿아.
#          dp[i][j] = dp[i-1][j] + dp[i][j-1].
# 3단계 - base case: 맨 위 행이랑 왼쪽 열은 각각 경로가 정확히 1.
# 4단계 - 순서: 행별로 채움 (각 칸이 위 & 왼쪽 필요, 이미 됨).
def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]   # base case: 가장자리 다 1
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]   # 전이
    return dp[rows-1][cols-1]

print(unique_paths(3, 3))   # 3x3 격자 통한 6 경로
# 주목: 상태 문장 ('(i,j) 까지 경로') 이 분명해지자, 다른 모든 단계가
# 기계적으로 떨어졌어. 상태 정의가 싸움 전부야.

Exercise

다섯 단계 프레임워크를 '디코딩 방법 수'에 적용해 봐. 1→A … 26→Z로 읽는 숫자 문자열에서 가능한 디코딩 방법 수를 세는 문제야(예: '12'는 'AB' 또는 'L', 그래서 2). 상태 dp[i]를 문장으로 정의하고, 전이를 쓰고(숫자 하나만 디코딩하는 경우와 두 자리를 묶는 경우), base case를 말해. 코딩은 없어도 돼. 설계만 해 봐.

Hint

상태는 dp[i] = 첫 i글자를 디코딩하는 방법 수. 전이는 dp[i] = dp[i-1](s[i-1]이 1–9의 유효한 한 자리면) + dp[i-2](s[i-2:i]가 10–26의 유효한 두 자리면). base는 dp[0] = 1(빈 문자열, 한 가지 방법). 상태 문장이 서면 두 갈래를 더하는 이유가 명백해져.

인식 신호

다섯 단계 프레임워크

그리디의 실패는 어디까지 신호인가

피파의 고백

Code

External links

Exercise

Progress

댓글 0