[자료구조] 동적계획법 (Dynamic Programming)

개발지식/자료구조

[자료구조] 동적계획법 (Dynamic Programming)

thinktank911 2025. 12. 2. 13:56

1. 동적계획법이란?

정의

복잡한 문제를 작은 부분 문제들로 나누어 해결하고, 그 결과를 저장(메모이제이션)하여 중복 계산을 방지하는 알고리즘 설계 기법

특징

최적 부분 구조: 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
중복 부분 문제: 같은 작은 문제가 여러 번 반복해서 나타남
메모리 사용: 계산 결과를 저장하므로 메모리를 더 사용하지만, 시간은 크게 절약

언제 사용하나?

최적화 문제 (최댓값, 최솟값, 최단거리 등)
경우의 수를 세는 문제
순서가 있는 선택 문제
분할 정복으로 풀 수 있지만 중복 계산이 많은 문제

2. 왜 필요한가?

일반 재귀의 문제점

피보나치 수열 예시:

fib(n) = fib(n-1) + fib(n-2)

fib(5) 호출 시:
         fib(5)
        /      \
    fib(4)    fib(3)
    /    \    /    \
 fib(3) fib(2) fib(2) fib(1)
 /   \
fib(2) fib(1)

문제점:

fib(3)이 2번 계산됨
fib(2)가 3번 계산됨
숫자가 커질수록 중복 계산이 기하급수적으로 증가

시간 복잡도 비교

방법	시간 복잡도	fib(40) 실행시간
일반 재귀	O(2^n)	약 1초
동적계획법	O(n)	0.001초 미만

결론: n=50만 되어도 일반 재귀는 수 시간이 걸리지만, DP는 순식간에 해결!

3. 핵심 개념

3-1. 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해를 부분 문제의 최적해로 구성할 수 있는 성질

예시: 최단 경로

A에서 C로 가는 최단 경로가 A→B→C라면
A→B 구간도 최단 경로여야 함
B→C 구간도 최단 경로여야 함

3-2. 중복 부분 문제 (Overlapping Subproblems)

동일한 작은 문제들이 여러 번 반복해서 계산되는 성질

예시:

피보나치: fib(n-1)과 fib(n-2) 모두 fib(n-3)을 계산
계단 오르기: 3층 가는 방법 = 2층 가는 방법 + 1층 가는 방법

3-3. 메모이제이션 (Memoization)

계산한 결과를 저장해두고, 같은 계산이 필요할 때 저장된 값을 재사용하는 기법

저장 방법:

배열 (Array): 인덱스로 접근 가능한 경우
객체/해시맵 (Object/Map): 복잡한 키가 필요한 경우

4. 구현 방법

4-1. 메모이제이션 (Top-Down, 하향식)

특징:

재귀 함수를 사용
큰 문제에서 시작해서 작은 문제로 내려감
필요한 부분 문제만 계산
구현이 직관적

구조:

function solve(n, memo = {}) {
  // 1. 기저 사례 (Base Case)
  if (n <= 1) return n;
  
  // 2. 이미 계산했는지 확인
  if (memo[n]) return memo[n];
  
  // 3. 계산하고 저장
  memo[n] = solve(n-1, memo) + solve(n-2, memo);
  
  // 4. 반환
  return memo[n];
}

장점:

코드가 재귀적 정의와 유사해서 이해하기 쉬움
필요한 부분만 계산하므로 불필요한 계산 없음

단점:

재귀 호출 스택 깊이 제한 (JavaScript는 약 10,000)
함수 호출 오버헤드

4-2. 타뷸레이션 (Bottom-Up, 상향식)

특징:

반복문을 사용
작은 문제부터 차례대로 풀어 테이블 채움
모든 부분 문제를 계산
공간 최적화 가능

구조:

function solve(n) {
  // 1. DP 테이블 초기화
  const dp = new Array(n + 1).fill(0);
  
  // 2. 기저 사례 설정
  dp[0] = 0;
  dp[1] = 1;
  
  // 3. 작은 문제부터 순서대로 계산
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  
  // 4. 최종 답 반환
  return dp[n];
}

장점:

스택 오버플로우 걱정 없음
반복문이라 일반적으로 더 빠름
공간 최적화가 가능 (dp 배열 크기 줄이기)

단점:

불필요한 부분도 모두 계산할 수 있음
점화식 세우기가 어려울 수 있음

4-3. 어떤 방법을 선택할까?

상황	추천 방법
재귀적 정의가 명확할 때	메모이제이션
n이 매우 클 때 (깊은 재귀)	타뷸레이션
공간 최적화가 필요할 때	타뷸레이션
모든 부분 문제가 필요하지 않을 때	메모이제이션

5. 실전 예제

예제 1: 피보나치 수열

문제: n번째 피보나치 수를 구하라

점화식: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1

타뷸레이션 풀이:

function fibonacci(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];
}

// 공간 최적화 버전 (O(1) 공간)
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;
}

예제 2: 계단 오르기

문제: n층 계단을 오르는데, 한 번에 1칸 또는 2칸씩 오를 수 있다. n층까지 오르는 방법의 수는?

분석:

n층에 도달하려면 (n-1)층에서 1칸 오르거나, (n-2)층에서 2칸 오르기
dp[n] = dp[n-1] + dp[n-2]
피보나치와 동일한 구조!

풀이:

function climbStairs(n) {
  if (n <= 2) return n;
  
  const dp = new Array(n + 1);
  dp[1] = 1; // 1층: 1가지
  dp[2] = 2; // 2층: (1+1), (2) 2가지
  
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  
  return dp[n];
}

// 예시
console.log(climbStairs(5)); // 8
// 방법: 11111, 1112, 1121, 1211, 2111, 122, 212, 221

예제 3: 최소 비용으로 계단 오르기

문제: 각 계단에 비용이 있고, 계단을 오를 때마다 해당 비용을 지불. 한 번에 1칸 또는 2칸씩 오를 수 있을 때, 최소 비용으로 꼭대기에 도달하는 비용은?

입력: cost = [10, 15, 20]

분석:

dp[i] = i번째 계단까지 가는 최소 비용
i번째 계단에 도달하려면:
- (i-1)번째에서 오거나
- (i-2)번째에서 오거나
dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2])

풀이:

function minCostClimbingStairs(cost) {
  const n = cost.length;
  const dp = new Array(n);
  
  // 처음 두 계단은 그냥 올라갈 수 있음
  dp[0] = cost[0];
  dp[1] = cost[1];
  
  for (let i = 2; i < n; i++) {
    dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
  }
  
  // 마지막 계단 또는 마지막 전 계단에서 도착
  return Math.min(dp[n-1], dp[n-2]);
}

// 예시
console.log(minCostClimbingStairs([10, 15, 20])); // 15
// 최적: 1번 계단(15) -> 끝

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

문제: 배열에서 순서를 유지하면서 선택할 수 있는 가장 긴 증가 수열의 길이는?

입력: [10, 9, 2, 5, 3, 7, 101, 18] 출력: 4 (예: [2, 3, 7, 101])

분석:

dp[i] = i번째 원소를 마지막으로 하는 LIS 길이
j < i이고 arr[j] < arr[i]인 모든 j에 대해
dp[i] = Math.max(dp[j] + 1)

풀이:

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1); // 최소 길이는 1
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  return Math.max(...dp);
}

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

시간 복잡도: O(n²) 공간 복잡도: O(n)

예제 5: 동전 거스름돈 (Coin Change)

문제: 특정 금액을 만들기 위한 최소 동전 개수는? (동전은 무한히 사용 가능)

입력: coins = [1, 2, 5], amount = 11 출력: 3 (5+5+1)

분석:

dp[i] = i원을 만드는 최소 동전 개수
각 동전에 대해:
dp[i] = Math.min(dp[i], dp[i-coin] + 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 (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 예시
console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3));        // -1 (불가능)

DP 테이블 채워지는 과정:

amount:  0  1  2  3  4  5  6  7  8  9  10  11
dp:     [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2,  3]

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

문제: 무게 제한이 있는 배낭에 물건을 넣어 최대 가치를 만들어라. (각 물건은 1개씩만 사용 가능)

입력:

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

분석:

dp[i][w] = i번째 물건까지 고려했을 때, 무게 w에서의 최대 가치
i번째 물건을 넣거나, 안 넣거나 둘 중 선택

풀이:

function knapsack(weights, values, capacity) {
  const n = weights.length;
  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] = Math.max(
          dp[i-1][w],  // 안 넣기
          values[i-1] + dp[i-1][w - weights[i-1]]  // 넣기
        );
      } else {
        dp[i][w] = dp[i-1][w];  // 못 넣음
      }
    }
  }
  
  return dp[n][capacity];
}

// 예시
console.log(knapsack([2,3,4,5], [3,4,5,6], 8)); // 10

6. 문제 풀이 전략

6-1. DP 문제 인식하기

다음 키워드가 보이면 DP를 의심하라:

"최소/최대"
"경우의 수를 세라"
"가능한가?"
"최적의 방법"
"가장 긴/짧은"

6-2. 문제 해결 5단계

1단계: DP인지 판단

최적 부분 구조가 있는가?
중복 부분 문제가 있는가?

2단계: 상태 정의

dp[i]가 무엇을 의미하는지 명확히 정의
예: "i번째까지의 최대값", "i원을 만드는 최소 개수"

3단계: 점화식 세우기

현재 상태를 이전 상태들로 표현
예: dp[i] = dp[i-1] + dp[i-2]

4단계: 초기값 설정

기저 사례(base case) 결정
예: dp[0] = 0, dp[1] = 1

5단계: 계산 순서 결정

Bottom-Up: 작은 것부터
Top-Down: 큰 것부터 재귀

6-3. 디버깅 팁

1. DP 테이블 출력하기

console.table(dp);  // 2차원 배열도 깔끔하게 출력

2. 작은 입력으로 시작

n=3, n=5 정도의 작은 케이스로 손으로 계산
DP 테이블이 예상대로 채워지는지 확인

3. 경계 조건 체크

배열 인덱스 범위
0, 1, n-1, n 같은 경계값

4. 초기값 확인

기저 사례가 올바른가?
Infinity, 0, 1 중 무엇이 적절한가?

7. 연습 문제 추천

초급 (DP 입문)

피보나치 수 - 기본 중의 기본
계단 오르기 - 피보나치 변형
집 도둑 (House Robber) - 연속 선택 불가 조건
최대 부분 배열 합 (Maximum Subarray)

중급 (패턴 익히기)

동전 거스름돈 - 조합 문제
최장 증가 부분 수열 - 2중 반복문 DP
최소 비용 경로 (Minimum Path Sum) - 2D DP
단어 분할 (Word Break) - 문자열 DP
팰린드롬 부분 문자열 - 구간 DP

고급 (실전 대비)

편집 거리 (Edit Distance) - 2D DP 응용
0-1 배낭 - 고전 DP
최장 공통 부분 수열 (LCS) - 2D DP
정규식 매칭 - 복잡한 상태 전이
주식 매매 (Best Time to Buy and Sell Stock) 시리즈

'개발지식 > 자료구조' 카테고리의 다른 글

[자료구조] 탐욕법(Greedy Algorithm) (0)	2025.11.25
[자료구조] 그래프(Graph) (0)	2025.11.17
[자료구조] 트리(Tree) (0)	2025.11.10
[자료구조] 탐색(검색) 알고리즘 (Search Algorithm) (0)	2025.11.04
[자료구조] 정렬 (Sort) - 병합 정렬, 퀵 정렬 (0)	2025.10.27

현재글[자료구조] 동적계획법 (Dynamic Programming)

홍익인간 개발자

널리 세상을 이롭게 하고 싶은 개발자

Today :
Yesterday :

홍익인간 개발자