다이나믹 프로그래밍(DP): 중복 계산 제거

프롤로그 - Dynamic Programming이라는 위압감

처음 "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의 두 가지 접근: Top-Down vs Bottom-Up

나는 메모이제이션이 DP의 전부인 줄 알았는데, 또 다른 방식이 있었다. Bottom-Up 방식이다.

Top-Down (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];
}

장점: 코드가 직관적이다. 재귀의 정의 그대로 쓸 수 있다. 단점: 재귀 호출 스택이 쌓이므로 n이 너무 크면 스택 오버플로우가 날 수 있다.

Bottom-Up (Tabulation)

작은 것부터 차근차근 계산해서 쌓아 올리는 방식이다. 반복문을 쓴다.

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로 풀 수 있는 건 아니다. DP를 쓸 수 있는 문제는 두 가지 특징이 있다.

1. 중복되는 부분 문제 (Overlapping Subproblems)

큰 문제를 쪼갰을 때, 같은 작은 문제가 여러 번 등장해야 한다. 피보나치가 대표적이다. fib(5)를 풀려면 fib(3)이 여러 번 필요하다.

만약 작은 문제들이 모두 독립적이면, 그냥 Divide & Conquer(분할 정복)를 쓰면 된다. 병합 정렬이 좋은 예다. 배열을 반으로 나눴을 때 왼쪽과 오른쪽은 서로 겹치지 않는다. 그래서 병합 정렬은 DP가 아니다.

2. 최적 부분 구조 (Optimal Substructure)

작은 문제의 최적해를 합치면 큰 문제의 최적해가 되어야 한다. 예를 들어, 최단 경로 문제에서 A → C의 최단 경로가 A → B → C라면, A → B도 최단 경로여야 한다. 만약 A → B가 최단 경로가 아니라면, A → C도 최단 경로가 아니게 된다.

이 두 가지가 충족되면, DP로 풀 수 있다.

구체적인 예제 - 동전 거스름돈 문제 (Coin Change)

피보나치만으로는 성이 안 차서, 동전 거스름돈 문제를 풀어봤다. 이 문제는 실제로도 자주 나오는 전형적인 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]를 구하려면:

• 동전 1을 쓴다면: dp[31] + 1
• 동전 5를 쓴다면: dp[27] + 1
• 동전 10을 쓴다면: dp[22] + 1
• 동전 25를 쓴다면: dp[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는 "상태"를 정의하고, "상태 전이"를 점화식으로 표현하는 것이다. 이 틀만 잡히면, 복잡한 문제도 풀린다.

또 다른 예제 - 최장 공통 부분 수열 (LCS)

최장 공통 부분 수열(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는 단순히 숫자 계산만 하는 게 아니라, 상태의 관계를 다루는 도구였다.

0/1 배낭 문제 (Knapsack)

배낭 문제는 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

배낭 문제는 실생활에도 많이 쓰인다. 예산 내에서 프로젝트 선택, 서버 자원 할당, 광고 슬롯 배정 등이 모두 배낭 문제의 변형이다.

공간 최적화: Rolling Array

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 vs Greedy vs Divide & Conquer

DP를 공부하면서, 비슷해 보이는 다른 기법들과의 차이가 궁금했다.

Greedy (탐욕법)

매 순간 최선의 선택을 한다. 동전 거스름돈 문제에서 항상 가장 큰 동전을 쓰는 게 Greedy다. 하지만 동전이 [1, 3, 4]이고 금액이 6일 때, Greedy는 4 + 1 + 1 = 3개를 선택하지만, 정답은 3 + 3 = 2개다. Greedy는 항상 최적해를 보장하지 않는다. DP는 모든 경우를 고려해서 최적해를 찾는다.

Divide & Conquer (분할 정복)

문제를 독립적인 부분 문제로 나눠서 각각 해결한다. 병합 정렬, 퀵 정렬이 대표적이다. DP와 다른 점은 부분 문제가 겹치지 않는다는 것이다. Divide & Conquer는 각 부분 문제를 한 번씩만 푼다. DP는 겹치는 부분 문제를 여러 번 풀어야 하는데, 캐싱으로 최적화한다.

정리:

• Greedy: 빠르지만 최적해 보장 안 됨. 특정 조건에서만 작동.
• Divide & Conquer: 부분 문제가 독립적일 때. 캐싱 불필요.
• DP: 부분 문제가 겹칠 때. 캐싱으로 최적화.

DP 문제를 알아보는 법

나는 문제를 보고 "이게 DP 문제인가?"를 판단하는 감을 기르고 싶었다. 몇 가지 패턴을 정리해봤다.

신호 1 - "최대", "최소", "최적"이라는 단어

"최소 비용", "최대 이익", "최적 경로" 같은 표현이 나오면 DP를 의심해봐야 한다.

신호 2 - "몇 가지 방법"

"N을 만드는 경우의 수", "배열을 나누는 방법의 수" 같은 문제도 DP일 가능성이 크다.

신호 3 - 작은 문제를 여러 번 풀게 되는 구조

재귀로 짰는데 중복 계산이 보이면 DP다.

신호 4 - 문제의 제약이 작음 (n <= 1000 정도)

DP는 보통 O(n^2) ~ O(n^3) 정도의 복잡도를 가진다. 제약이 작으면 DP로 풀 수 있다는 힌트다.

마치며 - DP는 "기억"의 힘

나는 DP를 공부하면서 깨달은 게 있다. DP는 복잡한 알고리즘이 아니라, "과거를 기억하는 힘"이었다. 똑같은 실수를 반복하지 않고, 한 번 배운 걸 계속 활용하는 것. 인생도 비슷하다. 같은 문제를 겪으면 이전 경험을 떠올려서 더 나은 선택을 한다. DP는 컴퓨터에게 이 능력을 주는 것이다.

처음엔 "Dynamic Programming"이라는 이름에 쫄았지만, 이제는 이 이름이 오히려 친근하다. 거창한 이름 뒤에 숨은 단순한 진리를 발견했기 때문이다.

결국 DP는 이거였다: 이미 푼 거 다시 풀지 마라. 메모해두고 꺼내 쓰자. 그게 전부다.