알고리즘 문제를 풀다 보면 "이 문제는 DP로 풀어야 합니다"라는 해설을 자주 접하게 됩니다. 많은 입문자들이 여기서 좌절합니다. 이름부터가 '동적 계획법(Dynamic Programming)'이라니, 뭔가 굉장히 어렵고 역동적인 기술이 필요할 것 같기 때문입니다. 하지만 이 이름은 1950년대 리처드 벨만이라는 수학자가 단순히 '멋있어 보여서' 붙인 이름일 뿐, 실제 내용은 "기억하기(Memorization)"에 가깝습니다. 오늘은 복잡한 계산을 획기적으로 줄여주는 효율성의 끝판왕, DP의 원리를 피보나치 수열을 통해 아주 쉽게 이해해 보겠습니다.
1. 동적 계획법(DP)이란?
동적 계획법은 "한 번 푼 문제는 답을 적어놓고, 다시 풀지 않는다"는 단순한 철학에서 시작됩니다. 큰 문제를 작은 문제로 쪼개서 푸는 것은 '분할 정복'과 비슷하지만, DP의 핵심은 작은 문제들이 반복해서 나타난다(Overlapping Subproblems)는 점입니다. 이 반복되는 연산을 매번 다시 계산하는 비효율을 막기 위해, 계산 결과를 어딘가에 저장해 두었다가 재사용하는 기법을 사용합니다.
2. 왜 DP가 필요한가? (재귀 함수의 비효율)
가장 유명한 예시인 피보나치 수열을 예로 들어보겠습니다. 피보나치 수열은 `1, 1, 2, 3, 5, 8, 13...` 처럼 앞의 두 수를 더해 다음 수를 만드는 수열입니다. 점화식으로는 $F(n) = F(n-1) + F(n-2)$로 표현됩니다.
이를 단순 재귀 함수로 구현하면 다음과 같습니다.
function fib(n) {
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
코드는 간결하지만 치명적인 문제가 있습니다. 만약 `fib(5)`를 구하려면 어떻게 될까요? 1. `fib(5)`는 `fib(4)`와 `fib(3)`을 부릅니다. 2. `fib(4)`는 다시 `fib(3)`과 `fib(2)`를 부릅니다. 3. 여기서 벌써 `fib(3)`이 중복 호출되었습니다. 숫자가 커지면 이 중복은 기하급수적으로 늘어나, `fib(100)` 정도만 되어도 우주가 멸망할 때까지 계산이 끝나지 않는 O(2^n)의 시간이 걸립니다.
3. DP의 해결책: 메모이제이션 (Memoization)
이 비효율을 해결하는 방법은 간단합니다. 종이(배열)를 한 장 준비해서 계산한 값을 적어두는 것입니다. 이를 메모이제이션이라고 합니다.
3-1. 동작 과정 (Top-Down 방식)
- `fib(5)`를 계산해야 합니다. 메모장을 봅니다. 값이 없네요.
- 계산을 위해 `fib(4)`와 `fib(3)`이 필요합니다.
- ... 쭉 내려가서 `fib(3)`의 답이 '2'라는 것을 알게 되었습니다.
- 이 '2'라는 값을 메모장에 적어둡니다. (`memo[3] = 2`)
- 나중에 다른 곳에서 또 `fib(3)`을 부르면? 계산하지 않고 메모장에 적힌 '2'를 바로 반환합니다.
이렇게 하면 모든 숫자는 딱 한 번씩만 계산되므로, 시간 복잡도가 O(N)으로 획기적으로 줄어듭니다. `fib(100)`도 0.0001초 만에 구할 수 있게 됩니다.
4. DP 구현의 두 가지 스타일
DP를 구현하는 방법은 크게 두 가지가 있습니다.
- Top-Down (하향식): 큰 문제에서 시작해 작은 문제로 쪼개 내려가는 방식입니다. 재귀 함수와 메모이제이션을 사용합니다. 직관적이지만 스택 오버플로우 위험이 있습니다.
- Bottom-Up (상향식): 가장 작은 문제부터 차근차근 답을 쌓아 올려 큰 문제를 해결하는 방식입니다. 단순 반복문(for)을 사용합니다. `dp[1]=1`, `dp[2]=1`부터 시작해 `dp[3]`, `dp[4]`를 채워 나갑니다. 실무나 코딩 테스트에서는 함수 호출 비용이 없는 이 방식을 더 선호합니다.
1. 동적 계획법(DP)은 반복되는 부분 문제의 답을 저장(Memoization)하여 재사용하는 알고리즘입니다.
2. 중복 계산이 많은 재귀 함수의 시간 복잡도를 지수 시간($O(2^n)$)에서 선형 시간($O(n)$)으로 줄여줍니다.
3. 점화식을 세우고, Bottom-Up(반복문) 방식으로 구현하는 것이 가장 효율적입니다.