[Python] 백준 / gold / 12865 : 평범한 배낭

문제 링크 : https://www.acmicpc.net/problem/12865

알고리즘 분류 - 다이나믹 프로그래밍
다이나믹 프로그래밍으로 들어가서 풀었지만, 정렬과 힙으로 풀릴 것 같아서 시도해봤다. 오답이었는데, 왜 틀렸지 생각하고 찾아내는 과정이 좀 오래걸렸다. 너무 맞는 것 같아서. 시간복잡도를 따지는 연습은 많이 된 것 같고 내가 생각한 알고리즘 로직이 진짜로 정확한지 따지는 연습은 좀 더 필요한 것 같다.

이 문제에서 얻어갈 3 가지

1. pop 할 땐 ? empty 를 고려한다.
2. 내가 채택한 알고리즘이 진짜로 정답을 내는지 충분히 고민하고 코드를 써야겠다.
   만약 이게 시험이었다면 맞지도 않는 알고리즘으로 시간만 엄청 잡아먹은거다..
3. Knapsack - DP
   Fractional Knapsack - Greedy

정렬과 힙을 사용하면 오답인 이유

• 힙을 사용한 풀이 방법

난 물건들을 무게 (W) 로 정렬하고, 탐색을 시작했다. 그리고 bag 라는 힙을 정의했다. 이 힙은 value 를 기준으로한 min heap 이다.

현재 물건 thing[i] 를 가방에 넣을 수 있다면 넣고, 무게가 오버되서 넣을 수 없다면 넣을 수 있는 무게가 될 때까지 value 가 작은 물건을 pop 한다. 그리고 pop 진행 전 prevValue 와 방금 새롭게 만든 bagValue 를 비교해서 가치가 높은 것을 bagValue 로 남기고 다음 차례를 진행한다.

• 이렇게 하면 근데 다음과 같은 반례가 생긴다.

예를 들어 K = 102 이고 현재 bag에 A(무게 100, 가치 2), B(무게 2, 가치 1) 2개의 물건이 들어있다고 가정해보자. 그리고 다음에 들어갈 수 있는 3개의 물건이 C(무게 10, 가치 1000), D(무게 9, 가치 2000), E(무게 8, 가치 3000) 라고 가정한다.

근데 나는 힙에서 가치가 낮은 물건을 pop 했기 때문에 B를 pop 하게 된다. 그러면 가방에 들어있는 물건의 무게는 100 이기 때문에 C, D, E 를 넣을 수 없게 된다.

힙에서 최솟값인 B를 제거하지 않고, 현재 손해 보는 것 같더라도 A를 제거하면 나중에 C, D, E 를 모두 넣을 수 있기 때문에 A를 pop 하는게 합리적인 선택이 된다.

그래서 이 문제는 이렇게 풀면 안됐다. 현재 손해 보더라도 나중에 이득을 보는지 확인하는 알고리즘은 "대부분" 다이나믹 프로그래밍이다.

이 문제를 보석 도둑 문제와 비슷하다고 생각해서 잘못 풀게 된 것 같다.
https://velog.io/@heyksw/Python-백준-gold-1202-보석-도둑
이 문제는 가방도 여러 개고 보석도 여러 개라서 각각 정렬을 하기 때문에 조금 다르다.

올바른 풀이 - Knapsack

공부를 해봤는데, 이 문제는 knapsack 문제라고도 불리는 유명한 문제였다.
Fractional Knapsack 문제는 보석을 쪼갤 수 있을 때고, Knapsack 문제는 보석을 쪼갤 수 없을 때다. 풀이 방법은 다음과 같았다.

Fractional Knapsack - Greedy 알고리즘
Knapsack - Dynamic Programming

( 의문점 ) 근데 그럼 보석 도둑 문제는 Knapsack 문제가 아닌건가 ?
-> knapsack 이 아니다. 보석 도둑 문제는 가방이 여러 개 였고, 가방에 1개의 보석만 담을 수 있었다. Knapsack 문제는 가방이 1개고 여러가지 보석을 담을 수 있는 경우다. 그래서 그 문제는 그리디, 힙으로 푸는 문제였다.

Knapsack 문제 풀이 방법

물건이 N개, 가방 최대 수용무게 K 일 때 dp 설정을 다음과 같이 한다.
dp[i][j] = ( i 번째 물건까지 살펴봤을 때, 가방 무게가 j 인 상황에서의 최댓값 )
편의상 가방이 수용가능한 무게를 가방무게라고 한다.

이렇게 보면 어려워 보이는데, 풀어서 생각하면 이해할 수 있다.

• 먼저 (j < w) 인 경우 = 이번 물건 무게가 가방무게 보다 무거운 경우
  -> 당연히 가방에 그 물건을 넣을 수가 없다.
• (j >= w) 인 경우 = 이번 물건을 가방에 넣을 수 있는 경우
  max( 이번 물건을 그냥 넣지 않는 경우, 이번 물건을 꼭 넣고 싶은 경우 )
  = max( 그냥 이번 물건을 넣지 않은 dp[i-1][j] , 이번 물건을 넣기 위해 필요한 무게 w 를 뺀 dp[i-1][j-w] 에 이번 물건의 가치 v를 추가 )

이렇게 다이나믹 프로그래밍을 수행하면 dp[N-1][K] 에 정답이 저장된다.

"이 생각을 대체 어떻게 하지"

( 복습하다가 든 생각. 중요 )

두 번째 이 문제를 복습할 때는 풀이 방법이 기억나버렸다. 그리고 내가 이 문제를 생판 처음 접근했다면 절대 못 풀었을 것 같다고 생각이 들었다.

이런 문제는 풀이를 미리 알고 있어야만 풀 수 있나 ? 이런 풀이를 내가 생으로 생각해낼 수 있나 ? 이런 생각 때문에 진짜 오래 고민한 것 같다.

[ 결론 ] : 바로 이런 문제 풀이가 생각나는건 불가능하다. 하지만 but. dp 문제는 결국 dp table 을 만들어야 된다. 이게 무슨 의미냐면 주어진 조건을 활용해서 1차원 또는 2차원 table을 만들어야 된다는 생각은 할 수 있다는 거다.

이 문제는 물건 (N) 과 가방 (K) 가 메인 조건이다. 그래서 N 이나 K 를 활용한 1차원 dp, 또는 N, K 를 같이 활용한 2차원 dp 로 풀릴것이다. 라는 예측을 할 수 있게된다. 조금 더 디테일 하게 나누면 무게 (W) 와 가치 (V) 를 정렬할 것인지 까지 고려해볼 수도 있을거다.

이런식으로 어떻게 dp table 을 구성할 건지, 그에 따른 점화식을 어떻게 짤건지 시행 착오를 겪다보면, 어려운 문제도 결국 풀 수 있게 될것 같다.

dp table 이 3차원인 문제가 나온다면, 그냥 틀릴꺼다.

오답 코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())
thing = []
for _ in range(N):
    W, V = map(int, sys.stdin.readline().split())
    # 가치를 기준으로 힙 생성을 위해 Value, Weight 순서
    thing.append((V, W))

thing.sort(key=lambda x:x[1])
bag = []
bagWeight = 0
bagValue = 0
i = 0

# thing -> (Value, Weight)
while i < N:
    if bagWeight + thing[i][1] <= K:
        bagWeight += thing[i][1]
        bagValue += thing[i][0]
        heapq.heappush(bag, thing[i])
    else:
        prevWeight = bagWeight
        prevValue = bagValue
        popThing = []
        while bagWeight + thing[i][1] > K:
            x = heapq.heappop(bag)
            popThing.append(x)
            bagWeight -= x[1]
            bagValue -= x[0]
        if prevValue < bagValue + thing[i][0]:
            bagValue += thing[i][0]
            bagWeight += thing[i][1]
            heapq.heappush(bag, thing[i])
        else:
            bagValue, bagWeight = prevValue, prevWeight
            for x in popThing:
                heapq.heappush(bag, x)
    i += 1

print(sum(map(lambda x: x[0], bag)))

정답 코드

import sys
N, K = map(int, sys.stdin.readline().split())
gems = []

for _ in range(N):
    # W, V
    gems.append(tuple(map(int, sys.stdin.readline().split())))

# dp[i][j] = i 번째 까지 탐색 했을 때, 무게 j 인 가방의 최대 가치
dp = [[0]*(K+1) for _ in range(N)]
for i in range(N):
    dp[i][0] = 0
for j in range(K+1):
    if gems[0][0] <= j:
        dp[0][j] = gems[0][1]

for i in range(1, N):
    for j in range(1, K+1):
        if gems[i][0] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-gems[i][0]]+gems[i][1])

print(dp[-1][-1])