9.2 문제 : 여행 짐 싸기(Python)

문제 출처 : algospot.com :: PACKING

algospot.com :: PACKING

---

1. 문제 분석

(1) 완전 탐색 알고리즘

• 물건의 모든 조합을 하나하나 검사하고 이들 중 최적의 조합을 찾아내는 완전 탐색 알고리즘부터 시작
• 각 물건에 대해 가져가거나 말거나 두 가지의 선택이 존재한다.
• 따라서 전체 n개의 물건에 대해 2^n개의 조합이 있고 이를 통해 다음과 같은 부분 문제를 얻을 수 있다.

 

• pack(items) = 지금까지 모든 물건들의 목록이 items에 주어질 때, 남은 용량을 채워 얻을 수 있는 최대 절박도의 합

(2) 동적 계획법

• 물건들의 목록인 items이 아닌 특정 물건을 넣고 남은 용량에 담을 수 있는 물건들의 절박도 합만을 반환하도록 pack()을 변형하면 지금까지 고른 물건의 목록은 상관이 없다.
• 중요한 것은 마지막으로 선택해야하는 물건의 번호(item)와 캐리어에 남아 있는 용량(capacity)이다.
• 책에서는 item 이후의 물건들 이라고 표현되는데 이게 언뜻 보면 item + 1 번 부터의 물건으로 해석되는 것 처럼 느껴진다.
• 그런데 개인적으로는 코드와 설명을 다시 봐도 item부터의 물건을 선택하는 것으로 해석하고 이해하는 것이 쉬웠다.
• 따라서 밑의 설명은 item 번째의 물건 부터 선택하는 것을 가정하고 설명한다.
• 이 부분은 내가 잘 못 이해한 것일 수 있으니 두 가지를 고려해서 자신이 이해하기 쉬운 것으로 판단하기 바람..

 

• pack(capacity, item) = 캐리어의 용량이 capacity만큼 남았을 때 item 부터(책에서는 item 이후의 물건)의 물건들을 선택해서 얻을 수 있는 최대 절박도

 

• item 번째 물건을 선택할 때, 선택할 수 있는 경우는 item 번째 물건을 가져간다 / 가져가지 않는다 의 두 가지 경우가 있다.
• 각 경우에 대해 물건들의 부피와 절박도를 각각 volume과 need에 저장해놓은 상태라고 하면 item+1 번째 부터의 최대 절박도를 아래와 같이 계산할 수 있다.
• pack()은 두 가지 경우에서 절박도가 더 큰 경우를 선택하면 된다.

 

• 1. item 번째 물건을 가져간다.
• pack(capacity - volume[item], item + 1) + need[item]
• 전체 용량에서 item만큼의 부피를 빼고 item의 절박도 만큼 더한다.

 

• 2. item 번째 물건을 가져가지 않는다.
• pack(capacity, item + 1)
• 전체 용량과 절박도는 변하지 않는다.

---

2. 코드 - 문제 풀이 해설 방법

(1) pack(capacity, item) : 최대 절박도의 합을 반환

# 최대 절박도의 합을 반환
# pack(capacity, item) : 캐리어에 남은 용량이 capacity일 때, item 이후의 물건들을 담아 얻을 수 있는 최대 절박도의 합을 반환
def pack(capacity, item):
    # 기저 사례 : 더 이상 담을 수 있는 물건이 없을 때
    if item == n:
        return 0

    # 메모이제이션
    if cache[capacity][item] != -1:
        return cache[capacity][item]

    # 다음 물건을 담지 않을 경우
    cache[capacity][item] = pack(capacity, item + 1)

    # 다음 물건을 담을 경우
    # 남은 용량이 현재 담으려는 물건보다 커야 캐리어에 담을 수 있다.(조건문 빼먹는 실수)
    if capacity >= volume[item]:
        cache[capacity][item] = max(cache[capacity][item], pack(capacity - volume[item], item + 1) + need[item])

    return cache[capacity][item]

• cache[capacity][item]에는 현재 용량(capacity)에서 어떤 물건(item)부터 채워넣을지 말지 선택할 때 얻을 수 있는 최대 절박도가 저장된다.
• 코드를 작성했던 실수 중 하나가 바로 item 번째 물건을 담을 때 용량 초과가 발생하는지 검사하는 조건문을 빼먹었다.
• 물건을 담을 수 있다면, 해당 경우에서 얻을 수 있는 최대 절박도를 비교해서 다시 cache에 담아 이를 반환한다.

(2) reconstruct(capacity, item, picked) : 최대 절박도를 얻을 수 있는 조합을 역 추적을 통해 picked 리스트에 저장

# 선택한 물품들을 역 추적하기
def reconstruct(capacity, item, picked):
    # 기저 사례 : 모든 물건들을 모두 고려함
    if item == n:
        return
    
    # 만일, 두 값이 같다면 items[item]은 선택하지 않았다는 의미이다.
    if pack(capacity, item) == pack(capacity, item + 1):
        reconstruct(capacity, item + 1, picked)

    # 두 값이 같지 않다면 items[item]은 선택했으므로 picked 리스트에 추가하고 다시 재귀적으로 다른 물건을 찾는다.
    else:
        picked.append(items[item])
        reconstruct(capacity - volume[item], item + 1, picked)

• 직전 9.1 예제 문제와 달리 최대 절박도 조합에 대한 정보를 따로 저장하지 않고 pack() 함수의 값을 비교하여 최대 절박도 조합을 추적하는 방식으로 구현되었다.
• pack(capacity, item)와 pack(capacity, item+1)이 같다면 item 번째 물건은 선택하지 않았다는 의미가 된다.
• 즉, item 번째 물건을 선택하지 않아도 최대 절박도를 얻을 수 있다는 뜻이 된다.
• 그러나 같지 않다면 item 번째 물건은 선택했다는 의미이므로 item 번째 물건을 picked에 추가한다.
• 그리고 전체 여유 용량에서 item만큼의 용량이 제외된 상태로 item+1번째 물건부터 다시 재귀적으로 호출하여 위 과정을 반복한다.

(3) 문제 입-출력

for tc in range(int(input())):
    n, w = map(int, input().split())

    items = []
    volume = []
    need = []
    for _ in range(n):
        name, vol, nd = input().split()
        items.append(name)
        volume.append(int(vol))
        need.append(int(nd))

    cache = [[-1] * len(items) for _ in range(w + 1)]
    picked = []

    reconstruct(w, 0, picked)

    for p in picked:
        print(p)

 

---

3. 시간 복잡도 분석

• pack() 함수에서 capacity의 인수는 0부터 w까지 총 w+1 개의 값을 가질 수 있고 item 인수는 0부터 n-1까지 총 n개의 값을 가질 수 있다.
• 이를 가지고 만들 수 있는 문제는 총 (w + 1) * n으로 O(wn)의 부분 문제를 갖는다.
• 각 부분 문제를 해결하는데 걸리는 시간은 상수 시간이므로 전체 시간복잡도는 결국 O(wn)이다.

---

4. 후기

  개인적으로 이 책의 1권은 동적 계획법이 차지하고 있는 부분이 굉장히 큰데 그 이유를 대략적으로 알 것 같다. 문제 유형이 뭔가 콕 찝기가 어렵다고 생각된다. 처음 8장에서 동적 계획법을 시작할 때는 단순하게 문제를 분할(탐색 범위를 분할 한다던가 혹은 카라츠바 알고리즘처럼 수식을 분할하는 형식)하는 것으로 생각되었는데 점점 보기에는 완전 탐색인 형태인 문제를 재구성하여 부분 문제를 정의하고 점화식을 만드는 과정을 통해 해결하는 형식으로 바뀌는 것 같다.

  문제 풀이 해설에 나와있는 것을 보고 이해는 가지만 아직 어떤 문제에 대해 부분 문제를 정의하고 기저 사례를 찾고 어디서 재귀 호출을 진행해야 하는지 설계하는 부분은 어렵게 느껴진다. 특히 확률과 같은 부분에서는 수학적인 개념을 잘 알고 있지 않다면 설계 자체가 안되는 경우도 있는데 대학 입학 이후로 수학과는 거리를 많이 둔 것이 아쉽게 느껴진다. 혹시나 이 블로그를 보는 사람들 중 슬슬 코딩 테스트를 준비하거나 아직 2~3학년인 컴공과 학부생이 있다면 자료 구조, 알고리즘 강의와 확률과 통계 강의는 열심히 듣고 또 별도로 공부하는 방법 등을 통해 이런 고생은 안했으면 하는 바람이다..

---

github : Algorithmic_Problem_Soving_Strategies/q9_2.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies