동적 프로그래밍 실전 예제 완벽 가이드

1. 알고리즘 소개 및 개념

동적 프로그래밍 실전 예제를 통해 복잡한 문제를 효율적으로 해결하는 방법을 배워보겠습니다. 동적 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 하위 문제로 나누고, 한 번 계산한 결과를 저장하여 재사용함으로써 중복 계산을 방지하는 알고리즘 설계 기법입니다. 이 기법은 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)라는 두 가지 핵심 특성을 가진 문제에 적용됩니다. 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack) 등이 대표적인 동적 프로그래밍 문제입니다. 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 두 가지 접근 방식으로 구현할 수 있으며, 각각 Top-Down과 Bottom-Up 방식에 해당합니다.

2. 동작 원리 상세 설명

동적 프로그래밍의 동작 원리는 크게 두 단계로 나뉩니다. 첫째, 문제를 더 작은 하위 문제로 분해합니다. 예를 들어 n번째 계단까지 올라가는 방법의 수를 구하는 문제는 (n-1)번째와 (n-2)번째 계단까지 올라가는 방법의 합으로 표현됩니다. 둘째, 하위 문제의 해를 메모리에 저장하여 같은 문제가 다시 등장할 때 저장된 값을 재사용합니다. Top-Down 방식인 메모이제이션은 재귀 함수를 사용하며, 필요한 하위 문제만 계산합니다. 함수 호출 시 먼저 캐시를 확인하고, 계산된 값이 있으면 반환하고 없으면 계산 후 저장합니다. Bottom-Up 방식인 타뷸레이션은 반복문을 사용하여 가장 작은 문제부터 순차적으로 해결하며 배열에 결과를 저장합니다. 이 방식은 재귀 호출 스택 오버플로우 위험이 없고 일반적으로 더 빠릅니다. 상태 전이 방정식(State Transition Equation)을 정확히 정의하는 것이 핵심이며, 초기 조건(Base Case)을 올바르게 설정해야 합니다.

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

동적 프로그래밍의 복잡도는 하위 문제의 개수와 각 문제를 푸는 시간에 의해 결정됩니다. 1차원 DP의 경우 일반적으로 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 예를 들어 피보나치 수열을 순수 재귀로 구현하면 O(2^n)의 지수 시간이 걸리지만, DP를 적용하면 O(n)으로 극적으로 개선됩니다. 2차원 DP 문제(예: LCS, 편집 거리)는 시간 복잡도 O(n×m), 공간 복잡도 O(n×m)을 가집니다. 배낭 문제의 경우 물건 개수 n과 배낭 용량 W에 대해 O(n×W)의 시간과 공간 복잡도를 갖습니다. 공간 복잡도는 슬라이딩 윈도우 기법이나 상태 압축을 통해 최적화할 수 있습니다. 예를 들어 2차원 배열을 1차원으로 줄이면 O(n×m)에서 O(m)으로 개선 가능합니다. 메모이제이션은 실제로 방문하는 상태만 저장하므로 최악의 경우보다 공간을 덜 사용할 수 있습니다.

4. 단계별 구현 과정

예제 1: 계단 오르기 (Bottom-Up 방식)

한 번에 1계단 또는 2계단씩 올라갈 수 있을 때, n번째 계단까지 도달하는 방법의 수를 구합니다.

function climbStairs(n) {
  // 1단계: Base case 처리
  if (n <= 2) return n;
  
  // 2단계: DP 테이블 초기화
  const dp = new Array(n + 1);
  dp[1] = 1;  // 1계단: 1가지 방법
  dp[2] = 2;  // 2계단: 2가지 방법
  
  // 3단계: 상태 전이 방정식 적용
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

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

예제 2: 최장 증가 부분 수열 (LIS)

주어진 수열에서 순서를 유지하면서 크기가 점진적으로 증가하는 가장 긴 부분 수열의 길이를 찾습니다.

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  
  // 1단계: DP 배열 초기화 (각 위치에서 LIS 길이)
  const dp = new Array(nums.length).fill(1);
  let maxLength = 1;
  
  // 2단계: 각 위치마다 이전 원소들과 비교
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // 현재 원소가 이전 원소보다 크면 연결 가능
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLength = Math.max(maxLength, dp[i]);
  }
  
  return maxLength;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4

예제 3: 0-1 배낭 문제 (Knapsack)

무게와 가치가 있는 물건들을 제한된 용량의 배낭에 넣어 최대 가치를 구합니다.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w]: i번째 물건까지 고려, 용량 w일 때 최대 가치
  const dp = Array.from({ length: n + 1 }, 
    () => new Array(capacity + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // 현재 물건을 넣을 수 없는 경우
      if (weights[i - 1] > w) {
        dp[i][w] = dp[i - 1][w];
      } else {
        // 넣는 경우와 안 넣는 경우 중 최대값
        dp[i][w] = Math.max(
          dp[i - 1][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];
console.log(knapsack(weights, values, 8)); // 10

예제 4: 메모이제이션 (Top-Down)

function fibMemo(n, memo = {}) {
  // 캐시 확인
  if (n in memo) return memo[n];
  
  // Base case
  if (n <= 2) return 1;
  
  // 계산 후 저장
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(50)); // 12586269025

5. 최적화 방법

공간 최적화: 많은 DP 문제에서 현재 상태가 직전 몇 개의 상태에만 의존하는 경우, 전체 배열 대신 필요한 변수만 유지하여 공간을 절약할 수 있습니다. 피보나치의 경우 O(n)을 O(1)로 줄일 수 있습니다.

function fibOptimized(n) {
  if (n <= 2) return 1;
  let prev = 1, curr = 1;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

상태 압축: 2차원 DP를 1차원으로 줄이는 기법으로, 배낭 문제에서 용량 차원만 유지하여 메모리를 크게 절약합니다. 계산 순서 최적화: 불필요한 상태 계산을 건너뛰거나, 계산 순서를 조정하여 캐시 효율성을 높입니다. 비트마스킹: 상태를 비트로 표현하여 집합 연산을 빠르게 수행하고 메모리를 절약합니다.

6. 실전 활용 예제

동적 프로그래밍 실전 예제는 코딩 테스트에서 자주 출제됩니다. 최소 편집 거리: 문자열 유사도 측정, 맞춤법 검사기에 활용됩니다. 최장 공통 부분 수열: Git의 diff 알고리즘, DNA 서열 비교에 사용됩니다. 동전 거스름돈: 최소 개수의 동전으로 거스름돈을 만드는 문제로 금융 시스템에 적용됩니다. 주식 매매: 최대 수익을 내는 매매 전략을 찾는 문제입니다. 행렬 연쇄 곱셈: 최소 연산 횟수로 행렬을 곱하는 순서를 결정합니다. 실무에서는 경로 탐색, 자원 할당, 일정 관리 등 다양한 최적화 문제에 동적 프로그래밍이 활용됩니다.