동적 계획법(Dynamic Programming) 입문: 기억하며 풀기
Algorithm
이름이 참 어렵습니다. "동적(Dynamic)"이라는 단어는 사실 별 의미가 없습니다. 리처드 벨만이라는 수학자가 펀딩을 따내려고 멋진 이름을 붙였다는 설이 유력합니다. 핵심은 **"문제를 쪼개서 풀고, 정답을 기억해 둔다"**입니다. 기억하기 알고리즘이라고 부르는 게 더 직관적일 겁니다.
1. 왜 필요할까? (피보나치 수열)
fib(5) = fib(4) + fib(3)
재귀 함수로 그냥 짜면 fib(2) 같은 똑같은 계산을 수없이 반복합니다. 시간 복잡도가 O(2^n)이라 조금만 숫자가 커져도 계산이 안 끝납니다.
2. DP의 조건
- 최적 부분 구조 (Optimal Substructure): 큰 문제의 답이 작은 문제의 답으로 구성된다.
- 중복되는 부분 문제 (Overlapping Subproblems): 똑같은 작은 문제가 반복해서 나타난다.
3. 구현 방식
3.1 메모이제이션 (Memoization) - Top-down
하위 문제의 결과를 캐시(배열이나 해시맵)에 저장합니다. 다음에 똑같은 문제가 나오면 계산 안 하고 캐시에서 꺼내 씁니다. 재귀를 사용하므로 구현이 직관적입니다.
3.2 타뷸레이션 (Tabulation) - Bottom-up
가장 작은 문제부터(0, 1...) 차근차근 답을 채워 올라갑니다. 반복문(for)을 사용합니다. 함수 호출 오버헤드가 없어서 미세하게 더 빠를 수 있습니다.
4. 실전 팁
DP 문제는 "점화식"을 세우는 게 99%입니다. 처음엔 완전 탐색(DFS)으로 접근해 보고, 중복 호출이 많다 싶으면 DP를 적용하는 흐름이 좋습니다. "계단을 오르는 방법의 수", "가장 긴 증가하는 부분 수열(LIS)", "배낭 문제(Knapsack)" 등이 대표적입니다.