4.12Dynamic Programming

Dynamic Programming(동적 계획법, DP)

A method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 그 작은 문제의 답을 이용해가며 복잡한 문제를 풀어내는 방식이다. 사실 이름이 주는 멋진 느낌과는 좀 많이 동떨어진 용어인데, 왜냐면 고안자인 Richard Bellman이 그냥 Dynamic이라는 말이 멋져서 선택했다고 했기 때문이다.

기본적으론 예전에 배운 분할 정복(Divide and Conquer)과 비슷한데, 분할 정복이 작은 문제로 나뉜게 서로 겹치지 않는다면, 동적 계획법은 작은 문제들이 겹치기에 같은 문제를 여러번 풀지 않고 메모이제이션을 통해 한번 계산한 결과를 저장하고 활용한다.

예를 들어, Merge Sort는 배열을 반으로 나누어 정렬하고 합치는데, 그렇게 나눈 배열들은 서로 겹치지 않는다. 즉, Divide and Conquer다. 반면, 동적 계획법의 대표적인 예시인 피보나치 수열의 경우 F(n) = F(n - 1) + F(n - 2)로, 보다 작은 문제들의 답을 재활용해서 큰 문제를 해결하는 방식이다.

Overlapping Subproblems(중복된 하위 문제들)

어떤 경우에 동적 계획법을 쓸 수 있을까?

우선, 여러번 반복적으로 겹치는 하위 문제들이 있을때 쓸 수 있다. 앞서 언급한 피보나치 수열이 대표적이다. 만약 F(5)를 구한다고 하면, F(4)와 F(3)을 구해야하는데 F(4)를 구하는데 F(3)이 필요하다. F(3)이 여러번 필요한 것이다. 더 나아가면, F(2)는 더 많이 필요할 것이다. F(5)같이 작은 경우에도 이런데, 더 큰 수를 구하려면 얼마나 많은 중복이 있겠는가?

이미지 출처 : #

Optimal Substructure(최적 부분 구조)

동적 계획법을 쓸 수 있을 또 다른 조건은 최적 부분 구조를 가지고 있어야 한다는 것이다.

문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성되면 그 문제는 최적 부분 구조를 가지고 있다고 한다. 예를 들어 서울에서 부산으로 가는 최적의 경로를 찾는다고 할 때, 서울에서 대전으로 가는 최적 경로와 대전에서 대구로, 대구에서 부산으로 가는 최적 경로를 모두 합친게 서울-부산간 최적 경로라면 이 문제는 최적 부분 구조를 가지고 있다고 할 수 있다.

이미지 출처 : #

재귀 방식과의 비교

계속 예로 들고 있는 피보나치 수열 문제를 재귀 방식으로 푸는것과 DP로 푸는 것을 비교해보자. 재귀로 피보나치 수열을 구현한다면 이렇게 된다.

javascript
function fib(n){
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

이 풀이는 직관적이고, 피보나치 수열의 원리를 잘 보여주는 코드이지만 시간 복잡도가 무려 O(2 ^ N)이다. 보통 안 좋은 알고리즘의 예시로 드는 O(N ^ 2)보다도 가파르게 시간이 상승하는 알고리즘이라는 의미다.

Memoization: Top-Down

이 문제를 개선할 수 있을까? 이 알고리즘이 성능이 좋지 않은 것은, 앞서 언급한 작은 부분들이 계속 반복되는데 이 반복들을 매번 새로 계산하기 때문이다. 따라서, 이 작은 부분들을 한번 풀고 나면 저장(Memoization)한 후 이후에 사용할 수 있다면 시간이 훨씬 빨라질 것이다.

아래는 메모이제이션을 구현한 코드다.

javascript
function fib(n, memo = [undefined, 1, 1]){
  if(memo[n] !== undefined) return memo[n];
  if(n <= 2) return 1;
  const res = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = res;
  return res;
}

이렇게 메모이제이션을 도입하면 n번째 피보나치 수를 구하기 위해 n번 계산하기 때문에 O(N)으로 시간 복잡도가 개선된다.

이 방식은 여전히 위에서부터 내려오며 답을 구한다. 즉, fib(n)을 구하기 위해 fib(n - 1)을 구하고 이를 구하기 위해 fib(n - 2)를 구하는 식이다. 그렇기 때문에 이 방식은 Top-Down 방식의 동적 계획법이라고도 부른다.

Tabulation: Bottom-up

위와는 대비되는 Bottom-Up 방식의 동적 계획법도 있다. 즉, fib(1)부터 시작해 fib(n)까지 올라가는 방식이다.

이 방식은 앞서 계산한 작은 문제의 답들을 table(자바스크립트에선 주로 배열)에 저장하고 반복하는 방식이므로 Tabulation이라고도 불린다.

javascript
function fib(n){
  if(n <= 2) return 1;
  const fibNums = [undefined, 1, 1];
  for(let i = 3; i <= n; i++){
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
}

위에서 내려오는것과 달리, 아래에서 올라가면 n번째까지 계산해야 하는 피보나치 수들을 단 한번만 계산해도 된다. 또, Top-Down 방식과 같이 재귀를 쓰는것보다 공간 복잡도에도 유리하다. 재귀를 쓰게되면 n이 커짐에 따라 스택이 계속 쌓여 스택 오버플로우가 일어날 수 있지만, Bottom-Up은 하나의 배열에 계속 숫자를 추가하는 단순한 방식이므로 안전하다.

---

🤠 연습 문제

강의에선 연습 문제를 제공한다. 이번 포스팅에선 Coin Change라는 문제를 그리디(Greedy) 방식과 동적 프로그래밍 방식으로 풀어보자.

1. 그리디

"동전들의 종류가 담긴 배열"과, "내고자 하는 금액" 두 가지가 인자로 주어질 때 해당 금액을 최소한 개수의 동전으로 지불할 수 있는 조합의 배열을 반환하라는 문제다. 예를 들면 아래와 같다.

javascript
minCoinChange([1, 2, 3, 4, 5], 11); // this should return: [5, 5, 1]
minCoinChange([5, 10, 15, 20, 25], 85); // this should return: [25, 25, 25, 10]
minCoinChange([1, 5, 6, 9], 11); // this should return: [9, 1, 1]

그리디 방식의 핵심은 가장 큰 단위로 우선 먼저 채우고, 남는 것을 작은 것으로 메우는 것이다. 따라서 coins를 우선 정렬하고, amount에서 빼가며 탐색한다.

javascript
function solution(coins, amount){
  coins.sort((a, b) => b - a);
  const answer = [];
  for(let i = 0; i < coins.length; i++){
    while(amount >= coins[i]){
      amount -= coins[i];
      answer.push(coins[i]);
    }
  }
  return answer;
}

2. 동적 게획법

이번엔 같은 인자를 받아서, 해당 amount를 지불하기 위한 방법이 몇갠지를 알려주는 코드를 작성해보자.

2-1. Tabulation(Bottom-Up)

1차원 배열을 만들어서 각 인덱스마다 해당 인덱스만큼의 액수를 지불하기 위한 방법을 저장한다.

0을 만드는 방법은 1가지(동전 안 쓰기)이므로 이를 저장하고, 동전의 종류를 담고 있는 coins를 하나씩 순회하며, 해당 동전을 포함해서 만들수 있는 금액들을 배열에 업데이트한다. 핵심은 아래의 점화식이다:

javascript
ways[x] += ways[x - coin];

금액 x를 만들고자 할때, x를 만드는 방법은 해당 금액에서 지금 순회하고 있는 동전을 뺀 금액을 만드는 방법을 반드시 포함한다.

예를 들어, 1원과 5원짜리로만 구성된 coins를 받아 5원을 만든다고 하면 2가지 방법(1, 1, 1, 1, 1과 5)이 있다. 그러면 6원을 만드는 방법은 1원을 가지고 여러가지 조합을 만드는 루프에서 5원을 만드는 방법의 개수만큼을 더해주면 된다. 즉, (1, 1, 1, 1, 1) 에 1을 추가하는 것 과 (5)에다 1을 추가하는 것이 있다. 이 원리를 사용하여 코드를 작성하면 아래와 같다.

javascript
function coinChange(coins, amount){
  const ways = Array(amount + 1).fill(0);
  ways[0] = 1;

  for(const coin of coins){
    for(let x = coin; x <= amount; x++){
      ways[x] += ways[x - coin];
    }
  }
  return ways[amount];
}

2-2. Memoization(Top-Down)

Memoization으로도 가능하다. 주어진 동전들로 amount를 만드는 방법 수를 구하는 함수 coinChange를 만들고 있으므로, 마지막 동전(lastCoin)을 쓸지/안 쓸지로 나누어

• amount - lastCoin을 만드는 방법 수
• 마지막 동전을 빼고 coins.slice(0, numCoins - 1)의 amount를 만드는 방법 수

이 두 가지를 합하면 된다.

javascript
function coinChange(coins, amount, idx = coins.length, memo = {}) {
  // 금액을 정확히 만들었으면 방법 1가지
  if (amount === 0) return 1;

  // 금액을 음수로 만들거나, 고려할 동전이 없는데 아직 amount 남음 → 불가능
  if (amount < 0 || idx === 0) return 0;

  const key = `${idx}-${amount}`;
  if (memo[key] !== undefined) return memo[key];

  // 경우1: 현재 동전(coins[idx-1])을 사용
  const use = coinChange(coins, amount - coins[idx - 1], idx, memo);

  // 경우2: 현재 동전을 사용하지 않고, 앞의 동전들만 고려
  const skip = coinChange(coins, amount, idx - 1, memo);

  // 두 경우의 수 합산
  memo[key] = use + skip;
  return memo[key];
}