
다이나믹 프로그래밍(DP): 중복 계산 제거
이름이 멋있어서 쫄았나요? 사실은 '기억하기(Memoization)'일 뿐입니다. 피보나치 수열을 예제로 DP의 마법을 체험해봅니다.

이름이 멋있어서 쫄았나요? 사실은 '기억하기(Memoization)'일 뿐입니다. 피보나치 수열을 예제로 DP의 마법을 체험해봅니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

처음 "Dynamic Programming"이라는 용어를 들었을 때, 나는 정말 겁먹었다. CS 전공자들이 입만 열면 "DP로 풀면 되죠"라고 말하는데, 도대체 이게 뭔지 감도 안 잡혔다. 뭔가 고차원적이고, 엄청 복잡한 수학 공식이 필요할 것 같았다. 하지만 막상 들여다보니, 이 겁나게 멋진 이름의 정체는 아주 단순했다.
"계산한 거 적어두고, 나중에 또 쓰기"그게 전부였다. 초등학교 구구단 외우듯이, 한 번 계산한 결과를 메모해뒀다가 다시 쓰는 것. 이렇게 간단한 개념인데 왜 이렇게 거창한 이름을 붙였을까? 이유는 웃기다. Richard Bellman이라는 수학자가 1950년대에 연구비를 따내기 위해 일부러 멋있게 지은 이름이라고 한다. "Programming"도 프로그래밍 코드가 아니라 "계획 세우기"라는 뜻이었다. 결국 마케팅이었던 셈이다.
나는 이 사실을 알고 나서야 DP를 편하게 받아들일 수 있었다. 이름에 쫄 필요 없다. 그냥 똑똑한 재귀일 뿐이다.
DP를 처음 이해하기 위해, 나는 피보나치 수열을 풀어봤다. 피보나치는 간단하다. F(n) = F(n-1) + F(n-2), 이전 두 개 더하면 된다. 재귀로 짜면 딱 정의 그대로다.
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
console.log(fib(10)); // 55
완벽해 보였다. 하지만 fib(40)을 실행하는 순간 컴퓨터가 멈췄다. 아니, 멈춘 건 아니고 몇 초간 계속 계산 중이었다. 왜 이렇게 느릴까?
그림을 그려보니 답이 나왔다. fib(5)를 계산하려면:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ...
fib(3)이 두 번, fib(2)는 세 번, fib(1)은 다섯 번 계산된다. 완전히 중복 계산 지옥이다. 이 트리는 지수적으로 커진다. 시간 복잡도가 O(2^n)이다. n이 40이면 대략 1조 번 계산한다. 내 맥북이 불타는 소리가 들렸다.
"똑같은 거 왜 계속 다시 계산해?" 이 질문이 DP의 시작이었다.
답은 너무 단순했다. 계산한 걸 적어두면 된다. fib(3)을 한 번 계산했으면, 그 값을 어딘가에 적어두고, 나중에 fib(3)이 또 필요할 때 다시 계산하지 말고 적어둔 걸 보면 된다. 이게 바로 Memoization(메모이제이션)이다.
const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n]) return memo[n]; // 이미 계산했으면 바로 리턴
memo[n] = fib(n - 1) + fib(n - 2); // 계산하고 메모에 저장
return memo[n];
}
console.log(fib(40)); // 102334155, 즉시 계산됨
이 코드로 fib(40)을 돌리니까 0.001초도 안 걸렸다. 마법 같았다. 지수 시간에서 선형 시간 O(n)으로 줄어든 것이다. 각 숫자를 딱 한 번씩만 계산하기 때문이다.
이걸 이해하고 나서 나는 DP를 이렇게 정의했다:
"이미 푼 문제는 다시 풀지 마라. 답을 어딘가에 적어두고 꺼내 쓰자."은행에서 이자를 계산할 때, 매번 처음부터 다시 계산하지 않고 전 달 잔액을 보고 더하는 것과 같은 원리다. 당연한 건데, 재귀 코드로 짜면 자꾸 잊어버리게 된다.
나는 메모이제이션이 DP의 전부인 줄 알았는데, 또 다른 방식이 있었다. Bottom-Up 방식이다.
위에서부터 아래로 내려가는 방식이다. 재귀를 쓰되, 이미 계산한 값은 캐싱해둔다. 내가 위에서 쓴 피보나치가 이 방식이다.
const memo = {};
function fib(n) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
장점: 코드가 직관적이다. 재귀의 정의 그대로 쓸 수 있다.
단점: 재귀 호출 스택이 쌓이므로 n이 너무 크면 스택 오버플로우가 날 수 있다.
작은 것부터 차근차근 계산해서 쌓아 올리는 방식이다. 반복문을 쓴다.
function fib(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
장점: 재귀 오버헤드가 없고, 스택 오버플로우 걱정 없다. 보통 더 빠르다. 단점: 작은 문제부터 순서대로 다 채워야 해서, 어떤 문제는 코드가 덜 직관적일 수 있다.
나는 처음엔 Top-Down이 이해하기 쉬웠는데, 익숙해지니 Bottom-Up이 더 깔끔하게 느껴졌다. 문제마다 편한 방식을 선택하면 된다.
아무 문제나 DP로 풀 수 있는 건 아니다. DP를 쓸 수 있는 문제는 두 가지 특징이 있다.
큰 문제를 쪼갰을 때, 같은 작은 문제가 여러 번 등장해야 한다. 피보나치가 대표적이다. fib(5)를 풀려면 fib(3)이 여러 번 필요하다.
만약 작은 문제들이 모두 독립적이면, 그냥 Divide & Conquer(분할 정복)를 쓰면 된다. 병합 정렬이 좋은 예다. 배열을 반으로 나눴을 때 왼쪽과 오른쪽은 서로 겹치지 않는다. 그래서 병합 정렬은 DP가 아니다.
작은 문제의 최적해를 합치면 큰 문제의 최적해가 되어야 한다. 예를 들어, 최단 경로 문제에서 A → C의 최단 경로가 A → B → C라면, A → B도 최단 경로여야 한다. 만약 A → B가 최단 경로가 아니라면, A → C도 최단 경로가 아니게 된다.
이 두 가지가 충족되면, DP로 풀 수 있다.
피보나치만으로는 성이 안 차서, 동전 거스름돈 문제를 풀어봤다. 이 문제는 실제로도 자주 나오는 전형적인 DP 문제다.
문제: 동전 종류가 주어지고, 특정 금액을 만들 수 있는 최소 동전 개수를 구하라. 예를 들어 동전이 [1, 5, 10, 25]이고 금액이 32라면, 25 + 5 + 1 + 1 = 4개가 최소다.
dp[i]를 "금액 i를 만드는 데 필요한 최소 동전 개수"로 정의한다. 그러면:
dp[i] = min(dp[i - coin] + 1) for coin in coins
예를 들어 dp[32]를 구하려면:
dp[31] + 1dp[27] + 1dp[22] + 1dp[7] + 1이 중 최소값을 선택하면 된다.
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // 0원을 만드는 데는 동전 0개 필요
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 5, 10, 25], 32)); // 4
console.log(coinChange([2, 5], 3)); // -1 (불가능)
이 코드의 핵심은 점화식이다. dp[i]가 이전 상태 dp[i - coin]에 의존한다는 관계를 명확히 정의하고, 작은 것부터 차근차근 채워나간다. 시간 복잡도는 O(amount × coins.length)이다.
나는 이 문제를 풀면서 DP의 본질을 더 깊이 이해했다. DP는 "상태"를 정의하고, "상태 전이"를 점화식으로 표현하는 것이다. 이 틀만 잡히면, 복잡한 문제도 풀린다.
최장 공통 부분 수열(Longest Common Subsequence, LCS)은 두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제다. 예를 들어 "ABCBDAB"와 "BDCABA"의 LCS는 "BCBA" 또는 "BDAB"이다(길이 4).
dp[i][j]를 "첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자의 LCS 길이"로 정의한다. 점화식은:
if (str1[i-1] === str2[j-1]):
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
글자가 같으면 이전 상태에서 +1, 다르면 둘 중 더 긴 쪽을 선택한다.
function lcs(str1, str2) {
const m = str1.length;
const n = str2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
console.log(lcs("ABCBDAB", "BDCABA")); // 4
이 문제는 2차원 DP의 대표 예제다. dp 테이블을 채워나가면서 최종 답을 구한다. 시간 복잡도는 O(m × n)이다.
나는 이 문제를 풀면서 DP가 문자열, 배열, 그래프 등 다양한 영역에 적용될 수 있다는 걸 깨달았다. DP는 단순히 숫자 계산만 하는 게 아니라, 상태의 관계를 다루는 도구였다.
배낭 문제는 DP의 꽃이다. 무게 제한이 있는 배낭에 가치 있는 물건들을 넣을 때, 최대 가치를 구하는 문제다.
문제: 각 물건은 무게와 가치가 있고, 배낭 용량은 W다. 각 물건은 한 번만 넣을 수 있다(0/1 배낭).
dp[i][w]를 "앞 i개 물건을 고려했을 때, 무게 w 이하로 담을 수 있는 최대 가치"로 정의한다. 점화식은:
if (weight[i] <= w):
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
else:
dp[i][w] = dp[i-1][w]
물건을 넣거나 안 넣거나 둘 중 최대값을 선택한다.
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(knapsack(weights, values, capacity)); // 10
배낭 문제는 실생활에도 많이 쓰인다. 예산 내에서 프로젝트 선택, 서버 자원 할당, 광고 슬롯 배정 등이 모두 배낭 문제의 변형이다.
DP 테이블이 커지면 메모리가 문제가 될 수 있다. 하지만 많은 DP 문제는 이전 상태만 필요하다. 예를 들어 피보나치는 dp[i-1]과 dp[i-2]만 필요하다. 전체 배열을 유지할 필요가 없다.
function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0;
let prev1 = 1;
for (let i = 2; i <= n; i++) {
let current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
이렇게 하면 공간 복잡도가 O(n)에서 O(1)로 줄어든다. 배낭 문제도 비슷하게 1차원 배열로 최적화할 수 있다.
나는 이 기법을 보고 "DP는 단순히 캐싱이 아니라, 상태 관리의 예술이구나"라고 느꼈다.
DP를 공부하면서, 비슷해 보이는 다른 기법들과의 차이가 궁금했다.
매 순간 최선의 선택을 한다. 동전 거스름돈 문제에서 항상 가장 큰 동전을 쓰는 게 Greedy다. 하지만 동전이 [1, 3, 4]이고 금액이 6일 때, Greedy는 4 + 1 + 1 = 3개를 선택하지만, 정답은 3 + 3 = 2개다. Greedy는 항상 최적해를 보장하지 않는다. DP는 모든 경우를 고려해서 최적해를 찾는다.
문제를 독립적인 부분 문제로 나눠서 각각 해결한다. 병합 정렬, 퀵 정렬이 대표적이다. DP와 다른 점은 부분 문제가 겹치지 않는다는 것이다. Divide & Conquer는 각 부분 문제를 한 번씩만 푼다. DP는 겹치는 부분 문제를 여러 번 풀어야 하는데, 캐싱으로 최적화한다.
정리:
나는 문제를 보고 "이게 DP 문제인가?"를 판단하는 감을 기르고 싶었다. 몇 가지 패턴을 정리해봤다.
"최소 비용", "최대 이익", "최적 경로" 같은 표현이 나오면 DP를 의심해봐야 한다.
"N을 만드는 경우의 수", "배열을 나누는 방법의 수" 같은 문제도 DP일 가능성이 크다.
재귀로 짰는데 중복 계산이 보이면 DP다.
n <= 1000 정도)DP는 보통 O(n^2) ~ O(n^3) 정도의 복잡도를 가진다. 제약이 작으면 DP로 풀 수 있다는 힌트다.
나는 DP를 공부하면서 깨달은 게 있다. DP는 복잡한 알고리즘이 아니라, "과거를 기억하는 힘"이었다. 똑같은 실수를 반복하지 않고, 한 번 배운 걸 계속 활용하는 것. 인생도 비슷하다. 같은 문제를 겪으면 이전 경험을 떠올려서 더 나은 선택을 한다. DP는 컴퓨터에게 이 능력을 주는 것이다.
처음엔 "Dynamic Programming"이라는 이름에 쫄았지만, 이제는 이 이름이 오히려 친근하다. 거창한 이름 뒤에 숨은 단순한 진리를 발견했기 때문이다.
결국 DP는 이거였다: 이미 푼 거 다시 풀지 마라. 메모해두고 꺼내 쓰자. 그게 전부다.