Python - < 12 >

개요

마트 세 곳을 돌며 우유 최저가를 메모지에 적는다고 해보자. 동적 계획법( DP )에서 표의 한 칸에 최솟값을 채우는 일이 이 메모지와 같다. 첫 가게에서는 가격을 그냥 적고, 두 번째 가게부터는 더 쌀 때만 고쳐 적는다. 다 돌고 나면 메모지에 남은 건 마지막에 본 가격이 아니라 최저가다.

같은 메모지를 다음 날 또 들고 나가면 얘기가 달라진다. 첫 가게라고 그냥 덮어쓰면 어제 찾은 최저가가 지워지니, 첫 가게부터 어제 값과 비교해야 한다.

수영장 문제 코드를 고치다가 dp[i]에 첫 후보를 비교 없이 대입하는 줄에서 멈췄다. 이러면 최솟값이 아니라 최신 값만 남는 거 아닌가..?

이번 글에서 헷갈렸던 지점은 대부분 같은 질문으로 돌아갔다. 테이블의 한 칸을 언제, 몇 번 건드리는가. 1차원으로 줄인 배열을 어느 방향으로 도는지, 루프 두 줄의 순서가 순열과 조합을 가르는지도 이 질문이다.

메모이제이션도 DP다

재귀 피보나치의 총 호출 수 C(n)은 두 하위 호출에 자기 자신 한 번을 더한 값이다.

C(n) = C(n-1) + C(n-2) + 1   →   C(n) = 2·F(n+1) − 1

n이 1 늘 때마다 호출이 약 1.618배( 황금비 φ )로 늘어서 O(φⁿ)이고, 흔히 쓰는 O(2ⁿ)은 느슨한 상한이다. fibo(40) 한 번에 약 3.3억 번 호출된다.

호출이 이렇게 불어나는 건 같은 하위 문제를 여러 번 풀기 때문이다. f(5)는 f(4)와 f(3)을 부르는데, f(4)도 안에서 f(3)을 또 부른다.

메모를 붙이면 한 번 계산한 값은 꺼내 쓰기만 해서 호출이 O(n)으로 줄어든다. 이때 fibo_memo(5)가 memo에 값을 저장하는 순서는 memo[2] → memo[3] → memo[4] → memo[5]로, 반복문으로 짠 fibo_dp(5)가 dp[2]부터 dp[5]까지 채우는 순서와 같다( base case n <= 1은 저장되지 않는다 ). 재귀가 위에서 출발해도 값이 확정되는 순서는 아래부터다.

흔히 “분할 정복은 하향식, DP는 상향식”이라고 소개하지만 단순화된 표현이다. DP를 가르는 기준은 방향이 아니라 겹치는 하위 문제를 한 번만 계산해 재사용하느냐다. 병합 정렬도 문제를 반씩 나누지만, 부분 문제 [l, r]이 전부 서로 다른 구간이라 메모를 붙여도 한 번도 다시 꺼낼 일이 없다. 겹침이 없으니 저장 비용만 늘어난다.

메모이제이션에도 약점이 있다. 첫 호출에서는 memo가 비어 있어서 f(n) → f(n-1) → … → f(1)로 한 줄로 내려가니, 호출 수가 O(n)이어도 재귀 깊이는 n 그대로다. 파이썬 기본 재귀 한도는 1000이라 fibo_memo(10000)은 RecursionError가 난다. sys.setrecursionlimit()으로 한도를 올려도 실제 스택 크기는 운영체제가 정하니, 반복문으로 표를 채우는 bottom-up이 해결책이다.

	Top-down ( memoization )	Bottom-up ( tabulation )
계산 순서	재귀가 찾아 줌	직접 정해야 함
계산 범위	필요한 하위 문제만	테이블 전체
위험	재귀 깊이	순서를 잘못 잡으면 빈 칸 참조

“빈 칸 참조”가 이 글 후반부의 주제다. 1부터 N²까지 한 줄로 이어진 경로에서 재귀 깊이가 100만까지 내려가던 사례는 Python - < 11 >의 정사각형 방 문제에 있다.

메모의 key에는 결과를 바꾸는 입력이 전부 들어가야 한다

파이썬 기본 인자 값은 def가 실행될 때 한 번만 만들어진다. memo={}로 두면 그 함수의 모든 호출이 같은 dict를 공유한다 ( C++ 기본 인자는 호출마다 새로 평가된다 ).

피보나치처럼 결과가 n에만 달린 함수라면 공유가 오히려 이득이다. functools.lru_cache를 붙인 것과 같은 효과가 난다. 동전이 입력에 끼면 사정이 다르다.

def coin_change(amount, coins, memo={}):
    if amount == 0:                 # 0원은 동전 0개
        return 0
    if amount in memo:              # key가 amount뿐이다
        return memo[amount]
    best = amount + 1               # 나올 수 없는 값으로 시작 ( 아래 동전 절 참고 )
    for c in coins:
        if c <= amount:
            best = min(best, coin_change(amount - c, coins, memo) + 1)
    memo[amount] = best
    return best

print(coin_change(6, (1, 3, 4)))    # 2  ( 3 + 3 )
print(coin_change(6, (1,)))         # 2  ← 1원짜리만으로는 6개가 맞다

두 번째 호출은 동전 구성이 바뀌었는데도 첫 호출이 남긴 memo[6]을 그대로 꺼낸다. 결과에 영향을 주는 입력이 amount와 coins 둘인데 key에는 하나만 들어갔다. key를 (amount, coins)로 잡거나, memo=None으로 받아 호출마다 새로 만들면 된다.

캐시 key = 결과에 영향을 주는 모든 입력. 다음 절의 토끼 문제도 같은 원칙이 DP 상태 설계에서 나타난 경우다.

규칙이 하나 늘면 상태도 하나 는다 — 토끼가 죽기 시작하면

피보나치 토끼 문제의 점화식 f(n+2) = f(n+1) + f(n)은 외울 식이 아니라 규칙을 옮겨 적은 것이다.

• f(n+1): 아무도 죽지 않으니 지난달 토끼가 그대로 있다
• f(n): n월에 살아 있던 토끼는 n+2월이면 전부 번식할 수 있다

여기에 “태어난 지 3달 후 죽는다”를 더해 보자. 먼저 떠오르는 건 죽는 쌍만큼 빼는 f(n+2) = f(n+1) + f(n) − f(n-3) 같은 식이다. 그런데 f(n-3)은 n-3월에 살아 있던 전체 수라서, 그달에 막 태어난 쌍만 빼야 하는 자리에 나이 든 쌍까지 같이 빠진다. 번식 항 f(n)도 이제는 죽은 쌍을 포함해서 같이 틀어진다.

살아 있는 수 f(n) 하나로는 다음 달을 계산할 정보가 모자란다. 나이별로 상태를 나눈다.

a(n) = 갓 태어난 쌍,  b(n) = 1살,  c(n) = 2살

b(n+1) = a(n)            // 갓 태어남 → 1살
c(n+1) = b(n)            // 1살 → 2살
a(n+1) = c(n+1) = b(n)   // 2살이 된 쌍이 그 달에 번식
                         // c(n)은 다음 칸으로 넘기지 않는다 = 죽음

죽는 쌍은 빼는 게 아니라 다음 칸으로 넘기지 않는다. dp[n][나이] 같은 다차원 DP 테이블이 이 구조에서 출발한다. 앞 절의 coin_change가 동전 구성을 key에서 빠뜨려 틀렸듯, 결과를 바꾸는 정보( 나이 )가 상태에 없으면 점화식을 아무리 고쳐도 맞지 않는다.

최적 부분 구조 — 최장 경로가 DP로 안 풀리는 이유

DP에는 두 조건이 필요하다. 하위 문제가 겹쳐야 하고( 중복 부분문제 ), 하위 문제의 최적해를 조합하면 전체 최적해가 돼야 한다( 최적 부분 구조 ). 둘 다 “하위 문제끼리 독립/연관”이라는 말로 설명돼서 헷갈리기 쉽다.

	하위 문제끼리 공유하나?	한 하위 문제의 선택이 다른 쪽을 방해하나?
DP에 필요한 조건	공유해야 함 ( 중복 부분문제 )	방해하면 안 됨 ( 최적 부분 구조 )
병합 정렬	공유 X → DP 의미 없음	방해 X
최장 단순 경로 ( 사이클 있음 )	—	방해 O → DP 불가

간선이 A–B 1, B–C 2, A–C 1, B–D 2인 무방향 그래프에서 A→D 최장 단순 경로는 A→C→B→D( 5 ), A→C 최장 단순 경로는 A→B→C( 3 )다. 최단 경로라면 “A→D 최적 경로 속 A→C 구간은 A→C 최적 경로”가 성립한다. 최장 경로에서 그렇게 바꿔 끼우면 A→B→C→B→D가 되어 B를 두 번 지난다.

같은 정점을 두 번 지나려면 사이클이 필요하니, 사이클이 없는 방향 그래프( DAG )에서는 이 충돌이 없다. 들어오는 간선의 출발점이 모두 끝난 정점부터 차례로( 위상 정렬 순서 ) longest[v] = max(longest[u] + w(u, v))를 채우면 된다. 게임의 테크 트리에서 선행 조건을 전부 채우는 데 걸리는 최소 시간이 이 계산이다.

1차원으로 줄이면 순회 방향이 생긴다

이항계수 B[i][j] = B[i-1][j-1] + B[i-1][j]( 파스칼 삼각형 )는 바로 윗줄만 읽는다. 테이블 전체가 아니라 prev, cur 두 줄이면 충분하고, 범위 밖을 0으로 두면 j == i 같은 경계 예외 처리도 사라진다. 그래픽스의 더블 버퍼링, 라이프 게임의 세대 버퍼와 같은 구조다.

한 줄로 합치면 문제가 생긴다. 새 row[j]는 옛 row[j-1] + 옛 row[j]인데, row[j]를 덮어쓰는 순간 그 칸의 옛 값이 사라진다.

[1, 2, 1, 0]에서 다음 줄을 만드는 과정을 칸마다 적으면

앞에서부터: row[1] = 1 + 2 = 3
            row[2] = 3 + 1 = 4    ← row[1]이 이미 새 값 3
            row[3] = 4 + 0 = 4    → [1, 3, 4, 4]  오염이 연쇄된다

뒤에서부터: row[3] = 1 + 0 = 1
            row[2] = 2 + 1 = 3
            row[1] = 1 + 2 = 3    → [1, 3, 3, 1]

j를 뒤에서부터 돌리면 row[j]를 계산할 때 row[j-1]이 아직 옛 값으로 남아 있다. 읽어야 할 칸이 아직 갱신되지 않은 쪽에 남도록 순회 방향을 정한다. 이 규칙은 아래 햄버거 문제에서 다시 나온다.

이항계수는 팩토리얼 대신 덧셈으로

C(30, 15) = 155,117,520은 32비트 int에도 들어가는 크기다. 그런데 n! / (r!(n−r)!)으로 구하면 중간값 30!을 거쳐야 한다. C++ long long은 20!( 약 2.43 × 10¹⁸ )까지 담고 21!( 약 5.1 × 10¹⁹ )에서 넘친다. C++에서 부호 있는 정수 overflow는 undefined behavior다.

그럼 mod를 먼저 걸면 될까. 곱셈과 덧셈은 mod를 중간에 걸어도 되지만 나눗셈은 안 된다.

C(5, 2) % 7 = 10 % 7 = 3
(5! % 7) / ((2! · 3!) % 7) = 1 / 5   ← 정수도 아니다

파스칼 점화식은 덧셈만 쓴다. 중간값이 전부 그 자체로 이항계수라 답보다 커지지 않고, 매 단계 % M을 걸어도 결과가 맞는다. 앞 절의 한 줄 배열을 그대로 쓴다.

def binom(n, r, M):
    row = [0] * (r + 1)                       # C(i, 0..r) 한 줄
    row[0] = 1                                # C(0, 0) = 1
    for i in range(1, n + 1):
        for j in range(min(i, r), 0, -1):     # 뒤에서부터 갱신
            row[j] = (row[j - 1] + row[j]) % M
    return row[r]

print(binom(30, 15, 10**9 + 7))   # 155117520
print(binom(5, 2, 7))             # 3

mod 안에서 나눗셈이 꼭 필요하면 나누는 대신 곱하는 수로 바꾼다. M이 소수면 페르마 소정리에 따라 a^(M−1) ≡ 1 (mod M)이라, a^(M−2)를 곱하는 게 a로 나누는 것과 같다( 모듈러 역원 ).

동전 거스름돈 — 루프 두 줄의 순서가 순열과 조합을 가른다

그리디가 맞는 동전 체계

10·50·100·500원처럼 동전끼리 배수 관계면 큰 동전부터 쓰는 그리디가 최적이다. 배수 관계가 필수 조건은 아니라서 1·5·10·25센트도 그리디가 최적이고, 1·3·4원이면 6원을 그리디가 4+1+1( 3개 )로 내지만 최적은 3+3( 2개 )이다. 그리디가 항상 최적인 체계를 canonical coin system이라고 하는데, 간단한 산술 조건 하나로 판정되지 않아서 금액별로 그리디와 DP 최적해를 비교해 확인한다.

sentinel은 amount + 1

최소 동전 수 테이블은 “만들 수 없음”을 표시할 큰 값으로 채우고 시작한다. 최소 동전 수는 아무리 커도 amount( 1원짜리만 쓸 때 )라 amount + 1은 절대 답으로 나오지 않고, 여기에 +1을 해도 넘치지 않는다.

C++에서 INT_MAX를 쓰면 dp[x - c] + 1이 INT_MAX + 1이 되면서 보통 INT_MIN으로 넘어가고, 이게 min()에서 이겨 테이블을 오염시킨다. 더하기 전에 INF인지 검사하거나 1e9, 0x3f3f3f3f처럼 더해도 여유가 있는 값을 쓴다. sentinel은 절대 나올 수 없는 값이면서 연산 후에도 넘치지 않는 값이어야 한다.

방법의 수 — 같은 코드, 다른 답

{1, 2}원으로 3원을 만드는 방법의 수를 센다. 두 코드는 루프 두 줄의 순서만 다르다.

coins = (1, 2)
amount = 3

# 금액 바깥, 동전 안쪽
ways = [1] + [0] * amount           # ways[0] = 1: 아무것도 안 고르는 방법 하나
for a in range(1, amount + 1):
    for c in coins:
        if c <= a:
            ways[a] += ways[a - c]  # 마지막에 c를 놓는 방법 수를 더한다
print(ways[amount])                 # 3

# 동전 바깥, 금액 안쪽
ways = [1] + [0] * amount
for c in coins:
    for a in range(c, amount + 1):
        ways[a] += ways[a - c]
print(ways[amount])                 # 2

• 금액 바깥 → 3 ( 1+1+1, 1+2, 2+1 ). 금액마다 어떤 동전이든 마지막에 놓을 수 있어서 놓는 순서가 다르면 다른 방법으로 센다. 순열이다.
• 동전 바깥 → 2 ( 1+1+1, 1+2 ). 동전 종류를 하나씩 허가하니 모든 방법이 “1들 먼저, 그다음 2들” 순서로만 만들어진다. 2+1은 만들어질 길이 없다. 조합이다.

개요의 질문으로 보면 차이는 ways[3]에 몇 번 오느냐다. 금액이 바깥이면 ways[3]에는 딱 한 번 오고, 그 한 번에 모든 동전을 “마지막 동전” 후보로 본다. 동전이 바깥이면 ways[3]에 동전마다 다시 오고, 올 때마다 그 동전 하나로 만드는 방법만 더한다.

한 번만 오는 구조는 아래 수영장 문제와, 여러 번 오는 구조는 햄버거( 배낭 ) 문제와 모양이 같다.

마트 통로를 한 방향으로만 지나가며 담으면, 무엇을 담았든 담은 순서는 통로 순서 하나로 고정된다. 게임으로 치면 순서가 중요한 커맨드 입력( ↓↘→ + P )과 순서가 상관없는 크래프팅 재료의 차이다.

SWEA 5215 햄버거 다이어트 — 칼로리를 거꾸로 도는 이유

문제. 재료 N개( N ≤ 20 )마다 맛 점수와 칼로리가 있다. 각 재료는 한 번씩만 쓸 수 있고, 칼로리 합이 L 이하가 되도록 골라 맛 점수 합을 최대로 만든다. 그 최댓값을 출력한다.

재료를 넣거나 안 넣거나 둘 중 하나인 0/1 배낭이다. dp[c]를 칼로리 c에서의 최대 맛 점수로 두고, 재료마다 dp[c] = max(dp[c], dp[c - cal] + taste)로 갱신한다.

1차원 배열 하나로 갱신하니 파스칼 절의 순회 방향 문제가 그대로 나온다( 위 그림의 앞에서부터 쪽 ). 칼로리를 작은 쪽부터 돌면 dp[c - cal]이 이번 재료를 이미 넣은 값일 수 있어서, 같은 재료를 여러 번 넣는 무제한 배낭이 된다. 큰 쪽부터 돌아야 dp[c - cal]이 아직 이번 재료를 안 본 값으로 남는다.

• 각 항목 1회 사용( 0/1 ) → 역순
• 무제한 사용 → 정순

T = int(input())

for tc in range(1, T + 1):
    # N = 재료의 수, L = 최대 칼로리 제한
    N, L = map(int, input().split())
    # foods = 재료들의 정보 [맛, 칼로리]
    foods = [tuple(map(int, input().split())) for _ in range(N)]
    # 최댓값을 저장하는 공간
    dp = [0] * (L + 1)

    for taste, cal in foods:
        # 음식 칼로리 당 변경되는 부분들만 순회
        for cur_cal in range(L, cal - 1, -1):
            # 기존 값, 합성 값(이전 값 기준) 비교
            dp[cur_cal] = max(dp[cur_cal], dp[cur_cal - cal] + taste)

    print(f'#{tc} {dp[L]}')

처음에는 루프 안에서 cur_cal < cal이면 continue로 걸렀는데, range 끝 값을 cal - 1로 잡아 처음부터 제외했다. 역순이라 조건이 한 번 참이 되면 그 아래도 전부 참이어서 가능하다.

복잡도는 O(N·L) = 20 × 10⁴ = 2 × 10⁵다. N ≤ 20이라 부분집합 완전탐색( 2²⁰ ≈ 10⁶ )으로도 풀리는 제한이고, DP는 L에, 완전탐색은 N에 비용이 걸린다.

dp를 0으로 채우면 dp[c]는 무엇인가

dp = [0] * (L + 1)로 시작하면 dp[c]는 “칼로리 합이 c 이하일 때 최대 맛”이 된다. 아무것도 안 고른 0점이 모든 칸에 깔려 있어서, 칼로리를 덜 쓰고 남는 경우까지 같은 칸에 들어간다. 그래서 답이 dp[L] 하나다.

“정확히 c”로 쓰고 싶으면 만들 수 없는 칸을 막아야 한다.

NEG = float('-inf')
dp = [0] + [NEG] * L        # 칼로리 0만 만들 수 있는 상태로 시작
# ... 갱신은 동일 ...
print(max(dp))              # 정확히 0 ~ L 중 최댓값

-inf에 맛을 더해도 -inf라 만들 수 없는 조합은 끝까지 걸러지고, dp[c]에는 칼로리 합이 정확히 c인 경우만 남는다. 답은 L 이하 전체에서 골라야 하니 max(dp)다.

SWEA 1952 수영장 — 한 번만 오는 칸은 비교 없이 시작한다

문제. 1일 / 1달 / 3달 / 1년 이용권 요금과 12개월 각각의 이용 계획( 이용 일수 )이 주어진다. 1년 계획을 모두 덮는 가장 적은 비용을 출력한다. 3달권은 아무 달에나 시작할 수 있다.

dp[i]를 1월 ~ i월을 덮는 최소 비용으로 두면 i월을 덮는 방법은 세 가지다.

dp[i] = min( dp[i-1] + 1일권 × 이용일,
             dp[i-1] + 1달권,
             dp[i-3] + 3달권 )
답 = min(dp[12], 1년권)

첫 버전은 이용권 네 개를 enumerate로 돌며 idx로 분기했고, dp[i]를 sentinel로 채운 뒤 후보마다 min으로 비교했다. 총 이용일도 따로 계산했고, 루프는 0월부터 돌았다.

0월부터 돌면 생기는 일

루프를 0부터 돌리면 dp[i-1], dp[i-3]이 dp[-1], dp[-3]을 읽는다. 파이썬에서는 음수 인덱스가 배열 끝으로 감기고, 끝 칸은 아직 sentinel이라 그 후보가 min에서 지면서 결과적으로 무시된다. 파이썬에서는 우연히 맞고, 같은 코드를 C++로 옮기면 범위 밖 접근( UB )이다. 루프를 1월부터 돌리고 3달권은 i >= 3일 때만 본다.

최신 값만 남는 것 아닐까

sentinel을 없애려면 첫 후보를 비교 없이 dp[i]에 넣어야 한다.

dp[cur_month] = dp[cur_month - 1] + min(day * plan_table[cur_month], month)
if cur_month >= 3:
    dp[cur_month] = min(dp[cur_month], dp[cur_month - 3] + quarter)

처음엔 이게 이상해 보였다. 첫 줄이 dp[cur_month]를 그냥 덮어쓰니까, 이전에 들어 있던 더 작은 값이 있었다면 지워지는 것 아닌가 싶었다.

풀린 건 이 칸에 몇 번 오는가를 보고 나서였다. 배낭이나 동전 문제는 바깥 루프( 재료, 동전 )가 돌 때마다 같은 칸 dp[c]를 다시 방문한다. 그때 dp[c]에 들어 있는 기존 값은 이전 재료까지 고려한 최적해라서 반드시 비교해야 한다. 개요의 다음 날 메모지 쪽이다.

수영장의 dp[cur_month]는 루프 전체에서 딱 한 번 온다. 그 한 번의 반복 안에서 후보를 전부 계산하니, 첫 줄이 덮어쓰는 건 이전 최적해가 아니라 아무 의미 없는 초기값 0이다. 두 번째 줄의 dp[cur_month]는 “지금까지 본 후보의 최솟값”이고, 리스트 최솟값을 구할 때 첫 원소로 시작하는 것과 같은 구조다. 개요의 첫날 메모지 쪽이다.

• 한 칸을 여러 번 방문 → 기존 값과 비교
• 한 칸을 한 번만 방문 → 첫 후보를 대입하고 나머지만 비교

이렇게 하니 sentinel도, 총 이용일 계산도 필요 없어졌다.

해를 넘기는 3달권은 안 봐도 된다

11월이나 12월에 3달권을 사면 내년까지 덮는다. 이 경우를 따로 보지 않아도 정답이다.

• 11월에 산 3달권이 올해 덮는 건 11·12월이다. 10월에 사면 10·11·12월을 덮어서 범위가 더 넓고 가격은 같다.
• dp는 단조 증가한다( 덮을 달이 늘면 비용이 줄 수 없으니 dp[9] ≤ dp[10] ). 따라서 dp[9] + 3달권 ≤ dp[10] + 3달권.

10월에 사는 쪽이 항상 같거나 싸니, 11월에 사는 후보는 볼 필요가 없다( 12월도 같은 논리 ). 더 나은 선택으로 바꿔 끼워도 손해가 없음을 보이는 교환 논증이다.

T = int(input())
MONTH_COUNT = 12

for tc in range(1, T + 1):
    # 1일 / 1달 / 3달 / 1년 이용권 비용
    day, month, quarter, year = map(int, input().split())
    # 계획이 적혀진 달력으로 index를 그 달로 사용
    plan_table = [0]
    plan_table.extend(list(map(int, input().split())))
    dp = [0] * (MONTH_COUNT + 1)

    for cur_month in range(1, MONTH_COUNT + 1):
            # 1일 / 1달 권 기준 최소 계산
            dp[cur_month] = dp[cur_month - 1] + min(day * plan_table[cur_month], month)
            # 3달 권 기준 최소 계산
            if cur_month >= 3:
                dp[cur_month] = min(dp[cur_month], dp[cur_month - 3] + quarter)
    # 1년 권 기준 최소 계산 (1 번 비교)
    dp[MONTH_COUNT] = min(dp[MONTH_COUNT], year)

    print(f'#{tc} {dp[MONTH_COUNT]}')

첫 버전과 비교하면 이용권 이름을 바로 언패킹해 enumerate와 idx 분기가 빠졌고, 루프가 1월에서 시작해 음수 인덱스가 사라졌고, 1년권은 루프 밖에서 한 번만 비교한다.

소감

DP가 코딩의 탈을 쓴 수학 문제라고 생각하게 되었다. 관련 문제들을 다시 최적화 및 논리를 정리해가면서 여러 개념들을 다시금 곱씹어보니 꽤나 신기한 응용 방식들을 알게 되어 재밌었다.