알고리즘 연습하기 - DP를 활용한 배낭문제

우선 DP 알고리즘의 기본 개념은 알고리즘 준비하기 - 다이나믹 프로그래밍에 잘 정리해두었으니 참고하면 좋을 것 같다.

🎯 배낭문제

다이나믹 프로그래밍 (DP) 문제 중 대표적인 유형이 바로 0/1 배낭 문제이다.

물건의 개수 N이 주어지고, 배낭이 최대로 버틸 수 있는 무게 K가 주어진다. 각 물건의 무게와 가치가 주어질 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제가 바로 배낭 문제이다. 그 중에서 0/1인 이유는 물건을 쪼개서 넣을 수는 없고 물건을 넣거나, 혹은 넣지 않거나 둘 중 하나의 선택만 할 수 있기 때문이다.

평범한 배낭 문제를 인용해서 설명을 해보도록 하자. 물건의 개수(N)는 4개, 배낭의 무게(K)는 7이다.

	물건1	물건2	물건3	물건4
무게	6	4	3	5
가치	13	8	6	12

물건의 개수가 4개라서 브루트포스 알고리즘으로 구하더라도 짧은 시간내에 구할 수는 있으나 물건의 개수가 조금만 더 늘어난다면 따져보아야할 경우의 수는 기하급수적으로 늘어나기 때문에 DP를 활용해야 한다.

우선 값을 저장할 dp를 2차원 배열로 만든다. 배열의 형태는 dp[i][j]으로 저장할 것인데, i는 물건의 번호가, j는 배낭의 용량이 된다. 여기서 dp[i][j]는 i번째까지의 물건을 살펴보고 배낭의 용량이 j일 때 배낭에 들어간 물건의 가치합의 최댓값을 의미한다.

즉 궁극적으로 구하고자 하는 K의 가치 최대값은 dp[N][k]에 위치할 것이다.

🎯 배낭문제 해결 과정

1. 배낭문제에서는 우선 배열의 초기상태를 모두 0으로 채워준다.

특히 i가 0일 때에는 배낭의 무게가 몇이던 물건을 선택하지 않았기 때문에 0이 채워지고, j가 0일 때에는 어떤 물건이던 배낭의 무게가 0일 때에는 물건이 들어갈 수 없기 때문이다.

2. 반복문을 통해 물건이 채워질 때마다 최댓값을 구해준다.

첫번째 물건(W = 6, V = 13)의 경우에는 배낭의 무게가 5일때까지는 물건을 넣을 수 없다. 따라서 배낭의 무게가 6일 때부터 가치를 배열에 넣을 수 있게 된다. 따라서 dp[1][6]과 dp[1][7]은 V인 13을 넣어주고 그 전까지는 그대로(0) 둔다.

이제부터 집중을 해야하는 부분이다. 두번째의 물건은 무게가 4, 가치가 8이다. 무게가 4이기 때문에 배낭의 무게가 3일때까지는 들어갈 수 없다. 그러므로 이전 물건까지 살펴보았던 dp[i-1][j]의 값을 그대로 가져온다. 따라서 dp[2][1] ~ dp[2][3]에는 0이 채워진다. 그리고 dp[2][4]에서는 배낭의 무게가 4인데 물건의 무게가 4이니까 두번째 물건을 넣을 수 있다. 따라서 이전 물건까지 살펴보았던 dp[i-1][j]와 dp[i-1][j - i번째의 무게] + i번째의 가치 중 더 큰 값을 넣는다.

이 작업을 i의 끝까지 반복적으로 작업해주면 된다.

앞에서 설명이 장황했지만 결론은 다음과 같다.

현재 물건을 포함하지 않는 경우 : 이전에 구했던 dp[i-1][j]
현재 물건을 포함하는 경우 : 남은 공간의 가치 dp[i-1][j - 현재 물건의 w] + 현재 물건의 가치 V

🎯 해결 코드 (JS)

let dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));

for (let i = 1; i <= N; i += 1) {
  const [weight, value] = bagInfo[i - 1];

  for (let j = 1; j <= K; j += 1) {
    if (j - weight >= 0) {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);
    } else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}

console.log(dp[N][K]);

🎯 배낭문제 다른 유형 확인하기 (비교 대상을 잘 확인하자!)

👉 문제 확인하기 : BOJ - 앱

반드시 처음과 같은 풀이를 고집할 필요는 없다. 이번 문제의 경우에는 비교 대상이 메모리 공간이 되어버리면 안된다. 최대 입력값이 10억인데 10억개의 칸이 비어있는 배열을 만든다는 것은 메모리 초과가 발생할 확률이 높기 때문이다(실제로 나도 메모리 초과가 발생하였다). 따라서 위와 같은 경우에는 비활성화 하는 비용을 기준으로 최대 나올 수 있는 비용의 합까지의 배열 칸을 만든 후에 가능한 최대 메모리 공간을 배열에 입력해주면 해결이 되는 문제이다.

코드는 아래와 같다.

const [N, M] = input.shift().split(' ').map(Number);
const MEMORIES = input.shift().split(' ').map(Number);
const EXTRA_COST = input.shift().split(' ').map(Number);

const SUM = EXTRA_COST.reduce((acc, cur) => {
  return acc + cur;
}, 0);

let DP = Array.from({ length: N + 1 }, () => Array(SUM + 1).fill(0));

for (let i = 1; i <= N; i += 1) {
  const memory = MEMORIES[i - 1];
  const cost = EXTRA_COST[i - 1];

  for (let j = 0; j <= SUM; j += 1) {
    if (cost - j > 0) DP[i][j] = DP[i - 1][j];
    else {
      DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - cost] + memory);
    }
  }
}

let answer = SUM;

for (let i = 1; i <= N; i += 1) {
  for (let j = 0; j <= SUM; j += 1) {
    if (DP[i][j] >= M) answer = Math.min(j, answer);
  }
}

console.log(answer);

🎯 배낭문제
🎯 배낭문제 해결 과정
- **1. 배낭문제에서는 우선 배열의 초기상태를 모두 0으로 채워준다. **
- ** 2. 반복문을 통해 물건이 채워질 때마다 최댓값을 구해준다. **
🎯 해결 코드 (JS)
🎯 배낭문제 다른 유형 확인하기 (비교 대상을 잘 확인하자!)