동적 프로그래밍으로 Knapsack 문제의 상태 전이 설계하기

상태와 전이가 맞물릴 때 동적 프로그래밍이 성립한다

동적 프로그래밍(Dynamic Programming, DP)은 같은 부분 문제가 반복되고, 그 부분 해를 조합해 전체 최적해를 만들 수 있을 때 계산 결과를 저장해 재사용하는 알고리즘 패러다임이다.

설계의 중심에는 상태(state), 전이(transition), 기저(base) 조건이 있다. 상태는 문제를 구분하는 최소 파라미터로 정하고, 전이는 기존 상태로 현재 상태를 구하는 점화식으로 만든다. 계산한 값은 캐시나 테이블에 저장한다.

계산 순서는 크게 메모이제이션과 바텀업으로 나뉜다. 전자는 재귀와 캐시를 결합하고, 후자는 반복문으로 테이블을 채운다.

필요한 상태만 탐색하는 메모이제이션

메모이제이션은 재귀 호출로 도달한 상태만 계산한 뒤 해시나 배열 캐시에 보관한다. 상태 공간 가운데 실제로 필요한 일부만 방문한다면 불필요한 계산을 피할 수 있고, 점화식을 코드로 옮기기도 비교적 간결하다.

대신 재귀 깊이가 커지면 스택 오버플로 위험이 생긴다. 캐시 키가 상태 정의와 정확히 맞는지도 관리해야 한다.

순서를 정해 테이블을 채우는 바텀업

바텀업 DP는 작은 상태에서 큰 상태로 이어지는 순서를 먼저 정한 뒤 테이블을 반복적으로 갱신한다. 호출 스택을 쓰지 않고, 메모리 접근 패턴을 예상하기 쉽다는 장점이 있다.

반면 테이블 전체를 채우는 방식이라 결과에 필요하지 않은 상태까지 계산할 수 있다. 입력 범위와 상태 공간이 충분히 명확할 때 선택하기 좋다.

Knapsack에서 상태를 정의하는 방법

0/1 Knapsack에서는 아이템을 어디까지 고려했는지와 남은 용량이 상태를 구성한다. 예를 들어 i번째 아이템까지 고려하고 현재 용량이 W인 상황을 상태로 둘 수 있다.

각 상태에서는 아이템을 선택하지 않는 경우와 선택하는 경우를 비교한다. 선택 가능하다면 이전 상태의 가치에 해당 아이템의 가치를 더하고, 그렇지 않으면 미선택 상태를 유지한다. 기저 상태도 함께 정해야 한다.

전이가 인접 상태에만 의존하면 1차원 롤링 배열로 공간을 O(W)까지 줄일 수 있다. 실제 선택 집합이 필요하면 parent 또는 take 테이블을 보관하거나, 전이 조건을 다시 검사해 역추적한다.

음수 가중치와 음수 용량은 허용하지 않으며, 입력 정합성을 확인해야 한다. W가 매우 큰 경우에는 값 기반 DP를 검토할 수 있다.

⤢✕

Python으로 구현하는 0/1 Knapsack

Python 3.10+를 전제로 하며, weights와 values의 길이는 같아야 한다. 두 값은 비음수 정수이고 용량 W는 0 이상 정수여야 한다.

메모이제이션 구현은 필요한 상태를 재귀로 계산한다.

from functools import lru_cache
from typing import List

def knapsack_td(weights: List[int], values: List[int], W: int) -> int:
    n = len(weights)
    if n != len(values):
        raise ValueError("weights와 values 길이 불일치")
    if W < 0 or any(w < 0 for w in weights) or any(v < 0 for v in values):
        raise ValueError("음수 입력 불가")

    @lru_cache(maxsize=None)
    def dp(i: int, cap: int) -> int:
        # 기저
        if i == n or cap == 0:
            return 0
        # 미선택
        best = dp(i + 1, cap)
        # 선택
        w, v = weights[i], values[i]
        if w <= cap:
            best = max(best, v + dp(i + 1, cap - w))
        return best

    return dp(0, W)

# 예시
# print(knapsack_td([3, 4, 5], [30, 50, 60], 8))  # 90

바텀업 방식에서 0/1 특성을 유지하려면 용량 축을 역순으로 순회해야 한다.

from typing import List

def knapsack_bu_1d(weights: List[int], values: List[int], W: int) -> int:
    n = len(weights)
    if n != len(values):
        raise ValueError("weights와 values 길이 불일치")
    if W < 0 or any(w < 0 for w in weights) or any(v < 0 for v in values):
        raise ValueError("음수 입력 불가")

    dp = [0] * (W + 1)  # dp[c]: 용량 c에서의 최대 가치
    for w, v in zip(weights, values):
        # 0/1 특성 보장: 역순 순회
        for c in range(W, w - 1, -1):
            cand = dp[c - w] + v
            if cand > dp[c]:
                dp[c] = cand
    return dp[W]

# 예시
# print(knapsack_bu_1d([3, 4, 5], [30, 50, 60], 8))  # 90

용량 W가 지나치게 큰 경우에는 아이템 가치 합 ΣV를 기준으로 상태를 구성할 수 있다. 최대 가치마다 필요한 최소 무게를 구한 뒤, W 이하로 가능한 최대 가치를 선택한다. 아이템 가치 합 ΣV가 실용 범위일 때 사용할 수 있으며 시간 복잡도는 O(n·ΣV)다.

from math import inf
from typing import List

def knapsack_value_dp(weights: List[int], values: List[int], W: int) -> int:
    if len(weights) != len(values):
        raise ValueError("길이 불일치")
    if W < 0 or any(w < 0 for w in weights) or any(v < 0 for v in values):
        raise ValueError("음수 입력 불가")

    maxV = sum(values)
    dp = [inf] * (maxV + 1)
    dp[0] = 0
    for w, v in zip(weights, values):
        for val in range(maxV, v - 1, -1):
            if dp[val - v] + w < dp[val]:
                dp[val] = dp[val - v] + w
    # W 이하 무게로 달성 가능한 최대 가치
    for val in range(maxV, -1, -1):
        if dp[val] <= W:
            return val
    return 0

선택 집합까지 복원해야 한다면 바텀업 2차원 dp와 take 테이블을 유지하고, i=n부터 역추적한다.

접근 방식별 복잡도와 제약

접근법	시간복잡도(일반)	Knapsack 시간복잡도	공간복잡도	안정성(스택)	구현 난이도	특징
순진 재귀	지수적	O(2^n)	O(n)	낮음	낮음	중복 계산 다수
메모이제이션	상태×전이	O(nW)	O(상태 수)	중간(깊이 의존)	낮음~중간	필요한 상태만 계산
바텀업(Tabulation)	상태×전이	O(nW)	O(W) 또는 O(nW)	높음	중간	순차 메모리 접근, 캐시 예측 용이

W가 매우 크면 O(nW)는 비현실적일 수 있다. 이때는 값 기반 DP 또는 근사 알고리즘을 고려한다.

자원 배분 문제에서 얻는 운영상 이점

동적 프로그래밍은 SKU 묶음 구성, 마케팅 채널 예산 배분, 프로젝트 포트폴리오 선택처럼 제한된 자원에서 선택을 최적화하는 문제에 적용할 수 있다. VM과 컨테이너 패킹, 스팟과 온디맨드를 섞는 비용-성능 최적화, 제한된 자원에서의 규칙 세트 선택에도 같은 구조를 사용할 수 있다.

순진 재귀와 비교하면 수천~수십만 배 가속할 수 있으며, n=100, W=10^4에서는 O(nW)로 계산할 수 있다. 1차원 롤링 배열을 적용하면 메모리는 O(W)로 줄어든다. 다만 n·W가 10^8 이상이면 메모리와 시간 압박을 경계해야 한다.

경계와 기저 조건을 명시하면 결정적 결과를 안정적으로 낼 수 있다. 반복형 바텀업은 스택 한계와 무관하므로 대용량 입력에서 유리하다.