평범한 배낭 _ 시간복잡도 개선

포스팅 했던 평범한 배낭 문제를 시간 복잡도가 낮은 방법으로 다시 풀어 보았다.

3960ms는 기존 코드, 1508ms는 이번에 다시 푼 코드이다.

먼저 기존에 포스팅 했던 방식의 코드는 어떻게 작동하는지 되짚어 보자.

dp 배열에 무게 별로 담을 수 있는 최대 가치를 저장한다.

• 초기 dp 값은 모두 0이다.
• w의 무게와 v의 가치를 가지는 물건이 있을 때, 0 부터 k(버틸 수 있는 무게)-w 까지의 i에 대해서 dp[w+i] = max(dp[i] + v, dp[w+i])를 통해 업데이트 해 나간다.
• 모든 물건에 대해 위와 같은 과정을 거치고, dp값들 중 최대값을 구하면 된다.

문제의 예제 입력에 대해서 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하는 과정은 아래와 같다.

• 빨간색 글씨는 각 물건에서 업데이트 되는 값이다.
• 빨간색 칸들은 각 물건에서 탐색하게 되는 칸들이다.

시간 복잡도가 개선된 코드는 어떻게 작동하는지 알아보자.

dp Dictionary를 이용해 무게 별로 담을 수 있는 최대 가치를 저장한다.

• 초기 dp는 {0: 0}이다.
• w의 무게와 v의 가치를 가지는 물건이 있을 때, dp에 저장되어 있는 무게와 w를 더해 k를 초과하지 않는 경우의 무게의 합과 가치의 합을 임시로 저장해 놓는다. (tmp 배열에 저장한다.)
• tmp 배열에 저장된 무게 tmp_w 와 가치 tmp_v에 대해서, dp에 tmp_w가 존재하지 않는 경우에는 dp[tmp_w] = tmp_v로 추가해준다.
• dp에 tmp_w가 존재하는 경우에는 dp[tmp_w]에 이미 저장되어 있는 값이 tmp_v보다 작을 때만 dp[tmp_w] = tmp_v로 업데이트 해준다.

• 빨간색 글씨는 각 물건에서 업데이트 되는 값이다.
• 빨간색 칸들은 각 물건에서 탐색하게 되는 칸들이다.

두 그림을 비교해 보자. Dictionary를 활용한 코드에서 각 물건에 대해 탐색하는 칸이 적다는 것을 확인할 수 있다. List를 활용한 코드에서는 각 물건에 대해 0 부터 k-w 까지 모두 탐색해나가야 하는 반면 Dictionary를 활용한 코드에서는 기존 dp에 저장되어있는 무게들만 탐색하기 때문에 효율적이다.

CODE

import sys
read=sys.stdin.readline

n,k=map(int,read().split())
things=list(list(map(int,read().split())) for _ in range(n))

dp=dict()
dp[0]=0

for w,v in things:
    #dp에 저장되어 있는 무게와 w를 더해 k를 초과하지 않는 경우의 
    #무게의 합과 가치의 합을 임시로 저장
    tmp=[]
    for dp_w, dp_v in dp.items():
        if dp_w + w <= k:
            tmp.append((dp_w + w,dp_v+v))

    for tmp_w, tmp_v in tmp:
        #tmp_w가 dp내에 존재하면, tmp_v가 기존 dp값보다 작을 때만 업데이트 한다.
        if tmp_w in dp:
            if dp[tmp_w] < tmp_v:
                dp[tmp_w] = tmp_v
        #tmp_w가 dp내에 존재하지 않으면, 바로 업데이트 한다.
        else:
            dp[tmp_w] = tmp_v

print(max(dp.values()))

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]