[Algorithm] Dynamic Programming - 동적 프로그래밍

동적 프로그래밍은 말이 동적이지 쉽게 이해하자면 프로그램이 돌아갈 때 자체적으로 기억을 하게 하는 것이다. 모든 값을 검사할 때, 이전의 값 중 최적의 해를 저장해두었다가, 다음 값을 검사할 때 비교하는 방식이다.

 

아주 아주 간단한 동적 프로그래밍은 최댓값 혹은 최솟값을 찾는 문제이다. 숫자로만 이뤄진 배열을 입력받는 경우, 가장 작은 수를 이미 가지고 있는 최댓값을 구하는 함수 또는 가장 큰 수를 이미 가지고 있는 최솟값을 구하는 함수를 이용해 문제를 풀 수 있을 거다.

 

const findMax = (arr) => {
  let max = -Infinity;
  
  for ( let value of arr ) { // value 는 arr[index] 와 같다 ( for...of 검색 )
    if ( max < value ) {
      max = value;
    }
  }
  return max;
}

const findMin = (arr) => {
  let min = Infinity;
  
   for ( let value of arr ) {
    if ( min > value ) {
      min = value;
    }
  }
  return min;
} 

let arr = [1, 2, 3, 4, 5];
console.log(`minVal: ${findMin(arr)}, maxVal: ${findMax(arr)}`);
// minVal: 1, maxVal: 5

이전의 검사 결과 또는 계산 결과를 저장해둔 다음, 현재 또는 다음의 검사에서 비교하는 방식이 바로 동적 프로그래밍이다. 이전에 탐욕 알고리즘에서 접했던 가방 채우기 문제를 다시 만나보자.

 

가방채우기 문제

이번에는 대중적으로 알려진 예제를 사용해보겠다. 먼저, 우리의 가방은 4파운드의 짐을 넣을 수 있다. 훔칠 수 있는 물건은 아래의 표에서 확인할 수 있듯이 스테레오 ( $3000, 4 lbs ( 파운드 ) ), 노트북 ( $2000, 3 lbs ), 기타 ( $1500, 1 lbs ) 가 있다. 훔치는 물건의 총가치가 최대가 되도록 하려면 어떤 물건을 훔쳐야 할까?

제품명	가격 ( $ )	무게 ( lbs )
스테레오	2000	4
노트북	2000	3
기타	1500	1

 

우리는 딱 봐도 노트북 + 기타 조합이 $ 3500 으로 총가치가 가장 높다는 것을 알 수 있다. 하지만 컴퓨터는 인간처럼 직관적으로 파악하는 능력이 없다 ㅠㅠ

 

그래서 어쩔 수 없이 모든 조합을 검사해주어야 한다!

이 때, 모든 조합에 대해 조건을 걸어주어야 하는 데, 가격과 무게가 그 역할을 담당한다.

그럼 단순하게 모든 조합을 시도해본 뒤, 가능한 조합의 총가치를 비교하면 될까?

const findValuable = (stuff, states, index) => {
  let result = [];
  
  if ( index === stuff.length ) {
    for ( let i = 0; i < stuff.length; i++ ) {
      if ( states[i] ) {
        result.push(stuff[i]);
      }
    }
    return result;
  }
  
  states[index] = false;
  result.push( findValuable(stuff, states, index + 1 ) );
  
  states[index] = true;
  result.push( findValuable(stuff, states, index + 1 ) );
  
  return result;
};

const stuff = [{ name: 'stereo',
                  value: 3000,
                  weight: 4
                },
                { name: 'labtop',
                  value: 2000,
                  weight: 3
                },
                { name: 'guitar',
                  value: 1500,
                  weight: 1
                }];
const bag = { weight: 0, totalValue: 0 };
const maxWeight = 4;
const states = new Array(stuff.length).fill(false);

// 모든 경우의 수
const allPossibility = findValuable( stuff, states, 0 ).flat(2);
// 그 중 가능한 경우
const possible = allPossibility.filter(arr=> arr.length > 0 && arr.reduce((a,c)=>(a+c.weight),0) <= 4);
let result;
let maxVal = 0;

for ( let things of possible ) {
  let tmpResult = things.reduce((a,c) => (a+c.value), 0);
  if ( maxVal < tmpResult ) {
    maxVal = tmpResult;
    result = [...things];
  }
}

console.log(`I can still ${result.map(thing=>thing.name).join(', ')}.
It's total value is $${maxVal}.
And it's weight is ${result.reduce((a,c)=>(a+c.weight),0)} lbs.`);

/*
 * I can still labtop, guitar.
 * It's total value is $3500.
 * And it's weight is 4 lbs.
 */

이 방법은 가능한 방법이긴 하지만 모든 경우를 다 확인해야하고, 선을 넘은 조합은 ( 선넘조 ) 걸러주어야 한다. 물건이 3개인데, 나올 수 있는 모든 경우의 수는 8가지 ( 아래의 표 ) 이다.

제품명	총 가격 ( $ )	총 무게 ( lbs )
물건없음	0	0
기타	1,500	1
랩탑	2,000	3
스테레오	3,000	4
기타 + 스테레오	4,500	5
기타 + 랩탑	3,500	4
스테레오 + 랩탑	5,000	7
기타 + 스테레오 + 랩탑	6,500	8

 

만약 물건이 늘어난다면, 4개면 16개가 된다. 즉, 이 알고리즘의 실행 시간은 O(2^n)이 된다. ( === 너무 느리다 )

 

이런 문제를 해결하기 위해 사용하는 알고리즘이 바로

 

Dynamic Programming ( 동적 프로그래밍 )

이다. 동적 프로그래밍은 하위의 작은 문제를 풀고, 이를 확장해서 더 큰 문제를 풀어나가는 방법이다.

위에서 예를 든 가방 채우기는 1 lbs와 3 lbs를 담을 수 있는 작은 가방이 있다고 가정하고 문제를 푼 다음, 이를 이용해서 원래의 문제를 풀어낸다.

 

아래와 같은 표가 있을 때, 열은 가방의 크기 ( 바로 앞에서 언급한 작은 가방 ) 를 나타내고 행은 선택할 물건을 나타낸다.

각 행에서 순차적으로 가방의 크기를 늘려갈 것이고 ( 오른쪽으로 진행하고 ), 가방의 원래 크기 ( 여기서는 4 lbs ) 에 도달하면 다음 행으로 넘어간다.

 

각 칸에서 하는 일은 물건을 넣느냐 아니냐 하는 문제이다.

먼저 기타행 만 실행하면 다음과 같다.

	1	2	3	4
기타	기타	기타	기타	기타
스테레오
랩탑

현재 훔치기 딱 좋은 물건은 기타이다. ( $ 1500 )

 

다음은 스테레오까지 실행해보자

	1	2	3	4
기타	기타	기타	기타	기타
스테레오	기타	기타	기타	스테레오
랩탑

이번에는 4 lbs의 가방에 도달하면서 넣을 수 있는 물건이 스테레오로 바뀌었다! 왜일까?

 

물건이 기타와 스테레오뿐이고, 각각 1 lbs, $ 1,500 과 4 lbs, $ 3,000 을 가지고 있다.

이 프로그램은 총가치가 가장 큰 경우를 찾아야 하므로, 가방의 무게 변화 ( 1 lbs -> 2 lbs -> 3 lbs -> 4 lbs )에 따라 넣을 수 있는 최선의 값을 넣게 된다.

 

스테레오의 끝까지 실행한 지금 최종 가치는 $ 3,000 이다!

 

이번에는 랩탑 행을 실행해보자

	1	2	3	4
기타	기타	기타	기타	기타
스테레오	기타	기타	기타	스테레오
랩탑	기타	기타	랩탑

아직 3 lbs 가방까지밖에 실행하지 않았다.

 

가방의 크기가 2 lbs 일 때 까지는 기타만 들어갈 수 있지만, 가방의 크기가 3 lbs라면 랩탑의 가치가 기타보다 크기 때문에 랩탑이 들어간다. 그다음 마지막에는 아래와 같은 결과를 만날 수 있다.

	1	2	3	4
기타	기타	기타	기타	기타
스테레오	기타	기타	기타	스테레오
랩탑	기타	기타	랩탑	기타 + 랩탑

논리적으로 다시 보자.

각 행을 나눠서 본다면, 가방의 크기가 1 lbs 일 때 스테레오나 랩탑의 행에서는 바로 윗 행 ( 스테레오 행 1 열이라면 기타가 들어있는 칸 ) 의 값을 가져온다.

 

그러나 가방의 크기가 현재 행의 물건을 충분히 담을 수 있는 경우에는 현재 행의 물건의 가치와 바로 위 값을 비교하여 더 큰 가치의 물건을 넣는다. ( 스테레오의 마지막에 스테레오가 들어간 경우, 혹은 랩탑의 3열에 랩탑이 들어간 경우 )

 

그리고 랩탑의 4열에 이르러서는 4열의 이전까지 최댓값이 $ 3,000 인 것을 알 수 있기 때문에 랩탑의 3 lbs에 1 lbs 가방을 더할 수 있는지 확인하고, 더할 수 있다면 그 가치가 이전의 최댓값보다 큰 지 검사한다.

 

그리고 그 값이 크다면 그 조합을 현재의 최종 최댓값으로 저장한다. 그래서 나온 결과가 ' 기타 + 랩탑 ' 이다.

 

각 칸의 가치를 계산하자면 다음과 같다.

 

cell[{i /* 행 */}][{j /* 열 */}] 의 최댓값은 아래의 두 가지로 결정할 수 있다.

1. 지금까지 구한 cell [i-1][j]의 값 중에서 가장 최대값 ( 행만 위로 올린다 )
2. 현재 물건의 가치 + 남은 공간의 가치 ( 남은 공간의 가치 === cell[i - 1][j - 현재 물건의 무게] )

 

직관적으로 풀었다고 하더라도, 아마 위의 결정 방식을 사용했을 거다. 그리고 그 방식을 알고리즘처럼 코드에 적용한다면 그걸 우리는 동적 프로그래밍이라 부른다.