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

1. 알고리즘 소개 및 개념

동적 프로그래밍 실전 예제는 복잡한 문제를 작은 하위 문제로 나누어 해결하는 최적화 기법입니다. Dynamic Programming(DP)은 한 번 계산한 결과를 메모리에 저장하여 중복 계산을 방지하고, 전체 문제의 최적해를 효율적으로 구하는 알고리즘입니다. 이 기법은 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack), 최단 경로 문제 등 다양한 실전 문제에 적용됩니다. 동적 프로그래밍은 두 가지 핵심 특성을 가집니다: 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)입니다. 이러한 특성을 만족하는 문제는 DP로 효율적으로 해결할 수 있으며, 코딩테스트와 실무에서 자주 등장하는 핵심 알고리즘 패턴입니다.

2. 동작 원리 상세 설명

동적 프로그래밍은 크게 두 가지 접근 방식으로 구현됩니다. 첫 번째는 Top-down (메모이제이션) 방식으로, 재귀 함수를 사용하여 큰 문제를 작은 문제로 분해하고, 계산 결과를 캐시에 저장합니다. 이미 계산된 값은 캐시에서 바로 반환하여 중복 계산을 방지합니다. 두 번째는 Bottom-up (타뷸레이션) 방식으로, 반복문을 사용하여 가장 작은 부분 문제부터 순차적으로 해결하며 테이블을 채워나갑니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)라는 점화식을 찾으면, F(0)과 F(1)부터 시작하여 F(n)까지 순차적으로 계산할 수 있습니다. 각 단계에서 이전 단계의 결과를 활용하므로, 지수 시간 복잡도를 선형 시간 복잡도로 개선할 수 있습니다. DP 테이블은 1차원 배열, 2차원 배열, 또는 해시맵 형태로 구성되며, 문제의 상태(state)를 키로 사용하여 부분 문제의 해를 저장합니다. 상태 전이(state transition)는 점화식으로 표현되며, 이는 DP 구현의 핵심입니다.

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

시간 복잡도: 동적 프로그래밍의 시간 복잡도는 부분 문제의 개수 × 각 부분 문제를 푸는 시간으로 계산됩니다. 피보나치 수열의 경우, 부분 문제가 n개이고 각 문제를 O(1)에 해결하므로 O(n)입니다. 일반 재귀는 O(2^n)이지만 DP로 최적화하면 지수 시간을 다항 시간으로 단축할 수 있습니다. LCS 문제는 O(m×n), 배낭 문제는 O(n×W) (W는 배낭 용량)의 시간 복잡도를 가집니다. 공간 복잡도: DP 테이블을 저장하는 메모리가 필요하므로, 일반적으로 O(n) 또는 O(n×m)의 공간이 필요합니다. 하지만 슬라이딩 윈도우 기법을 사용하면 공간을 최적화할 수 있습니다. 예를 들어 피보나치에서 전체 배열 대신 최근 두 값만 유지하면 O(1) 공간으로 해결 가능합니다. Top-down 방식은 재귀 호출 스택으로 인해 추가 O(n) 공간이 필요할 수 있습니다.

4. 단계별 구현 과정

동적 프로그래밍 실전 예제를 단계별로 구현해보겠습니다. 대표적인 문제인 피보나치 수열, 최장 증가 부분 수열(LIS), 배낭 문제를 JavaScript로 구현합니다.

예제 1: 피보나치 수열 (Top-down)

// 메모이제이션을 사용한 피보나치
function fibonacci(n, memo = {}) {
  // 기저 사례
  if (n <= 1) return n;
  
  // 이미 계산된 값이 있으면 반환
  if (memo[n]) return memo[n];
  
  // 계산 후 메모에 저장
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(10)); // 55
console.log(fibonacci(50)); // 12586269025

예제 2: 피보나치 수열 (Bottom-up)

// 타뷸레이션을 사용한 피보나치
function fibonacciDP(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];
}

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

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

// 최장 증가 부분 수열의 길이 구하기
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  
  const dp = new Array(nums.length).fill(1);
  let maxLength = 1;
  
  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;
}

const arr = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(arr)); // 4 (부분수열: [2,3,7,101])

예제 4: 0-1 배낭 문제

// 0-1 배낭 문제 (각 물건을 0개 또는 1개만 선택)
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++) {
      // 현재 물건을 넣을 수 없는 경우
      if (weights[i - 1] > w) {
        dp[i][w] = dp[i - 1][w];
      } else {
        // 넣지 않는 경우 vs 넣는 경우 중 최댓값
        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];
const capacity = 8;
console.log(knapsack(weights, values, capacity)); // 10

5. 최적화 방법

공간 최적화: 많은 DP 문제에서 현재 상태가 직전 몇 개의 상태에만 의존하는 경우, 전체 테이블 대신 필요한 부분만 유지할 수 있습니다. 배낭 문제의 경우 2차원 배열을 1차원으로 압축하여 O(capacity) 공간으로 해결 가능합니다. 시간 최적화: 불필요한 상태 계산을 건너뛰거나, 더 효율적인 점화식을 찾아 상태 전이 횟수를 줄일 수 있습니다. LIS 문제는 이진 탐색을 활용하면 O(n log n)으로 개선됩니다. 메모리 접근 패턴 최적화: 캐시 친화적인 순회 방식을 사용하면 실제 실행 시간을 단축할 수 있습니다. Bottom-up 방식이 일반적으로 Top-down보다 캐시 효율이 좋습니다.

// 공간 최적화된 배낭 문제 (1차원 배열 사용)
function knapsackOptimized(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  
  for (let i = 0; i < weights.length; i++) {
    // 뒤에서부터 업데이트하여 같은 물건을 중복 선택 방지
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  
  return dp[capacity];
}

6. 실전 활용 예제

동적 프로그래밍 실전 예제는 다양한 코딩테스트와 실무 문제에 적용됩니다. 경로 찾기: 격자에서 왼쪽 위에서 오른쪽 아래로 가는 최소 비용 경로 계산 (LeetCode 64번). 문자열 편집 거리: 두 문자열을 같게 만드는 최소 편집 횟수 계산 (Levenshtein Distance). 주식 매매: 주식을 사고 팔아 최대 이익을 얻는 전략 수립. 동전 교환: 특정 금액을 만드는 최소 동전 개수 또는 경우의 수 계산. 이러한 문제들은 상태 정의와 점화식 도출이 핵심이며, 연습을 통해 패턴을 익히면 다양한 변형 문제도 해결할 수 있습니다. DP는 알고리즘 인터뷰에서 가장 자주 출제되는 주제 중 하나이므로, 기본 예제부터 시작하여 점진적으로 난이도를 높여가며 학습하는 것이 효과적입니다.