동적 프로그래밍 실전 예제 – 개념부터 구현까지 완벽 마스터

1. 알고리즘 소개 및 개념

동적 프로그래밍 실전 예제를 통해 알고리즘의 핵심 개념을 마스터해보겠습니다. 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하는 최적화 기법입니다. 이 알고리즘의 핵심은 한 번 계산한 결과를 메모리에 저장하여 중복 계산을 방지하는 메모이제이션(Memoization)과 상향식 접근법인 타뷸레이션(Tabulation)입니다. 동적 프로그래밍은 피보나치 수열, 최단 경로 찾기, 배낭 문제, 최장 공통 부분 수열(LCS) 등 다양한 최적화 문제에서 활용됩니다. 특히 코딩 테스트와 실무에서 자주 등장하는 만큼, 반드시 숙지해야 할 필수 알고리즘입니다.

2. 동작 원리 상세 설명

동적 프로그래밍은 두 가지 핵심 속성을 가진 문제에 적용됩니다. 첫째, 최적 부분 구조(Optimal Substructure)는 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다는 특성입니다. 둘째, 중복되는 부분 문제(Overlapping Subproblems)는 동일한 작은 문제들이 반복적으로 나타나는 특성을 의미합니다. 동적 프로그래밍은 크게 두 가지 방식으로 구현됩니다. 하향식(Top-down) 접근법은 재귀를 사용하며 메모이제이션으로 결과를 캐싱합니다. 상향식(Bottom-up) 접근법은 반복문을 사용하여 작은 문제부터 순차적으로 해결하며 테이블에 결과를 저장합니다. 예를 들어, 피보나치 수열에서 F(5)를 계산할 때 F(3)이 여러 번 계산되는 비효율을 DP로 해결할 수 있습니다. 이미 계산된 F(3)의 값을 저장해두고 재사용함으로써 지수 시간 복잡도를 선형 시간으로 개선합니다.

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

동적 프로그래밍의 복잡도는 문제의 특성에 따라 다르지만, 일반적인 패턴을 분석할 수 있습니다. 시간 복잡도는 부분 문제의 개수와 각 부분 문제를 푸는 데 걸리는 시간의 곱으로 결정됩니다. 피보나치 수열의 경우, 순수 재귀는 O(2^n)이지만 DP를 적용하면 O(n)으로 개선됩니다. 2차원 DP 배열을 사용하는 최장 공통 부분 수열 문제는 O(m×n)의 시간 복잡도를 가집니다. 공간 복잡도는 메모이제이션 테이블의 크기에 의해 결정됩니다. 1차원 DP는 O(n), 2차원 DP는 O(m×n)의 공간을 사용합니다. 하지만 슬라이딩 윈도우 기법을 사용하면 2차원 문제도 O(min(m,n))으로 공간을 최적화할 수 있습니다. 메모이제이션은 재귀 호출 스택 공간도 사용하므로 깊이가 깊은 경우 스택 오버플로우에 주의해야 합니다.

4. 단계별 구현 과정

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

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

// 1. 순수 재귀 방식 (비효율적 - O(2^n))
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// 2. 메모이제이션 (Top-down DP - O(n))
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// 3. 타뷸레이션 (Bottom-up DP - O(n))
function fibTabulation(n) {
  if (n <= 1) return n;
  
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

// 4. 공간 최적화 (O(1) 공간)
function fibOptimized(n) {
  if (n <= 1) return n;
  
  let prev = 0, curr = 1;
  
  for (let i = 2; i <= n; i++) {
    const temp = curr;
    curr = prev + curr;
    prev = temp;
  }
  
  return curr;
}

console.log(fibOptimized(10)); // 55

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

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w]: i번째 아이템까지 고려했을 때, 용량 w에서의 최대 가치
  const dp = Array(n + 1).fill(null)
    .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) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  
  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(null)
    .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];
}

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

예제 4: 계단 오르기 문제

// 한 번에 1칸 또는 2칸씩 오를 수 있을 때, n번째 계단까지 가는 방법의 수
function climbStairs(n) {
  if (n <= 2) return n;
  
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  
  for (let i = 3; i <= n; i++) {
    // 현재 계단은 (i-1)번째에서 1칸 오르거나, (i-2)번째에서 2칸 오르는 방법
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

console.log(climbStairs(5)); // 8

5. 최적화 방법

동적 프로그래밍 실전 예제에서 성능을 극대화하는 최적화 기법들을 소개합니다. 공간 복잡도 최적화: 2차원 DP 배열이 필요한 경우, 실제로는 이전 행만 참조한다면 1차원 배열로 축소할 수 있습니다. 배낭 문제에서 dp[capacity + 1] 크기의 1차원 배열만 사용하고 역순으로 순회하면 O(n)의 공간으로 해결됩니다. 상태 압축: 비트마스킹을 활용하여 여러 상태를 하나의 정수로 표현하면 메모리를 절약할 수 있습니다. 조기 종료: 불가능한 상태를 사전에 체크하여 불필요한 계산을 건너뛰면 실행 시간을 단축할 수 있습니다. Bottom-up 선호: 재귀 호출 오버헤드를 피하고 캐시 친화적인 순차 접근으로 성능을 개선할 수 있습니다. 희소 테이블: 대부분의 값이 0인 경우 Map이나 객체를 사용하여 실제 값만 저장하면 메모리를 크게 절약할 수 있습니다.

6. 실전 활용 예제

동적 프로그래밍은 실무와 코딩 테스트에서 광범위하게 활용됩니다. 최단 경로 알고리즘: 플로이드-워셜 알고리즘은 DP로 모든 정점 쌍 간의 최단 경로를 O(n³)에 찾습니다. 문자열 편집 거리: 레벤슈타인 거리는 검색 엔진의 오타 수정, DNA 서열 비교 등에 사용됩니다. 최적 행렬 곱셈 순서: 대규모 행렬 연산의 연산량을 최소화합니다. 주식 거래 전략: 최대 이익을 내는 매수/매도 시점을 결정합니다. 리소스 할당 최적화: 제한된 리소스를 여러 작업에 최적으로 배분합니다. 이러한 동적 프로그래밍 실전 예제들을 마스터하면 복잡한 최적화 문제를 효율적으로 해결할 수 있습니다.