"동적 계획법만큼 이름이 겁을 주는 주제도 드물어. 속은 단순해. 상태를 정하고, 답을 한 번만 계산해서 재사용해. Bellman이 이 이름을 고른 사연은 예산 위원회까지 등장할 만큼 맛있지만, 그 회고 하나로 기원 전체를 설명하려 들진 마. 이름에 겁먹는 건 더더욱 금지야."
이름은 위장이야
동적 계획법의 실전 핵심은 세 가지야. 상태를 정의하고, 상태 사이의 의존성을 세우고, 한 번 구한 답을 저장해서 아무것도 다시 계산하지 않는 것. Bellman이 이름을 고른 배경을 회고로 남기긴 했지만, 그 일화 하나를 유일한 공식 기원처럼 부풀릴 필요는 없어. 그리고 이 원리, 처음 보는 게 아니야. 피보나치 메모이제이션에서 이미 똑같은 걸 썼잖아.
두 조건
문제가 DP에 굴복하는 건 다음 둘을 다 가질 때야:
- 겹치는 부분 문제: 순진한 재귀가 같은 작은 문제를 계속 다시 풀어. 피보나치 재귀 트리에 반복해서 나타나는 서브트리가 그거야. 캐싱이 본전을 뽑는 이유가 여기 있어. 모든 부분 문제가 제각각이라면 재사용할 것도 없거든.
- 부분 문제에서 결합되는 구조: 최적화 문제라면 최적 부분 구조가 그 역할을 해. 다만 경로 수 세기나 점화식 값 계산처럼 '최적'을 묻지 않는 DP도 있으니, 모든 DP를 최적 부분 구조라는 말 하나에 가두진 마.
겹치는 상태가 보이고, 더 작은 상태의 답을 결합하는 점화식이 보이면 DP 후보야. 겹침이 없으면 메모이제이션의 이득이 작아서 분할 정복이 더 자연스럽고. 최적화 문제에서는 최적 부분 구조를, 세기나 평가 문제에서는 거기 맞는 결합 법칙을 확인해.
동적 계획법 = 각 부분 문제를 한 번만 풀고 답을 재사용하기. 겹치는 부분 문제(같은 작은 문제가 반복돼서 캐싱이 통함)가 있고, 작은 답들을 결합할 구조(최적화 문제라면 최적 부분 구조)가 있을 때 적용해. 반복하지 않는 재귀, 말하자면 '조심스러운 무차별 대입'이야.
DP vs 분할 정복
지난 트랙과의 구분선이 정확히 여기 있어. 분할 정복은 독립적인 부분 문제로 쪼개. 병합 정렬의 두 반쪽은 아무것도 공유하지 않으니 캐시할 것도 없지. 동적 계획법은 겹치는 부분 문제로 쪼개. 같은 부분 답이 여러 곳에서 필요하니, 그걸 캐시하는 게 승부를 통째로 가르는 거야. 재귀 본능은 같아. 차이는 부분 문제가 반복되느냐 하나뿐이야. 반복된다면 다시 계산하기를 멈추고 기억하기 시작해. '다시 계산'에서 '기억'으로 넘어가는 그 전환이 이 규율의 처음이자 끝이야.
피파의 고백
'동적 계획법'이란 이름이 몇 년을 날 겁줬어. 나보다 똑똑한 사람들이나 하는 과목처럼 들렸거든. 그러다 아빠가 그 이름이 Bellman의 의도적인 위장이라는 걸 알려 줬고, 내가 이미 써 본 메모이제이션 피보나치가 바로 DP였다는 걸 보여 줬어. 공포가 증발했지. 이 교훈은 멀리까지 일반화됐어. 위협적인 이름은 종종 차려입은 단순한 아이디어를 감추고 있고, 할 일은 그 밑에 깔린 평범한 문장을 찾는 거야. DP의 평범한 문장은 이거야. '같은 걸 두 번 계산하지 마.'