99클럽 코테 스터디 3일차 TIL + Knapsack 배낭 문제

오늘의 문제 

https://www.acmicpc.net/problem/1450

 

Knapsack 배낭 문제

 

문제 이름부터 냅색 문제라고 되어 있어서 당연하게 Knapsack 문제에 대해 알아 보았다. 

 

문제도 대층 쓱 보니 물건, 가방 이렇게 되어 있어서 당연히 Knapsack 문제인줄 알았다.

 

하지만 함정이 있었으니....

 

 

우선 공부한 Knapsack 문제에 대해 알아보자. 

 

Knapsack 배낭 문제는 물건, 배낭이라는 개념이 나온다. 

 

물건에는 아래 2가지 개념이 존재한다. 

• 물건의 무게
• 물건의 가치

 

배낭에는 아래 1가지 개념이 존재한다. 

• 담을 수 있는 최대 용량 (무게)

 

그래서 Knapsack 배낭 문제의 목표는 아래와 같다. 

 

배낭의 최대 용량을 초과하지 않으면서 담을 수 있는 최대 가치의 합 찾기

 

 

Knapsack 문제는 대표적인 DP 문제이다. 

 

따라서 재귀 함수 또는 DP 테이블을 통해 구현하면 된다. 

 

 

DP 테이블을 사용하는 경우를 간단히 보자. 

 

2차원 배열이 있는데 이 2차원 배열의 의미는 아래와 같다. 

 

최대 가치[i][w] (최대 무게가 w인 가방에서 i번째 물건까지 판단했을 때 최대 가치)

 

그래서 이 2차원 배열을 아래와 같은 3개의 경우를 생각하며 채워나가면 된다. 

 

• 다음 확인하는 물건의 무게가 최대 배낭 무게를 초과
  • 이전의 최대 가치가 유지 → 최대 가치[k][w] = 최대 가치 [k-1][w]
• 다음 확인하는 물건의 무게가 최대 배낭 무게를 초과 X
  • 다음 물건 넣는다 → 최대 가치[k][w] = 최대 가치 [k-1][w]  
  • 다음 물건 넣지 않는다 → 최대 가치[k][w] = 최대 가치 [k-1][w-k 무게] + k번째 물건의 가치

 

마지막 경우의 의미는 배낭의 무게가 'w-k번째 물건의 무게'라고 했을 때 k-1번째 물건까지 확인했을 때 최대 가치에 k번째 물건의 가치를 더하는 것이다. 

 

배낭의 무게가 'w-k번째 물건의 무게'인데 k번째 물건을 넣으면 무게가 최대가 되고 이때 최대 가치이려면 위와 같이 해야 한다. 

 

 

따라서 정리하면 아래와 같이 된다. 

 

• 다음 확인하는 물건의 무게가 최대 배낭 무게를 초과
  • 최대 가치[k][w] = 최대 가치 [k-1][w]
• 다음 확인하는 물건의 무게가 최대 배낭 무게를 초과 X
  • 최대 가치[k][w] = max(최대 가치 [k-1][w], 최대 가치 [k-1][w-k 무게] + k번째 물건의 가치)

 

재귀 함수를 사용하는 경우도 이런 비슷한 개념을 적용해 하는 것 같다. 

 

회고

당연히 knapsack 문제라 생각하고 knapsack 문제에 대해 공부하고 문제를 풀었다. 

 

문제에서는 물건의 가치를 구하는 것이 아니라 n개의 물건을 가방에 넣는 방법의 수를 찾는 것이였다. 

 

이런 문제도 DP로 풀 수 있을 것이라 생각해 경우의 수를 생각해 재귀로 방법의 수를 계산하도록 코드를 작성하였다. 

 

이렇게 하고 예제를 실행해보니 n이 30인 경우 먹통이 되었다. 

 

 

그제야 힌트를 보았는데 이분 탐색이였다;;;

 

n이 30이니 방법의 수를 구하는 경우의 수는 2^30이 된다. 

 

그러면 재귀로 풀게 되면 stack이 굉장히 중첩되어 터질 수 있겠다는 생각이 들었다. 

 

 

다른 풀이들을 보니 중요한 점은 절반을 나눠서 진행하는 것이였다. 

 

2^30은 10억대이지만 2^15는 32768이기 때문이다. 

 

다른 분들의 풀이를 봤는데도 나는 이해를 잘 못했다. 

 

좀 더 고민을 해보고 다시 도전해 봐야 할 것 같다.