백준 12865 평범한 배낭 - 파이썬 : 트리가 안되는 이유

백준 12865 평범한 배낭 - 파이썬

메모리 초과로 통과하지 못했다.

메모리를 얼마나 많이 사용하게 되는지, 다들 적용하는 다이나믹 프로그래밍 알고리즘의 공간복잡도를 비교해보자.

1. 내 코드의 공간복잡도

k번째 물품 포함 유무의 경우를 모두 확인하기 위해, k레벨은 물론 k+1레벨의 노드를 저장할 공간이 필요하다.

가장 메모리를 많이 차지하는 부분은 각 노드를 구하는 부분이다.

코드에서 볼 수 있듯, k번째 물품을 포함/불포함 하는 경우를 모두 살펴보기 위해 previous와 now 모두 저장할 공간이 필요하다.

 

k는 0이상, n 미만이므로 내 코드의 공간복잡도는 다음과 같다.

2. 냅색 DP의 공간복잡도

전형적인 풀이 방식은, 각 무게별로 가능한 최대 가치를 저장하는 테이블을 만드는 것이다.

배낭문제의 전형적인 DP 풀이 방법은, 0부터 weight_possible까지 정수 단위로 끊어서 각 무게가 가질 수 있는 최대 가치를 저장하는 것이다.

 

예를들어, k행 i열의 값은 0부터 k번 물품의 조합으로 i이하의 무게에서 만들어낼 수 있는 최대 가치를 나타낸다.

따라서 k+1번째 행을 구하기 위해서는 k+1번째 물품의 무게와 k행만 가지고 있으면 된다.

어차피 테이블의 가장 마지막행 마지막 열의 값만 필요하므로, 테이블 전체를 저장하고 있을 필요도 없다.

 

마찬가지로 k는 0이상, n미만이고 이때 공간복잡도와 파이썬 코드는 다음과 같다.

class Burden:
    def __init__(self, w, v):
        self.w, self.v = w, v

    def __str__(self):
        return f'(w: {self.w}, v: {self.v})'

    def __add__(self, other):
        return Burden(self.w+other.w, self.v+other.v)


# 입력부
n, weight_possible = map(int, input().split())
burdens = []
for i in range(n):
    w, v = map(int, input().split())
    burdens.append(Burden(w, v))

previous = [0]*(weight_possible+1) # k번째 행 저장
for burden in burdens:
    now = [0]*(weight_possible+1) # k+1번째 행 저장
    for i in range(len(now)):
        if burden.w <= i:
            now[i] = max(burden.v + previous[i-burden.w], previous[i])
        else:
            now[i] = previous[i]
    previous = now

print(previous[-1])

3. 결론

DP로 풀 때, 메모리는 배낭이 견딜 수 있는 무게에 대해 선형적으로 증가한다.

반면 트리로 풀면 물건 개수에 대해 지수적으로 증가한다.

 

시간복잡도는 더 차이난다. 물품의 개수 n, 배낭이 견딜 수 있는 무게 weight_possible에 대해 위 코드에서 구한 트리와 DP의 시간복잡도는 다음과 같다.

 

매우 큰 입력이 주어졌을 때 DP가 트리보다 시간적·공간적으로 더 효율적인 이유이다.

---