DP: 0 / 1 Knapsack 이론

DP: 0 / 1 Knapsack 

0/1 Knapsack 문제

 

아이디어

주어진 배낭(가방)은 고정된 용량을 가지고 있으며, 여러 개의 아이템이 주어진다.

각 아이템은 **무게(weight)**와 **이익(profit)**을 가지고 있다.
우리는 총 이익을 최대화하면서도, 배낭의 용량을 초과하지 않도록 해야 한다.

 

이 알고리즘이 0/1 Knapsack이라 불리는 이유는

각 아이템을 선택하거나(1) 선택하지 않거나(0) 하는 이진 선택(binary decision) 구조이기 때문이다.

---

문제 정의

• N개의 아이템이 주어진다.
• 배낭의 최대 수용량이 주어진다.
• profit[i]: i번째 아이템의 이익
• weight[i]: i번째 아이템의 무게
• 각 아이템은 한 번만 추가 가능하며, 부분적으로 추가할 수 없음.
• 배낭에 넣을 수 있는 아이템들의 조합 중 최대 이익을 반환해야 한다.

잘못된 직관: 탐욕적 선택(Greedy Approach)

처음에는 이익(profit)이 가장 큰 아이템을 먼저 선택하는 탐욕적(Greedy) 접근법이 효과적일 것 같지만,
이 방식은 항상 최적해(optimal solution)를 보장하지 않는다.

예를 들어, profit = [4, 4, 7, 1] weight = [5, 2, 3, 1] 가 있다고 해보자.

이익이 가장 높은 7을 먼저 선택하는 방식은 효과적이지 않을 수 있다.
왜냐하면 가장 이익이 높은 아이템이 가장 무거울 수도 있기 때문이다.

이를 해결하기 위해, 우리는 모든 가능한 선택 조합을 고려하는 **결정 트리(decision tree)**를 만들 수 있다.
이 트리는 배낭의 남은 용량(=C)과 현재 선택한 아이템들에 따라 변화하며,
각 경로는 아이템을 포함하거나(1), 포함하지 않거나(0) 하는 선택으로 구성된다.

코드 구현을 고려할 때

기본(base) 케이스

• i == len(profit)일 때, 즉 모든 아이템을 확인했을 때는 더 이상 선택할 아이템이 없으므로 종료해야 한다.
  → 반환값: 0 (더 이상 얻을 이익이 없음)

재귀적 접근

각 아이템에 대해 두 가지 선택지가 존재한다.

1. 아이템을 포함하지 않음 (skip)
   • 배낭의 용량을 고려할 필요 없이, 단순히 다음 아이템으로 넘어간다.
   • 이 경우, 현재까지의 **이익(profit)**에 변화가 없다.
2. 아이템을 포함함 (include)
   • 아이템을 포함하려면, 해당 아이템의 **무게(weight[i])**가 현재 배낭의 남은 용량보다 크지 않아야 한다.
   • 포함하는 경우, 배낭의 **새로운 남은 용량(capacity)**을 계산하고, 다음 아이템을 고려한다.
   • 이후, 새로운 용량을 가진 상태에서 재귀 호출하여 남은 아이템을 계속 평가한다.

최대 이익 계산

• 두 가지 선택지(포함 vs 미포함)에 대한 이익을 비교하여 더 큰 값을 선택해야 한다.
• 즉, maxProfit=max⁡(skip했을 때의 이익, include했을 때의 이익)

 

# Brute force Solution
# Time: O(2^n), Space: O(n)
# Where n is the number of items.
def dfs(profit, weight, capacity):
    return dfsHelper(0, profit, weight, capacity)

def dfsHelper(i, profit, weight, capacity):
    if i == len(profit):
        return 0

    # Skip item i
    maxProfit = dfsHelper(i + 1, profit, weight, capacity)

    # Include item i
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + dfsHelper(i + 1, profit, weight, newCap)
        # Compute the max
        maxProfit = max(maxProfit, p)

    return maxProfit

 

시간 복잡도 최적화 (Memoization 활용)

앞서 설명한 재귀적 해결법은 **O(2ⁿ)**의 시간 복잡도를 가지며, 이는 매우 비효율적이다.
그 이유는 같은 서브 문제를 여러 번 계산하기 때문인데,

이를 **메모이제이션(memoization)**을 활용하여 최적화할 수 있다.

• 캐시(cache)를 사용하여 이미 계산한 값 저장
• 배낭의 남은 용량(capacity)와 현재 아이템의 인덱스(i)를 기준으로 저장
• 중복 계산을 피하고 최적화 → O(2ⁿ)에서 O(n * m)으로 개선 (n은 아이템 개수, m은 최대 용량)

 

 

메모이제이션을 활용한 최적화

우리는 2D 캐시(cache) 배열을 만들어 이미 계산한 값을 저장하고,
중복 계산을 방지하여 O(n × m) (아이템 수 × 배낭 용량) 으로 줄일 수 있다.

최적화 방법

1. 캐시(메모이제이션 테이블) 생성
   • cache[i][capacity]는 i번째 아이템을 고려했을 때, 남은 배낭 용량이 capacity일 때 얻을 수 있는 최대 이익을 저장한다.
   • 초기값을 -1로 설정하여, 아직 계산되지 않은 상태임을 표시한다.
2. 이미 계산된 값이면 바로 반환
   • cache[i][capacity]가 -1이 아니라면, 이전에 계산한 값을 사용하여 중복 계산을 피한다.
3. 값을 캐시에 저장
   • 새롭게 계산한 최댓값을 cache[i][capacity]에 저장하여, 다음번에 같은 값이 필요할 때 바로 사용 가능하도록 한다.

# Memoization Solution
# Time: O(n * m), Space: O(n * m)
# Where n is the number of items & m is the capacity.
def memoization(profit, weight, capacity):
    # A 2d array, with N rows and M + 1 columns, init with -1's
    N, M = len(profit), capacity
    cache = [[-1] * (M + 1) for _ in range(N)]
    return memoHelper(0, profit, weight, capacity, cache)

def memoHelper(i, profit, weight, capacity, cache):
    if i == len(profit):
        return 0
    if cache[i][capacity] != -1:
        return cache[i][capacity]

    # Skip item i
    cache[i][capacity] = memoHelper(i + 1, profit, weight, capacity, cache)

    # Include item i
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + memoHelper(i + 1, profit, weight, newCap, cache)
        # Compute the max
        cache[i][capacity] = max(cache[i][capacity], p)

    return cache[i][capacity]

 

메모이제이션과 브루트포스(완전 탐색)의 차이

처음 보면 메모이제이션 방식과 브루트포스 방식이 크게 다르지 않아 보일 수 있음.
그러나, 중요한 차이점이 존재한다.

1. 브루트포스(완전 탐색) 방식
   • 모든 가능한 조합을 고려 → 중복된 연산 발생
   • 시간 복잡도: O(2ⁿ) (최악의 경우)
   • 같은 i, capacity에 대해 중복 계산 발생
   • 비효율적이며 큰 입력에서는 실행 시간이 매우 길어질 수 있음
2. 메모이제이션 방식
   • 캐시를 사용하여 이미 계산된 값은 다시 계산하지 않음
   • 시간 복잡도: O(n * m) (아이템 개수 × 배낭 용량)
   • 즉, 중복된 하위 문제를 저장하고 재활용함으로써 실행 속도가 크게 향상됨

---

탑다운(Top-down) vs. 바텀업(Bottom-up) 방식

탑다운 (Top-down, Memoization)

• 재귀적 접근 (위에서 아래로 내려감)
• 캐시(cache[i][capacity])를 활용하여 이미 계산된 값을 저장
• 불필요한 재귀 호출을 줄여 성능을 최적화
• 그러나 재귀 호출이 많아지면 스택 오버플로우 가능성 존재

바텀업 (Bottom-up, Tabulation)

• 반복문을 활용한 동적 계획법(DP) 접근
• 작은 부분 문제를 먼저 해결한 후, 이를 활용해 최종 결과를 계산
• 재귀 호출이 없어서 스택 오버플로우 문제가 없음
• 더 직관적이고 최적화된 방식

 

Bottom-up dynamic programming approach

https://youtu.be/ejdvyf4SOUY

 

바텀업 DP 테이블 구성 방식

1. 테이블(배열)의 의미

• 행(row) → 각 아이템 (총 n 개)
• 열(column) → 배낭의 용량 (0 ~ capacity 까지 m + 1 개)
• dp[i][c]: 앞 i개의 아이템을 고려했을 때, 용량 c에서의 최대 이익

2. 초기화 (Base Case)

• 0번째 열 (capacity = 0)에서는 모든 값이 0
  • 이유: 어떤 아이템도 넣을 수 없으므로 최대 이익 = 0
• 0번째 행 (아이템이 없는 상태)에서도 모든 값이 0
  • 이유: 아이템이 없으면 최대 이익도 0

3. 상태 전이 (점화식)

각 dp[i][c] 값은 두 가지 선택 중 더 큰 값을 저장해야 한다.

1. 아이템을 포함하지 않는 경우 (skip)
   • 이전 행 값(dp[i-1][c])을 그대로 가져옴
   • 즉, 아이템을 추가하지 않으면, 이전 최적값을 유지
2. 아이템을 포함하는 경우 (include)
   • 현재 아이템의 **이익(profit[i])**을 추가
   • 하지만 배낭 용량이 충분해야 하므로, weight[i] <= c인 경우만 가능
   • **이전 최적해(dp[i-1][c-weight[i]])**를 이용해 최적값 갱신
   • 즉, 이전 행(i-1)에서 (c - weight[i])만큼 왼쪽으로 이동한 값과 현재 이익을 더함
   • 수식

4. 최종 결과

• 최종적으로 dp[n][capacity]에 배낭에 넣을 수 있는 최대 이익이 저장됨
• 하단 우측(dp[n][m])이 정답

 

# Dynamic Programming Solution
# Time: O(n * m), Space: O(n * m)
# Where n is the number of items & m is the capacity.
def dp(profit, weight, capacity):
    N, M = len(profit), capacity
    dp = [[0] * (M + 1) for _ in range(N)]

    # Fill the first column and row to reduce edge cases
    for i in range(N):
        dp[i][0] = 0
    for c in range(M + 1):
        if weight[0] <= c:
            dp[0][c] = profit[0]

    for i in range(1, N):
        for c in range(1, M + 1):
            skip = dp[i-1][c]
            include = 0
            if c - weight[i] >= 0:
                include = profit[i] + dp[i-1][c - weight[i]]
            dp[i][c] = max(include, skip)
    return dp[N-1][M]

 

 

 

 

개선된 메모리 최적화 접근

• 2D 배열(dp)을 사용하지 않고, 2개의 1D 배열(prev_row, curr_row)만 사용
• 각 행을 교대로 업데이트하면서 메모리를 절약

메모리 최적화: 2줄만 유지하는 방식 (O(2m) → O(m) 메모리)

이전 바텀업 DP 구현에서는 전체 2D 테이블 (dp[n][capacity+1])을 메모리에 유지했음.
그러나, 실제로는 두 개의 행만 필요하다!

• 현재 계산 중인 현재 행(current_row)
• 이전 단계에서 계산된 이전 행(previous_row)

# Memory optimized Dynamic Programming Solution
# Time: O(n * m), Space: O(m)
def optimizedDp(profit, weight, capacity):
    N, M = len(profit), capacity
    dp = [0] * (M + 1)

    # Fill the first row to reduce edge cases
    for c in range(M + 1):
        if weight[0] <= c:
            dp[c] = profit[0]

    for i in range(1, N):
        curRow = [0] * (M + 1)
        for c in range(1, M + 1):
            skip = dp[c]
            include = 0
            if c - weight[i] >= 0:
                include = profit[i] + dp[c - weight[i]]
            curRow[c] = max(include, skip)
        dp = curRow
    return dp[M]

시간 및 공간 복잡도 정리

1. 시간 복잡도 (Time Complexity)

• 바텀업 접근법에서 n개의 아이템과 m개의 용량을 고려하는 이중 반복문을 사용
  • for i in range(n) → 아이템 개수만큼 반복
  • for c in range(capacity + 1) → 배낭의 용량만큼 반복
  • 각 상태를 한 번만 계산하므로 O(n * m)

✅ 개선 효과:

• 재귀(탑다운) 방식에서는 중복 계산이 많아 O(2ⁿ) (지수 시간) 발생
• 바텀업 방식은 중복을 제거하여 O(n * m) (다항 시간)로 최적화됨

---

2. 공간 복잡도 (Space Complexity)

접근법	공간복잡	메모리 사용 방식
탑다운 (메모이제이션)	O(n * m)	2D 배열 (cache[i][c]) 유지
기본 바텀업 DP	O(n * m)	2D 배열 (dp[i][c]) 유지
1D 배열 최적화	O(m)	1D 배열 (dp[c]) 사용
이중 행 최적화	O(m)	2개의 1D 배열 (prev_row, curr_row)만 사용

✅ 공간 최적화:

• 1D 배열을 사용하면 O(n * m) → O(m) 으로 줄일 수 있음
• 현재 값만 유지하면 되므로, 전체 2D 배열을 저장할 필요 없음

---

마무리 (Closing Notes)

✅ 동적 계획법(DP) 문제는 처음에는 어려울 수 있지만, 연습을 통해 익숙해질 수 있음
✅ 코드를 보는 것만으로는 부족하며, 직접 풀어보는 것이 가장 중요함
✅ 면접에서 DP 문제를 풀 때는, 먼저 기본 접근법을 설명하고, 이후 최적화 방법을 추가로 제시하는 것이 좋음

🚀 연습 팁:

• 쉬운 DP 문제부터 연습 (Fibonacci, Climbing Stairs, Coin Change)
• 배낭 문제 변형 (Subset Sum, Partition Equal Subset Sum, Unbounded Knapsack)
• 면접에서는 공간 최적화(O(m))를 요구할 가능성이 높음 → 연습 필수

📌 "DP는 패턴을 익히고 직접 손으로 풀어봐야 확실히 이해할 수 있다!"