동적계획법으로 최적화 문제의 상태와 전이를 설계하는 법

같은 계산을 반복하지 않도록 문제를 설계한다

동적계획법(Dynamic Programming)은 최적화 문제를 더 작은 하위 문제로 나눈 뒤, 이미 구한 부분 해를 저장해 다시 쓰는 알고리즘 기법이다. 조합적 폭발을 억제하면서 일관된 최적해를 구할 수 있어 금융, 공급망, 네트워크, 광고, 바이오인포매틱스 등에서 활용된다.

이 접근이 성립하려면 두 조건이 필요하다. 같은 하위 문제가 반복해서 나타나는 중복 부분 문제와, 부분 문제의 최적해를 조합해 전체 최적해를 만들 수 있는 최적 부분 구조다. 계산 시간과 저장 공간을 맞바꾸는 시간-공간 트레이드오프도 전제한다.

문제를 나눌 때는 다음 요소가 분명해야 한다.

• 상태는 의사결정 시점, 용량·예산·시간 같은 자원, 아이템·단계 같은 인덱스로 구성한다.
• 전이 규칙, 즉 점화식은 현재 상태를 이전 상태의 최적값으로 표현한다.
• 경계 조건은 초기값과 베이스 케이스를 정해 전이가 안정적으로 수렴하도록 만든다.

상태 공간은 작되 충분해야 한다

상태에는 의사결정에 필요한 변수만 남겨야 한다. 불필요한 차원을 없애면 상태 공간을 줄일 수 있지만, 필요한 정보를 빼면 올바른 전이를 만들 수 없다. 전이 규칙을 세울 때는 단조성, 분할 가능성, 무기억성을 확인해 최적 부분 구조가 성립하는지 검토한다.

계산 순서는 크게 두 방식으로 나뉜다.

메모이제이션은 재귀 호출을 통해 필요한 상태만 계산하는 하향식 방식이다. 희소한 상태 공간에 유리하지만 호출 스택 한계와 캐시 정책을 고려해야 한다. 타뷸레이션은 반복문으로 상태 테이블을 채워 가는 상향식 방식이며, 메모리 접근 지역성이 좋고 전체 상태를 다루는 전역 최적화에 적합하다.

전이가 인접한 상태에만 의존하면 롤링 배열을 사용해 O(NK) 공간을 O(K)로 줄일 수 있다. 비트셋, 좌표압축, 희소 테이블도 메모리 풋프린트를 관리하는 방법이다. 최적값만으로 끝나지 않고 실제 의사결정 경로가 필요하다면 역추적 포인터, 선택 마킹, 차분 비교를 이용해 해를 복원한다.

상태 폭이 너무 커질 때는 근사 동적계획(ADP), 가치 반복의 조기 종료, 프루닝, 도메인 휴리스틱을 적용할 수 있다. 이때는 품질과 속도의 트레이드오프를 운영 요구사항에 맞춰 관리한다.

목표 함수에서 운영 검증까지 이어지는 흐름

입력 단계에서 목표 함수, 제약, 데이터 도메인을 확정한다. 이어 최소 상태, 점화식, 순회 순서를 설계하고 불능 상태·무한대 대체값·빈 해에 대한 초기값을 정한다. 하향식에서는 캐시 적중률을, 상향식에서는 테이블 채움 순서를 확인하면서 계산한다. 마지막에는 정책을 추출하고 샘플 검증, 제약 위반 검사와 리페어를 수행한다.

⤢✕

불가능한 상태나 무한대는 sentinel 값으로 다루고, 오버플로를 막기 위한 클램핑을 적용한다. 캐시가 메모리 한계를 넘으면 상태 압축, 희소 구조, 체크포인팅 또는 스트리밍 전환을 검토한다. 재귀 깊이가 문제가 되는 환경에서는 반복형으로 변환하거나 꼬리재귀를 제거하고 스택 크기를 조정한다.

그리디와 분할정복 사이에서 보는 동적계획법

접근	성능(복잡도)	확장성(차원 증가)	일관성(최적성)	안정성(수렴/재현)	운영 편의(튜닝)
동적계획법	지수→다항 변환 가능, 캐시 의존	차원 저주 영향 큼, 압축 필요	전역 최적 보장(가정 충족 시)	초기값·전이 명확 시 안정	상태 설계 난도 높음, 검증 용이
그리디	매우 빠름, 선형~로그선형	매우 우수	문제 의존, 종종 근사	단순, 노이즈에 민감도 낮음	튜닝 용이, 근거 설명 쉬움
분할정복	로그/선형로그~다항	병렬성 우수	최적성은 문제 의존	구현 단순	메모리/스택 관리 필요

동적계획법은 가정이 충족되면 전역 최적해를 보장할 수 있지만, 상태 차원이 늘수록 차원 저주의 영향을 크게 받는다. 상태 설계의 난도는 높아도 상태·전이·경계가 명시되어 검증과 설명은 수월하다.

제약을 상태에 넣는 산업별 활용

공급망의 재고·생산 계획에서는 기간 t, 잔여 재고 r, 생산 여부 y를 상태로 둘 수 있다. 수요와 생산·보관 비용으로 전이하며, 백오더와 폐기를 포함한 총비용 최소화가 목표다. 생산능력, 리드타임, 안전재고 제약을 반영하고 타뷸레이션, 롤링 배열, 시나리오 기반 확률 DP를 활용한다.

포트폴리오 리밸런싱과 리스크 예산에서는 시점 t, 사용 예산 b, 리스크 버킷 k가 상태가 된다. 기대수익·분산·거래비용을 전이에 반영해 효용을 최대화하거나 CVaR 제약하에서 수익 최대화를 구한다. 근사 DP, 컷 생성, 팩터 노출에 따른 상태 축소가 사용된다.

광고 입찰과 캠페인 예산 배분은 남은 예산 B, 시간 슬롯 s, 채널 c를 상태로 삼는다. CTR/CVR 예측과 빈도 캡을 전이에 반영하고, 지출 상한과 페이싱 제약 아래 전환 또는 ROI를 최대화한다. Top-down 메모이제이션과 온라인 업데이트를 위한 캐시 만료 정책을 적용할 수 있다.

0/1 배낭 문제를 상향식으로 구현하기

전제조건: Python 3.10+, 입력 무게/가치는 비음수, 용량은 정수.

from typing import List, Tuple

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> Tuple[int, List[int]]:
    """
    0/1 Knapsack - Bottom-up DP.
    Returns (max_value, selected_indices in ascending order).
    Time: O(n*W), Space: O(n*W); can be reduced to O(W) without path reconstruction table.
    """
    n = len(weights)
    if n != len(values):
        raise ValueError("weights/values 길이 불일치")
    if capacity < 0:
        raise ValueError("capacity는 음수가 아님")

    # dp[i][c]: 첫 i개 고려, 용량 c에서의 최대 가치
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            if w <= c:
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)
            else:
                dp[i][c] = dp[i - 1][c]

    # 경로 복원
    selected = []
    c = capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            selected.append(i - 1)
            c -= weights[i - 1]
    selected.reverse()
    return dp[n][capacity], selected

if __name__ == "__main__":
    W, V, C = [2, 3, 4, 5], [3, 4, 5, 6], 5
    best, items = knapsack_01(W, V, C)
    print(best, items)  # 7 [0,1]

가치만 필요하다면 1차원 dp[c]를 사용하고 c를 역순으로 순회해 공간을 줄일 수 있다. 대규모 인스턴스에서는 상태 압축과 근사화(라운딩·그리디 시드)를 병행하며, 메모리 모니터링과 체크포인팅을 적용한다.

성능 개선과 운영상 이점

백트래킹의 O(2^n)는 문제에 따라 O(nW) 또는 O(n^2) 수준으로 낮출 수 있고, 10배~10^6배 속도 개선이 가능하다. 가정이 충족되면 전역 최적성을 일관되게 확보할 수 있으며, 리그레션 테스트로 재현성을 관리한다.

상태, 전이, 경계 조건이 드러나므로 설계 검증과 설명이 쉬워진다. 캐시와 테이블 기반의 계산은 노이즈 내성을 높이고, 점진적 개선과 튜닝 범위를 명확하게 만든다.