복잡도

DP의 복잡도 분석은 대체로 기계적입니다. 상태 수를 세고, 상태 하나당 하는 일을 세고, 두 값을 곱합니다. 이 장에서는 이 규칙을 고전 문제에 적용하고, 배낭 문제를 왜 의사 다항 시간이라고 부르는지, 메모이제이션과 타뷸레이션을 어떻게 비교하는지, 그리고 롤링 배열로 메모리를 줄이는 방법을 설명합니다.

기본 규칙

• 시간 = 상태 수 x 전이 하나의 비용
• 공간 = 동시에 메모리에 들고 있는 상태 수

피보나치는 상태가 n + 1개이고 각각 상수 시간이므로 O(n)입니다. LCS는 상태가 (n + 1)(m + 1)개이고 각각 상수 시간이므로 O(nm)입니다. 동전 종류가 k개인 동전 교환은 amount + 1개의 상태가 각각 동전 k개를 살피므로 O(amount x k)입니다.

고전 문제 한눈에 보기

DP에는 최선과 최악의 경우가 따로 있는 일이 드뭅니다. 입력 값과 상관없이 표를 끝까지 채우기 때문입니다. 다만 메모이제이션은 시작 상태에서 도달하는 상태가 일부뿐일 때 실제로 더 빠를 수 있습니다.

의사 다항 시간

배낭 문제의 O(n x W)는 다항식처럼 보이지만, W는 입력의 길이가 아니라 수의 크기입니다. W를 적는 데는 약 log2(W)비트면 충분하므로 입력에 비트 하나만 더해도 실행 시간이 두 배가 될 수 있습니다. 이런 알고리즘을 의사 다항 시간(pseudo-polynomial) 알고리즘이라고 합니다. 0/1 배낭 문제는 일반적으로 NP-난해이며, DP는 용량이 적당히 작은 정수일 때만 실용적입니다. W가 매우 크고 n이 40개 정도로 작다면 반씩 나누어 열거하는 meet-in-the-middle 방식이 더 나은 경우가 많습니다.

메모이제이션과 타뷸레이션 비교

Python에서 가장 흔히 놀라는 부분은 재귀 제한입니다. 상태가 수천 개 이어진 메모이제이션 함수는 RecursionError를 내고, sys.setrecursionlimit으로 한도를 올려도 해결되지 않을 수 있습니다. 최근 Python은 C 코드를 거치는 호출의 깊이도 따로 제한하는데, functools.cache 래퍼가 C로 작성되어 있기 때문입니다. 간단한 우회 방법은 작은 값부터 차례로 호출해 캐시를 미리 채우는 것입니다. 그러면 각 호출이 필요한 작은 상태를 이미 캐시에서 찾습니다.

from functools import cache


@cache
def ways(n: int) -> int:
    """1칸 또는 2칸씩 n칸 계단을 오르는 방법의 수"""
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


try:
    ways(5_000)
except RecursionError:
    print("too deep")

for i in range(5_001):  # 미리 채우기: 호출마다 재귀가 한 단계뿐
    ways(i)
print(ways(5_000) % 1_000_000_007)
print(ways.cache_info().currsize)  # 상태 5001개 저장

미리 채우기는 사실상 상향식 계산을 돌려서 한 것입니다. 상태가 수만 개라면 처음부터 반복문으로 작성합니다.

롤링 배열

표의 한 행이 바로 이전 행에만 의존한다면 두 행 이상을 들고 있을 필요가 없습니다. 다음은 LCS 길이를 O(min(n, m)) 공간으로 구하는 코드입니다.

def lcs_length(a: str, b: str) -> int:
    if len(b) > len(a):
        a, b = b, a  # 짧은 쪽을 b로
    prev = [0] * (len(b) + 1)
    for ch in a:
        cur = [0] * (len(b) + 1)
        for j, bj in enumerate(b, start=1):
            cur[j] = prev[j - 1] + 1 if ch == bj else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


print(lcs_length("ABCBDAB", "BDCABA"))  # 4

대신 두 행만 남기면 표를 거꾸로 따라가 부분 수열을 복원할 수 없습니다. Hirschberg 알고리즘은 분할 정복을 이용해 선형 공간에서 복원까지 해내며, 시간은 대략 두 배가 듭니다.

상태 정의를 바꿔 더 빠르게

상태를 더 잘 정의하면 복잡도 등급 자체가 바뀌기도 합니다. 단순한 LIS 점화식은 앞의 모든 위치를 살피므로 O(n^2)입니다. 길이마다 "가능한 가장 작은 끝 값"을 들고 있으면 안쪽 반복문을 이분 탐색으로 바꿀 수 있습니다.

from bisect import bisect_left


def lis_length(nums: list[int]) -> int:
    tails: list[int] = []  # tails[k] = 길이 k + 1인 증가 수열의 가장 작은 끝 값
    for x in nums:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)


print(lis_length([3, 1, 4, 1, 5, 9, 2, 6]))  # 4, 예: 1, 4, 5, 9

tails는 늘 정렬된 상태를 유지하므로 원소 하나에 O(log n), 전체는 O(n log n)입니다.

다른 접근과 비교

정리

• 시간은 상태 수 x 전이 비용, 공간은 동시에 들고 있는 상태 수입니다.
• 배낭 DP는 W의 수 크기에 의존하므로 의사 다항 시간입니다.
• 메모이제이션은 도달하는 상태만 계산하지만 재귀 비용을 치르고, 타뷸레이션은 예측 가능하며 최적화하기 쉽습니다.
• 롤링 배열은 메모리를 한두 행으로 줄이는 대신 복원을 포기합니다.