이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌17 - Algorithm - 일 년 전 등록 / 2달 전 수정

동적 프로그래밍(Dynamic programming)

배낭 문제, LCS 문제, 막대기 문제
조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

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

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

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

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

이번 시간에는 동적 프로그래밍의 대표적인 세 가지 문제를 풀어보겠습니다. 막대기 자르기 문제, 최장 공통 부분 수열 문제, 그리고 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) = 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나 BCDB입니다. 앞에서부터 겹치는 것들을 찾아서 문자열을 만들 때 그것이 가장 길다면 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(ABCBDA, BDCABA)와 c(ABCBDAB, DBCAB) 중 더 큰 값이 되는 겁니다.

이렇게 끝부분부터 비교해 하나씩 줄여가면 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인 이유는 물건을 쪼개서 넣지는 못하고, 선택지가 통째로 넣거나 아예 안 넣거나 두 개밖에 없기 때문입니다.

undefined

직관적으로 보면 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-무게] +가치)입니다. 마지막 물건 하나를 뺀 가치와 이전 물건을 뺀 후 새로 넣은 물건의 가치 중 큰 값을 고르면 됩니다.

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

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

6개의 댓글이 있습니다.
2달 전
궁금한게 있습니다. 배낭문제에서
무게 10 가치 60
무게 20 가치 100
무게 30 가치 120
경우 결과값이 220으로 나오는데 제생각에는 300이 나와야 하는데
제가 잘못계산 한걸까요? 확인후 알려주시면 정말 감사하겠습니다!
2달 전
220이 맞습니다. 20 * 5 + 30 * 4해서 220입니다. 무게는 20 + 30이라 50이고요.
2달 전
최대 가치는 무게 10을 5번 넣으면 300인데 한번 넣은 무게는 다시 넣을 수 없는조건이 걸리는건가요?
2달 전
무게 10짜리가 1당 가치가 6입니다 60은 총 가치이고요. 무게 20은 1당 가치가 5고, 30짜리는 1당 가치가 3입니다.
5달 전
4인 막대기의 최대 가격은 R4 = max(P1 + R3, P2 + R2, P3 + R1) 이부분에서 왜 P4는 고려하지 않는 건가요?? 막대 길이가 6이라면 P6이 최대값 아닌가요??
5달 전
수정했습니다 감사합니다
6달 전
막대기 자르기에서 길이가 4로 주어졌을 때
1+3, 2+2, 3+1 뿐만 아니라
1+1+2도 고려해야 하는 거 아닌가요?
6달 전
아닙니다. Pi+Rn-i만 가능합니다. 1+1은 2보다 못하기 때문에 이미 제외되었습니다
6달 전
질문을 하고 곰곰이 생각해보니 P(1) + R(3) 의 R(3)에 이미 P(1) + P(2) 가 고려되었겠군요. 감사합니다.
6달 전
그러면 저문제에서 Rn = max(Ri + Rn-i) (i는 1부터 n) 이어도 가능한가요?
6달 전
Ri면 구할 수 없습니다. Ri는 결과값이기 때문에 입력 값으로 쓰기는 부적절합니다.
6달 전
저 문제에서는 가능하지만 일반적으로 Rn = max(Pi + Rn-i) (i는 1부터 n) 이 아니라 Rn = max(Ri + Rn-i) (i는 1부터 n) 이어야 한다고 생각했는데 아닌가요~?
6달 전
일반적이라는 말이 상당히 애매합니다. 동적프로그래밍은 유형별로 풀이 식이 다 다릅니다.
6달 전
예제코드가 어떤 언어로 작성된건가요?
특히 코드중 === 연산이 어떤것인지 알려주시면 감사하겠습니다.
6달 전
자바스크립트입니다. ===는 값뿐만 아니라 자료형까지 일치하는지를 비교합니다.