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 만들기: 그리디가 4, 그다음 1, 그다음 1 = 세 동전 잡는데, 3+3 = 두 동전이 나아. 그리디는 국소 선택에 헌신하고 재고 못 해; DP 는 모든 선택을 고려하되 캐시해 효율적으로 유지. 그리디가 틀린 걸 잡으면 — 또는 틀릴까 의심만 해도 — 그게 상태를 정의하고 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] 를 문장으로 정의하고, 전이를 쓰고 (숫자 하나 디코딩 vs 둘 고려), 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 (빈 문자열, 한 방법). 상태 문장이 두 갈래 더하기를 명백하게 해.

인식 신호

다섯 단계 프레임워크

그리디의 실패가 DP 의 신호

피파의 고백

Code

External links

Exercise

Progress

댓글 0