동적 계획법이 진짜 뭔지

"동적 계획법은 알고리즘에서 가장 무서운 이름이랑 가장 단순한 아이디어 중 하나를 가졌어: 같은 부분 문제를 두 번 풀지 마. Richard Bellman 이 예산 위원회한테 인상적으로 들리려고 말 그대로 이름을 골랐어. 겁먹지 마."

이름은 마케팅 트릭이야

'동적 계획법' 은 고급 마법처럼 들려. 아니야. 1950년대에 이걸 만든 Bellman 이 나중에 인정했어, '동적' 은 흥미롭게 들려서, '계획법 (programming)' 은 비용 절감 보스한테 수학 연구를 위장하려 골랐다고. 실제 아이디어는 겸손해: 각 부분 문제를 한 번 풀고, 답을 저장하고, 다시 계산하는 대신 재사용해. 재귀 트랙에서 피보나치 메모이제이션이 O(2ⁿ) 를 O(n) 으로 무너뜨릴 때 이미 했어. 그게 동적 계획법이었어. 무서운 라벨 없이 DP 를 하고 있었던 거야.

두 조건

문제가 DP 에 굴복하는 건 이 둘 다 가질 때야:

겹치는 부분 문제: 순진한 재귀가 같은 더 작은 문제를 계속 풀게 돼 (피보나치 재귀 트리의 반복 서브트리). 이게 캐싱이 값하게 만들어 — 모든 부분 문제가 고유하면, 재사용할 게 없어.
최적 부분 구조: 전체 문제의 최적 해법이 부분 문제의 최적 해법으로 지어짐. (B 통한 A→C 최단 경로가 최단 A→B 랑 B→C 경로를 써.) 이게 부분-답을 전체 답으로 결합하게 해.

둘 다 있음 → DP 적용. 부분 문제 안 겹침 → 그냥 분할 정복 (캐시할 거 없음). 최적 부분 구조 없음 → 부분으로 답을 안전하게 못 지어, DP 안 통해.

동적 계획법 = 각 부분 문제를 한 번 풀고 답을 재사용. 문제가 겹치는 부분 문제 (같은 더 작은 문제가 반복, 그래서 캐싱이 도움) *그리고* 최적 부분 구조 (최선 전체가 최선 부분으로 지어짐) 를 가질 때 적용. '조심스러운 무차별' 이야 — 반복 안 하는 재귀.

DP vs 분할 정복

지난 트랙과의 구분이 정확해. 분할 정복 (병합 정렬) 은 독립적인 부분 문제로 쪼개 — 두 반이 아무것도 공유 안 해, 그래서 캐시할 게 없어. 동적 계획법은 겹치는 부분 문제로 쪼개 — 같은 부분-답이 많은 데서 필요해, 그래서 그걸 캐시하는 게 승리 전부야. 같은 재귀 본능; 차이는 부분 문제가 반복되냐야. 반복되면, 다시 계산하길 멈추고 기억하기 시작해. '다시 계산' 에서 '기억' 으로의 그 전환이 규율 전부야.

피파의 고백

'동적 계획법' 이 몇 년 날 겁줬어 — 나보다 똑똑한 사람 주제처럼 들렸어. 그러다 아빠가 이름이 Bellman 의 의도적 위장이라고 말하고, 내가 이미 쓴 메모이제이션 피보나치가 DP 였다고 보여줬어. 공포가 증발했어. 교훈이 강하게 일반화됐어: 위협적인 이름이 종종 차려입은 단순 아이디어를 감추고, 수는 그 아래 평범한 문장을 찾는 거야. DP 엔, 그 문장이 그냥 '같은 걸 두 번 계산하지 마' 야.

Code

메모이제이션 피보나치가 곧 동적 계획법·python

# 재귀 트랙에서 이미 DP 를 썼어. 여기, 이름 붙여서.
from functools import lru_cache

# 순진: 겹치는 부분 문제 다시 계산 -> O(2^n).
def fib_naive(n):
    if n < 2: return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# 동적 계획법 (top-down): 각 부분 문제를 한 번 풀고, 재사용.
@lru_cache(maxsize=None)
def fib_dp(n):
    if n < 2: return n
    return fib_dp(n - 1) + fib_dp(n - 2)   # 같은 점화식, 이제 캐시됨

print(fib_dp(50))   # 12586269025 — 즉시

# 피보나치에 확인한 두 DP 조건:
#   겹치는 부분 문제? 그래 — fib(3), fib(4)... 가 트리 곳곳에 반복.
#   최적 부분 구조?   그래 — fib(n) 이 fib(n-1),fib(n-2) 로 바로 지어짐.
# 둘 다 성립 -> DP 적용. 순진에서 유일한 변화: 각 답을 기억.

Exercise

각각, 두 조건을 확인해 DP 후보인지 정해: (1) n! 계산 — 겹치는 부분 문제가 있어? (2) 격자의 왼쪽 위에서 오른쪽 아래까지 오른쪽/아래로만 움직이는 구별되는 경로 수. 겹치는 부분 문제랑 최적 부분 구조 관점에서 각 판정을 설명해.

Hint

n! 은 최적 부분 구조는 있지만 겹치는 부분 문제는 없어 (각 factorial(k) 가 순진해도 한 번 계산) — 그래서 DP 아니라 평범한 재귀. 격자 경로: paths(i,j) = paths(i-1,j) + paths(i,j-1), 같은 (i,j) 부분 문제가 많은 경로에 걸쳐 반복 — 겹침 + 최적 부분 구조 → 교과서 DP.

이름은 마케팅 트릭이야

두 조건

DP vs 분할 정복

피파의 고백

Code

External links

Exercise

Progress

댓글 0