ZeroCho Blog

안녕하세요. 이번 시간에는 동적 프로그래밍에 대해 알아보겠습니다. 오랜만에 알고리즘으로 돌아왔습니다. 자료구조는 해시 테이블 빼고는 전부 다루었습니다. 해시 테이블은 이따가 다루겠습니다.

동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻입니다. 그리고 전혀 다이나믹하지도 않습니다. 그래서 어떤 서울대 교수님은 동적 프로그래밍 대신 기억하기 프로그래밍이라는 용어를 쓰기도 합니다.

메모이제이션 강좌를 보셨나요? 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다.

알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.

이번 시간에는 동적 프로그래밍의 대표적인 세 가지 문제를 풀어보겠습니다. 막대기 자르기 문제, 최장 공통 부분 수열 문제, 그리고 0/1 배낭 문제입니다.

막대기 자르기

일단 막대기부터 잘라봅시다. 하나의 긴 막대기가 있는데 막대기 조각마다 가격이 다릅니다. 막대기를 적절하게 잘라서 가장 가격이 높게 만들어야 합니다.

길이(i) 0 1 2 3 4 5 6 7 8 9 10
가격(Pi) 0 1 5 8 9 10 17 17 20 24 30

예를 들면 길이가 4인 막대기를 자를 때 얻을 수 있는 최대 가격은, 길이를 2인 막대기 두 개로 나누어서 가격을 5 + 5 = 10으로 만드는 겁니다. 길이가 6인 막대는 자르지 않고 그냥 팔았을 때 최대 17의 가격을 얻을 수 있습니다.

이 문제는 그냥 풀기엔 좀 복잡하게 보이지만 동적 프로그래밍을 사용하면 간단하게 풀 수 있습니다.

길이가 n인 막대기의 최대 가격을 Rn이라고 했을 때, Rn = max(Pi + Rn-i) (i는 1부터 n)로 나타낼 수 있습니다. max는 여러 값 중의 최대값을 의미합니다. 예를 들면 아까 길이가 4인 막대기의 최대 가격은 R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)이죠.

P1, P2, P3은 이미 주어져 있습니다. 이제 R1, R2, R3을 구해야 하는데요.
R1은 Rn = max(Pi + Rn-i) (i는 1부터 n) 식에서 max(Pi + R0)이므로 1입니다.
R2는 max(P1 + R1, P2 + R0)이라 max(2, 5) = 5입니다.
R3는 max(P1 + R2, P2 + R1, P3 + R0)라서 max(6, 6, 8) = 8입니다.
R4는 위의 값들로부터 max(9, 10, 9, 9) = 10임을 알 수 있습니다.

위의 과정에서 R1, R2, R3는 계속해서 나옵니다. 이 값들을 저장해 두고 재사용하면 일일히 재계산하지 않아도 되죠. 바로 여기서 Top-down으로 불리는 메모이제이션을 사용할 수도 있고, Bottom-up이라 불리는 상향식 계산법을 사용할 수도 있습니다.

상향식 계산법이 성능이 더 좋은 경우가 많으므로 상향식 계산법을 사용하겠습니다.

var p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
function cutRod(p, n) {
  var r = [0];
  for (var j = 1; j <= n; j++) {
    q = -1;
    for (var i = 1; i <= j; i++) {
      q = Math.max(q, p[i] + r[j - i]);
    }
    r[j] = q;
  }
  return r[n];
}
cutRod(p, 2); // 5
cutRod(p, 3); // 8
cutRod(p, 4); // 10
cutRod(p, 7); // 18

r이 바로 이전에 계산한 값들을 저장하는 부분입니다. 안의 반복문은 r[1]부터 r[j]를 구하는 부분입니다. q는 각 길이에 대한 최대 가격 Ri을 의미하고요. 바깥의 반복문은 안의 반복문으로부터 구했던 r[1]~r[j]를 활용해 Rn의 최대값을 도출하고 있습니다.

최장 공통 부분 수열 문제

최장 공통 부분 수열(LCS) 문제는 두 개의 문자열에서 순서대로 겹치는 문자가 최대 몇 개인지 구하는 문제입니다. 예를 들어 ABCBDAB와 BDCABA에서 LCS는 BCAB나 BDAB나 BCBA입니다. 앞에서부터 겹치는 것들을 찾아서 문자열을 만들 때 그것이 가장 길다면 LCS가 되는 거죠.

이 문제는 다음과 같이 분석할 수 있습니다. i라는 문자열과 j라는 문자열이 있다고 칩시다. lcs(i,j)는 이 두 문자열의 LCS 길이입니다. 만약 문자열의 마지막 두 문자가 같다면 lcs(i, j) = lcs(i-1, j-1) + 1과 같습니다. lcs(ABCBDAB, BDCAB)는 lcs(ABCBDA, BDCA) + 1과 같은 거죠.

만약 두 문자열의 마지막 문자가 다르다면, lcs(i, j) = max(lcs(i, j-1), lcs(i -1, j))가 됩니다. lcs(ABCBDAB, BDCABA)는 lcs(ABCBDAB, BDCAB)와 lcs(ABCBDA, BDCABA) 중 더 큰 값이 되는 겁니다.

이렇게 끝부분부터 비교해 하나씩 줄여가면 LCS의 길이가 나오게 됩니다.

function LCS(x, y) {
  var i = x.length;
  var j = y.length;
  var result = [];
  for (var k = 0; k <= i; k++) {
    if (!result[k]) {
      result[k] = []; // 이전 계산 값 저장 공간
    }
  }
  for (k = 0; k <= i; k++) {
    for (var l = 0; l <= j; l++) {
      console.log(k, l);
      if (k === 0 || l === 0) { // 베이스 값 설정
        result[k][l] = 0;
      } else if (x[k - 1] === y[l - 1]) { // 마지막 두 문자 비교, 같으면
        result[k][l] = result[k - 1][l - 1] + 1;
      } else { // 마지막 두 문자가 다르면
        result[k][l] = Math.max(result[k - 1][l], result[k][l - 1]);
      }
    }
  }
  return result[i][j];
}
LCS('ABCBDAB', 'BDCABA'); // 4

0/1 배낭 문제

배낭 문제는 무게 제한이 50인 배낭에 다음과 같은 세 개의 물건을 넣는 문제입니다. 넣은 물건들의 가치(v) 합이 최대가 되면 됩니다. 문제는 세 물건의 무게(w)를 합치면 60이라 다 넣지는 못한다는 겁니다.

이 문제 이름이 0/1인 이유는 물건을 쪼개서 넣지는 못하고, 선택지가 통째로 넣거나 아예 안 넣거나 두 개밖에 없기 때문입니다.

직관적으로 보면 2번과 3번 물건을 넣어서 무게는 50으로 맞추고, 가치는 220으로 하면 최적입니다. 문제는 컴퓨터한테 이 문제를 어떻게 풀도록 하냐는 거죠. 컴퓨터에게는 직관이 없습니다.

제일 먼저 떠오르는 것은 무게 대비 가치 순서로 고르도록 하는 겁니다. 이렇게 하면 1번과 2번을 선택하게 되고, 3번을 선택하지 못합니다. 틀린 결과죠.

사실 방법은 없습니다. 그냥 모든 경우를 계산해서 노가다로 푸는 겁니다. 중간에 계산 결과가 겹치는 부분은 저장해서 재사용하고요.

var item = [[1, 60, 10], [2, 100, 20], [3, 120, 30]];
function zeroOneKnapsack(item, cap) {
  var m = [];
  for (var i = 0; i <= item.length; i++) {
    m[i] = [];
  }
  for (i = 0; i < item.length + 1; i++) {
    for (var j = 0; j <= cap; j++) {
      if (i === 0 || j === 0) { // 물건이나 무게가 없음
        m[i][j] = 0;
      } else if (item[i-1][2] > j) { // 물건의 무게가 j보다 크면
        m[i][j] = m[i-1][j];
      } else {
        m[i][j] = Math.max(m[i-1][j], m[i-1][j-item[i-1][2]] + item[i-1][1]);
      }
    }
  }
  return m[item.length][cap];
}
zeroOneKnapsack(item, 50); // 220

위와 같이 컴퓨터에게 노가다를 시킬 때도 미리 알고리즘을 구상한 후 시켜야 합니다. 위의 코드에서 주목할 부분은 m입니다. m은 메모이제이션을 하는 부분입니다.

m[i][w]는 i개의 물건과 w의 무게 제한으로 가능한 최대 가치를 의미합니다. 이제 m[0][0]부터 순차적으로 구해나가야 합니다.

아무 물건도 선택하지 않았거나 무게가 없는 경우, m[i][w] = 0입니다.
i번째 물건의 무게가 무게 제한을 초과하는 경우는 m[i][w] = m[i-1][w]입니다. 즉 마지막에 넣은 물건 하나를 다시 뺀 가치가 답이 됩니다.

초과하지 않는 경우는 m[i][w] = max(m[i-1, w], m[i-1, w-무게] +가치)입니다. 마지막 물건 하나를 뺀 가치와 이전 물건을 뺀 후 새로 넣은 물건의 가치 중 큰 값을 고르면 됩니다.

다음 시간에는 그리디 알고리즘에 대해 알아보겠습니다.