Blog

1. 알고리즘 소개 및 개념

동적 프로그래밍 실전 예제는 복잡한 문제를 작은 하위 문제로 나누어 해결하는 효율적인 알고리즘 기법입니다. 동적 프로그래밍(Dynamic Programming, DP)은 중복되는 부분 문제의 결과를 저장하여 재사용함으로써 계산 시간을 획기적으로 단축시킵니다. 이 기법은 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack), 최단 경로 문제 등 다양한 실전 문제에서 핵심적으로 활용됩니다. 동적 프로그래밍은 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 두 가지 접근 방식으로 구현할 수 있으며, 각각 Top-down과 Bottom-up 방식으로 문제를 해결합니다.

2. 동작 원리 상세 설명

동적 프로그래밍의 핵심 원리는 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems) 두 가지 특성을 활용하는 것입니다. 최적 부분 구조란 전체 문제의 최적해가 부분 문제들의 최적해로 구성된다는 의미입니다. 중복되는 부분 문제는 동일한 계산이 여러 번 반복되는 특성을 말합니다.

메모이제이션 방식은 재귀 호출을 사용하며, 한 번 계산한 결과를 캐시(배열이나 해시맵)에 저장합니다. 같은 입력값으로 다시 호출될 때 저장된 값을 반환하여 중복 계산을 방지합니다. 타뷸레이션 방식은 반복문을 사용하여 작은 문제부터 순차적으로 해결하며 테이블을 채워나갑니다. 이미 계산된 값들을 참조하여 더 큰 문제를 해결하는 방식으로, 재귀 호출의 오버헤드가 없어 일반적으로 더 효율적입니다. 두 방식 모두 시간 복잡도는 동일하지만, 구현 복잡도와 공간 활용 측면에서 차이가 있습니다.

3. 시간/공간 복잡도 분석

동적 프로그래밍을 적용하면 지수 시간 복잡도를 다항 시간으로 개선할 수 있습니다. 예를 들어, 피보나치 수열을 순수 재귀로 구현하면 O(2^n)의 시간이 소요되지만, 동적 프로그래밍을 적용하면 O(n)으로 단축됩니다.

시간 복잡도: 일반적으로 부분 문제의 개수 × 각 문제를 푸는 시간으로 계산됩니다. 대부분의 1차원 DP는 O(n), 2차원 DP는 O(n²)의 시간 복잡도를 갖습니다. LCS 문제의 경우 두 문자열의 길이를 m, n이라 할 때 O(m×n)입니다.

공간 복잡도: 메모이제이션은 재귀 스택과 캐시 공간이 필요하므로 O(n) 이상의 공간이 필요합니다. 타뷸레이션은 DP 테이블만 필요하며, 경우에 따라 슬라이딩 윈도우 기법으로 O(1)까지 최적화할 수 있습니다. 예를 들어 피보나치는 이전 두 값만 필요하므로 상수 공간으로 최적화 가능합니다.

4. 단계별 구현 과정

동적 프로그래밍 실전 예제로 세 가지 대표적인 문제를 구현해보겠습니다.

예제 1: 피보나치 수열 (기본)

// 메모이제이션 방식 (Top-down)
function fibonacciMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

// 타뷸레이션 방식 (Bottom-up)
function fibonacciTable(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];
}

// 공간 최적화 버전
function fibonacciOptimized(n) {
  if (n <= 1) return n;
  
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

console.log(fibonacciMemo(10));      // 55
console.log(fibonacciTable(10));     // 55
console.log(fibonacciOptimized(10)); // 55

예제 2: 배낭 문제 (0/1 Knapsack)

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w] = i번째까지 물건을 고려했을 때, 용량 w에서의 최대 가치
  const dp = Array(n + 1).fill(0).map(() => Array(capacity + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // 현재 물건을 넣지 않는 경우
      dp[i][w] = dp[i - 1][w];
      
      // 현재 물건을 넣을 수 있는 경우
      if (weights[i - 1] <= w) {
        const valueWithCurrent = dp[i - 1][w - weights[i - 1]] + values[i - 1];
        dp[i][w] = Math.max(dp[i][w], valueWithCurrent);
      }
    }
  }
  
  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

예제 3: 최장 공통 부분 수열 (LCS)

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        // 문자가 같으면 이전 대각선 값 + 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];
}

// LCS 문자열 복원
function getLCSString(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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]);
      }
    }
  }
  
  // 역추적으로 LCS 문자열 구하기
  let lcs = '';
  let i = m, j = n;
  while (i > 0 && j > 0) {
    if (text1[i - 1] === text2[j - 1]) {
      lcs = text1[i - 1] + lcs;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  
  return lcs;
}

console.log(longestCommonSubsequence("abcde", "ace")); // 3
console.log(getLCSString("abcde", "ace"));             // "ace"

5. 최적화 방법

공간 복잡도 최적화: 2차원 DP 테이블에서 현재 행이 이전 행만 참조한다면, 두 개의 1차원 배열로 최적화할 수 있습니다. 피보나치처럼 고정된 개수의 이전 값만 필요하다면 변수 몇 개로 줄일 수 있습니다.

반복 제거: 불필요한 상태 전이를 건너뛰거나, 조기 종료 조건을 추가하여 계산량을 줄입니다. 예를 들어 배낭 문제에서 용량을 초과하는 경우를 미리 걸러낼 수 있습니다.

상태 압축: 비트마스킹을 활용하여 상태를 정수로 표현하면 메모리 사용량과 접근 속도를 개선할 수 있습니다. 특히 집합을 다루는 DP 문제에서 효과적입니다.

계산 순서 최적화: 캐시 효율성을 고려하여 배열 순회 순서를 조정하면 실행 속도가 향상됩니다. 메모리 접근 패턴을 지역성 있게 만드는 것이 중요합니다.

6. 실전 활용 예제

동적 프로그래밍 실전 예제는 코딩 테스트와 실무에서 광범위하게 활용됩니다. 알고리즘 문제: 백준, 프로그래머스, LeetCode의 중고급 문제 중 30% 이상이 DP 기법을 요구합니다. 계단 오르기, 편집 거리(Edit Distance), 동전 교환 문제 등이 대표적입니다.

실무 응용: 자원 할당 최적화, 경로 탐색(내비게이션), 문자열 유사도 계산(추천 시스템), 게임 AI(미니맥스 알고리즘), 재무 모델링(옵션 가격 계산) 등에서 동적 프로그래밍이 핵심 역할을 합니다. 특히 제약 조건 하에서 최적해를 찾아야 하는 모든 문제에 적용 가능합니다.