동적 계획법 1 - 상태와 점화식

이 장에서 배우는 것

같은 계산을 다시 한다는 사실을 알아차리면 풀이의 방향이 달라진다. 계산 순서를 조금 바꾸는 데서 그치지 않고, 한 번 구한 답을 저장해 다음 계산의 재료로 쓰게 된다. 동적 계획법(dynamic programming)은 이처럼 작은 문제의 답을 이용해 더 큰 문제의 답을 구하는 방법이다. 핵심은 표를 만드는 문법이 아니라, 표의 한 칸이 무엇을 뜻하는지 정하는 일이다.

앞 장에서 최단 거리는 여러 경로의 후보 중 작은 값을 고르는 과정으로 표현되었다. 이번에는 그래프를 만들지 않고도, 남은 금액이나 도착한 계단처럼 작은 상태를 정의해 답을 구한다. 짧은 문제 두 개로 상태와 점화식을 익힌 뒤, 동전 거스름 문제를 재귀·메모·표의 세 방식으로 구현한다.

• 중복 부분 문제와 최적 부분 구조가 풀이에서 어떻게 나타나는지 설명한다.
• 상태의 의미, 초기값, 점화식, 계산 순서를 한 묶음으로 정한다.
• 같은 점화식을 메모이제이션과 표 채우기로 구현하고 차이를 비교한다.
• 계단의 경우의 수와 동전의 최소 개수에서 덧셈과 최솟값을 구별한다.
• 작은 입력을 전수 생성해 느린 재귀와 빠른 풀이의 결과를 대조한다.

문제 상황

작은 작업장의 정산 프로그램을 만든다고 하자. 작업장에서는 내부 정산용 동전을 사용한다. 동전의 값은 1, 4, 6이고 각 종류는 필요한 만큼 쓸 수 있다. 프로그램은 주어진 금액을 정확히 만들면서 동전 개수가 가장 적은 구성을 찾아야 한다. 실제로 어떤 동전을 골랐는지 출력하는 기능은 뒤로 미루고, 우선 최소 개수만 구한다.

8을 정산할 때 가장 큰 동전부터 고르면 6, 1, 1로 세 개가 된다. 하지만 4, 4를 고르면 두 개면 된다. 큰 동전을 먼저 고르는 규칙은 이 동전 체계에서 최소 개수를 보장하지 않는다. 동전의 값이 바뀌어도 동작하려면 여러 선택을 비교할 근거가 필요하다.

문제를 다음처럼 정한다. 서로 다른 양의 정수로 이루어진 동전 목록과 0 이상의 정수 금액이 주어진다. 동전은 종류마다 무제한으로 사용할 수 있다. 정확한 금액을 만드는 최소 동전 개수를 반환하고, 만들 수 없으면 -1을 반환한다. 금액 0은 아무 동전도 쓰지 않으면 되므로 답이 0이다.

두 번째 상황은 작업장 내부 계단이다. 바닥을 위치 0으로 두고 한 번에 한 칸 또는 두 칸을 오른다. 위치 4까지 가는 이동 순서가 몇 개인지 센다. 한 칸 뒤 두 칸을 오르는 순서와 두 칸 뒤 한 칸을 오르는 순서는 서로 다르다. 이 문제는 최솟값을 구하지 않지만, 작은 상태의 답을 재사용한다는 점에서는 정산 문제와 같다.

같은 작은 문제를 다시 만나면 저장한다

계단의 마지막 이동으로 나누기

위치 4에 도착하는 마지막 이동을 살펴본다. 한 칸을 올라왔다면 바로 전 위치는 3이다. 두 칸을 올라왔다면 바로 전 위치는 2다. 위치 3까지 가는 모든 순서 뒤에 한 칸 이동을 붙이고, 위치 2까지 가는 모든 순서 뒤에 두 칸 이동을 붙이면 된다.

여기서 상태를 ways[i] = 위치 i까지 도착하는 이동 순서의 수라고 정의한다. 그러면 i가 2 이상일 때 ways[i] = ways[i - 1] + ways[i - 2]다. 큰 상태와 작은 상태의 답 사이의 관계를 나타낸 식을 점화식이라고 한다.

계단 상태를 작은 위치부터 채우면 앞의 두 답만 필요하다

위치 i	계산 근거	ways[i]
0	아무 이동도 하지 않는 순서 하나	1
1	한 칸 이동만 가능	1
2	ways[1] + ways[0]	2
3	ways[2] + ways[1]	3
4	ways[3] + ways[2]	5

위치 0의 답을 1로 두는 이유를 확인해야 한다. 아무 이동도 하지 않는 빈 순서도 하나의 방법이다. 여기에 두 칸 이동을 붙여야 위치 2에 도착하는 방법 하나가 만들어진다. 초기값은 식을 계산하기 편하게 정하는 숫자가 아니라, 상태의 뜻에 맞는 답이어야 한다.

마지막 이동이 한 칸인 경우와 두 칸인 경우는 겹치지 않는다. 가능한 마지막 이동을 모두 나누었으므로 빠진 순서도 없다. 작은 위치의 답이 맞다고 가정하면 두 답을 더한 큰 위치의 답도 맞다. 이것이 이 점화식의 짧은 귀납 근거다.

재귀 호출의 나무에서 같은 상태 찾기

위치 4의 답을 재귀로 구하면 위치 3과 위치 2의 답을 요청한다. 위치 3도 다시 위치 2의 답을 요청한다. 호출 경로는 달라도 “위치 2까지 가는 순서의 수”라는 질문은 같다. 이렇게 동일한 작은 문제가 여러 번 나타나는 성질이 중복 부분 문제다.

중복을 줄이려면 상태 2의 답을 처음 계산했을 때 저장하고, 다음 요청에는 저장한 값을 돌려주면 된다. 재귀의 흐름을 유지하면서 계산 결과를 저장하는 방식을 메모이제이션(memoization)이라고 한다. 필요한 상태에 도달했을 때 계산하므로 하향식이라고도 부른다.

반대로 위치 0과 1의 답부터 적고 2, 3, 4를 순서대로 계산할 수도 있다. 이를 표 채우기(tabulation)라고 하며, 작은 상태에서 큰 상태로 진행하므로 상향식이라고도 부른다. 두 방식은 다른 수학을 사용하는 풀이가 아니다. 같은 상태와 점화식을 서로 다른 순서로 계산한다.

단순 재귀는 비슷한 호출을 반복하므로 계단 수 n에 대해 지수적으로 많은 호출이 생길 수 있다. 메모와 표는 각 위치를 한 번 계산하므로 덧셈 횟수가 O(n)이다. 표를 모두 저장하면 공간은 O(n)이고, 메모 방식은 여기에 최대 O(n) 깊이의 재귀 호출 공간도 필요하다. 여기서는 정수 덧셈을 한 연산으로 센다. 경우의 수가 매우 커지면 큰 정수를 더하는 비용도 함께 늘어난다.

상태의 뜻에서 동전 점화식을 만든다

답을 정하는 데 필요한 정보만 남기기

동전 문제에서는 best[a] = 금액 a를 정확히 만드는 최소 동전 개수라고 정한다. 사용할 수 있는 동전 목록은 계산 내내 고정되어 있다. 또한 어느 동전을 앞에서 골랐든 각 종류를 계속 사용할 수 있다. 따라서 과거 선택을 모두 상태에 넣을 필요 없이 금액 하나로 질문을 표현할 수 있다.

이 생략에는 조건이 있다. 동전을 종류마다 한 번만 사용할 수 있다면 남은 금액이 같아도 앞으로 쓸 수 있는 동전이 다를 수 있다. 그때는 금액만으로 답을 정할 수 없다. 상태를 정할 때는 “같은 상태로 묶은 두 상황의 이후 선택지가 같은가”를 확인해야 한다. 동적 계획법의 표 모양은 이 질문에 답한 뒤에 정해진다.

금액 a를 만드는 마지막 동전의 값을 c라고 하자. 그 동전을 빼면 금액 a - c를 만들어야 한다. 그 금액을 만들 수 있다면 필요한 동전 수의 후보는 best[a - c] + 1이다. 사용할 수 있는 모든 c의 후보 중 가장 작은 값을 고른다.

따라서 초기값은 best[0] = 0이다. a가 양수일 때는 c <= a이고 나머지 금액을 만들 수 있는 동전만 대상으로 best[a - c] + 1의 최솟값을 구한다. 후보가 하나도 없으면 그 금액은 만들 수 없다.

최적 부분 구조를 확인하기

최소 개수로 금액 a를 만든 구성에서 마지막 동전 c를 제거했다고 하자. 남은 구성이 금액 a - c의 최소 구성보다 동전을 더 많이 쓴다면, 그 부분을 최소 구성으로 바꿀 수 있다. 여기에 c를 다시 붙이면 원래 구성보다 동전 수가 줄어든다. 이는 원래 구성이 최소라는 가정과 맞지 않는다.

즉, 최적해 안의 나머지 부분도 해당 작은 문제의 최적해여야 한다. 이 성질을 최적 부분 구조라고 한다. 모든 마지막 동전을 비교하는 점화식은 최적 구성의 마지막 동전도 후보에 포함한다. 그러므로 작은 금액의 답이 맞으면 큰 금액의 답도 맞게 구할 수 있다.

중복 부분 문제와 최적 부분 구조는 역할이 다르다. 중복은 결과를 저장해 계산을 줄일 근거이고, 최적 부분 구조는 작은 최적값으로 큰 최적값을 만들 수 있는 근거다. 계단처럼 개수를 세는 문제에서는 최적성 대신, 경우를 겹치거나 빠뜨리지 않게 나누었다는 근거가 필요하다.

동전 1, 4, 6으로 금액 8까지 최소 개수를 계산한다

금액 a	가능한 후보 개수	best[a]
0	빈 구성	0
1	best[0] + 1 = 1	1
2	best[1] + 1 = 2	2
3	best[2] + 1 = 3	3
4	4, 1	1
5	2, 2	2
6	3, 3, 1	1
7	2, 4, 2	2
8	3, 2, 3	2

표의 후보는 차례대로 동전 1, 4, 6을 마지막에 붙인 결과다. 금액보다 큰 동전의 후보는 생략했다. 예를 들어 금액 8에서는 금액 7에 1을 붙이는 후보, 금액 4에 4를 붙이는 후보, 금액 2에 6을 붙이는 후보를 비교한다.

불가능과 미계산을 구별하기

코드에서는 만들 수 없는 상태를 내부 값 amount + 1로 나타낸다. 동전 값이 모두 양의 정수이므로 목표 금액이 A일 때 가능한 구성의 동전 수는 A를 넘을 수 없다. 따라서 A + 1은 가능한 최소 개수와 겹치지 않는다. 이 값을 inf라는 변수에 저장한다.

외부에 반환하는 -1을 그대로 최솟값 계산에 쓰면 문제가 생긴다. 만들 수 없는 금액의 -1에 1을 더하면 0이 되어 좋은 후보처럼 보이기 때문이다. 내부 계산에서는 불가능한 후보를 제외하고, 함수가 끝날 때만 불가능 값을 -1로 바꾼다.

메모 배열에서는 아직 계산하지 않은 칸을 None으로 둔다. 불가능하다고 계산된 칸은 inf다. 이 둘을 구별해야 불가능한 상태도 한 번 계산한 뒤 재사용할 수 있다.

메모와 표는 계산 순서가 다르다

단순 재귀는 남은 금액에서 동전 하나를 빼며 내려간다. 같은 남은 금액을 다른 경로에서 만나면 다시 계산한다. 메모 방식은 이 재귀 함수의 입구에 저장된 답을 확인하는 절차를 추가한다. 표 방식은 금액 0부터 A까지 올라가며 같은 식을 반복문으로 계산한다.

표 방식의 불변식은 “금액 a를 계산하기 직전에 0부터 a - 1까지의 답이 모두 확정되어 있다”다. 동전 값 c가 양수이므로 참조하는 a - c는 항상 a보다 작다. 따라서 이미 확정된 칸만 읽는다. a의 계산이 끝나면 확정된 범위가 한 칸 늘어난다.

동전 종류 수를 k, 목표 금액을 A라고 하자. 메모와 표는 최대 A + 1개 상태에서 각각 k개 동전을 살피므로 시간 복잡도는 O(Ak), 저장 공간은 O(A)다. 메모에는 최대 O(A)의 호출 스택도 필요하다. A는 금액 자체이므로 금액이 매우 크면 이 방법도 비용이 커진다.

단순 재귀의 깊이는 최대 A이고, 각 호출에서 최대 k개로 갈라진다. k가 2 이상이면 느슨한 시간 상한을 O(k의 A제곱)으로 둘 수 있다. 동전이 하나뿐이면 갈래가 없어서 O(A)이고, 재귀 공간은 모두 O(A)다. 실제 호출 수는 동전 값에 따라 달라지지만, 중복 계산이 커질 수 있다는 점이 비교의 핵심이다.

세 방식의 정확성은 같은 점화식에 기대지만 실패 양상은 다르다. 재귀 두 방식은 금액이 커지면 호출 깊이 제한에 걸릴 수 있다. 메모가 중복 계산을 줄여도 재귀 깊이까지 줄이지는 않는다. 큰 금액을 반복 처리하는 구현에서는 표 방식이 이 제약을 피한다.

완성 코드

다음 내용을 main.py로 저장한다. 예시 입력의 첫 줄은 동전 종류 수와 목표 금액이고, 둘째 줄은 동전 값이다. 표준 라이브러리의 io.StringIO로 입력 스트림을 흉내 내므로 키보드 입력을 기다리지 않는다. 세 함수는 양의 정수 동전 목록과 0 이상의 정수 금액을 받는다는 계약을 공유한다.

검증에서는 1부터 4까지의 값으로 만들 수 있는 비어 있지 않은 동전 집합을 모두 만든다. 집합은 15개이고 각 집합에 금액 0부터 10까지를 넣으므로 총 165건이다. 저장하지 않는 재귀를 느린 기준 풀이로 삼고, 메모와 표의 반환값이 모두 같은지 검사한다. 별도로 답을 알고 있는 예시도 검사해 공통 점화식의 실수를 보완한다.

import io
from itertools import combinations


def min_coins_recursive(coins, amount):
    inf = amount + 1

    def solve(rest):
        if rest == 0:
            return 0
        best = inf
        for coin in coins:
            if coin <= rest:
                previous = solve(rest - coin)
                if previous != inf:
                    best = min(best, previous + 1)
        return best

    answer = solve(amount)
    return -1 if answer == inf else answer


def min_coins_memo(coins, amount):
    inf = amount + 1
    memo = [None] * (amount + 1)
    memo[0] = 0

    def solve(rest):
        if memo[rest] is not None:
            return memo[rest]
        best = inf
        for coin in coins:
            if coin <= rest:
                previous = solve(rest - coin)
                if previous != inf:
                    best = min(best, previous + 1)
        memo[rest] = best
        return best

    answer = solve(amount)
    return -1 if answer == inf else answer


def min_coins_table(coins, amount):
    inf = amount + 1
    dp = [inf] * (amount + 1)
    dp[0] = 0

    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and dp[value - coin] != inf:
                dp[value] = min(dp[value], dp[value - coin] + 1)

    answer = dp[amount]
    return -1 if answer == inf else answer


def verify_small_cases():
    solvers = (
        min_coins_recursive,
        min_coins_memo,
        min_coins_table,
    )
    known_cases = (
        ((1, 4, 6), 8, 2),
        ((4, 6), 7, -1),
        ((3,), 0, 0),
        ((3,), 6, 2),
    )
    for coins, amount, expected in known_cases:
        for solver in solvers:
            actual = solver(coins, amount)
            if actual != expected:
                raise AssertionError(
                    (solver.__name__, coins, amount, actual, expected)
                )

    checked = 0
    for size in range(1, 5):
        for coins in combinations(range(1, 5), size):
            for amount in range(11):
                slow = min_coins_recursive(coins, amount)
                memo = min_coins_memo(coins, amount)
                table = min_coins_table(coins, amount)
                if not (slow == memo == table):
                    raise AssertionError(
                        (coins, amount, slow, memo, table)
                    )
                checked += 1
    return checked


def main():
    source = io.StringIO("3 8\n1 4 6\n")
    count, amount = map(int, source.readline().split())
    coins = tuple(map(int, source.readline().split()))
    if (
        amount < 0
        or len(coins) != count
        or not coins
        or any(coin <= 0 for coin in coins)
        or len(set(coins)) != count
    ):
        raise ValueError("입력 조건을 확인한다")

    print("동전:", *coins)
    print("목표 금액:", amount)
    print("재귀:", min_coins_recursive(coins, amount))
    print("메모:", min_coins_memo(coins, amount))
    print("표:", min_coins_table(coins, amount))
    print("불가능 예시:", min_coins_table((4, 6), 7))
    checked = verify_small_cases()
    print(f"작은 입력 전수 대조: {checked}건 통과")


if __name__ == "__main__":
    main()

줄별 해설

import io는 예시 문자열을 입력 스트림처럼 읽기 위해 사용한다. combinations는 작은 동전 집합을 중복 없이 생성한다. 입력 순서가 달라도 최소 개수는 같으므로 검증에서는 같은 집합의 순열까지 만들지 않는다.

min_coins_recursive의 inf = amount + 1은 이번 목표 금액 전체에서 공통으로 쓰는 불가능 값이다. 내부 함수 solve(rest)의 반환값은 남은 금액 rest의 최소 개수다. rest가 0이면 동전이 더 필요하지 않으므로 0을 반환한다.

best = inf는 아직 가능한 후보를 찾지 못했다는 뜻이다. coin <= rest인 동전만 빼므로 남은 금액은 음수가 되지 않는다. previous가 불가능 값이 아닐 때 동전 하나를 더해 최솟값을 갱신한다. 모든 동전을 확인해도 후보가 없다면 best는 inf로 남는다.

answer = solve(amount)는 전체 문제를 요청한다. 바로 다음 반환문은 내부 불가능 값만 -1로 바꾼다. 재귀 호출 사이에서는 이 변환을 하지 않는다. 덕분에 각 호출이 같은 규칙으로 후보를 비교한다.

min_coins_memo의 memo = [None] * (amount + 1)은 금액별 저장 칸을 만든다. memo[0] = 0은 초기 상태의 답을 미리 기록한다. is not None으로 검사하므로 답이 0인 상태와 불가능하다고 확정된 상태도 저장된 답으로 인정한다.

memo[rest] = best는 모든 후보 비교가 끝난 뒤 실행한다. 비교 도중의 임시 답을 확정된 답처럼 저장하지 않는다. 이후 같은 rest가 요청되면 함수 입구에서 바로 반환하므로 동전 반복문을 다시 실행하지 않는다.

min_coins_table의 dp는 메모와 달리 미계산 표시가 필요 없다. 반복문이 계산 순서를 보장하므로 모든 칸을 inf로 시작하고 0번 칸만 고친다. range(1, amount + 1)은 목표 금액까지 포함한다. 내부 반복문은 현재 금액의 마지막 동전을 하나씩 시험한다.

verify_small_cases의 첫 반복문은 알려진 정답을 확인한다. 0원, 만들 수 없는 금액, 같은 동전의 반복 사용, 큰 동전 우선 선택이 실패하는 사례가 포함된다. 다음 세 겹의 반복문은 동전 집합 크기, 실제 집합, 목표 금액을 차례로 고른다.

slow == memo == table은 세 결과가 모두 같은지 검사한다. 다르면 입력과 세 결과를 예외에 담아 어느 사례에서 차이가 생겼는지 드러낸다. 검사가 끝난 사례만 checked에 더하므로 마지막 숫자는 실제로 대조한 입력 수다.

main의 입력 검사는 예시 데이터가 함수의 계약을 지키는지 확인한다. 마지막 조건문은 파일을 직접 실행했을 때 main을 호출한다. 난수를 사용하지 않으므로 출력과 검사 순서는 실행할 때마다 같다.

실행 결과

다음 명령으로 문법 컴파일을 확인한 뒤 실행할 수 있다. 첫 명령은 정상일 때 출력이 없으며, 프로그램의 예상 출력은 아래와 같다.

python3 -m py_compile main.py
python3 main.py

동전: 1 4 6
목표 금액: 8
재귀: 2
메모: 2
표: 2
불가능 예시: -1
작은 입력 전수 대조: 165건 통과

전수 대조가 통과했다는 말은 지정한 작은 입력 범위에서 세 구현이 일치했다는 뜻이다. 모든 금액의 정확성을 검사로 확인한 것은 아니다. 전체 범위의 근거는 앞서 살펴본 점화식과 계산 순서의 귀납 논증이고, 작은 입력 검사는 초기값·경계·저장 과정의 구현 실수를 찾는 역할을 한다.

또한 느린 재귀도 같은 점화식을 사용한다. 따라서 세 코드가 공유한 모델링 오류를 전수 대조만으로 잡지 못할 수 있다. 손으로 확인한 정답 사례와 정확성 근거를 함께 두는 이유다.

실무에서 자주 틀리는 것

불가능을 0으로 초기화한다

0은 이미 금액 0의 올바른 답이다. 다른 금액까지 0으로 두면 아직 찾지 못한 답이 동전 없이 가능한 것처럼 취급된다. 최솟값을 갱신해도 0보다 작은 후보는 나오지 않아 잘못된 값이 남는다.

틀린 코드는 다음과 같다.

dp = [0] * (amount + 1)
dp[value] = min(dp[value], dp[value - coin] + 1)

가능한 답과 구별되는 값으로 시작해야 한다.

inf = amount + 1
dp = [inf] * (amount + 1)
dp[0] = 0

저장된 답을 참과 거짓으로 검사한다

정수 0은 조건식에서 거짓으로 취급된다. 저장된 답의 존재 여부와 답 자체의 참·거짓은 다른 질문이다. 미계산 값을 None으로 정했다면 그 값과 직접 비교한다.

틀린 코드는 다음과 같다.

if memo[rest]:
    return memo[rest]

저장된 0도 반환하도록 고친다.

if memo[rest] is not None:
    return memo[rest]

음수 인덱스를 작은 금액으로 착각한다

파이썬 리스트의 음수 인덱스는 뒤쪽 원소를 가리킨다. 금액보다 큰 동전을 빼면 오류 대신 엉뚱한 칸을 읽을 수 있다. 아직 계산하지 않은 뒤쪽 칸을 읽는 순간 표의 불변식도 깨진다.

틀린 코드는 다음과 같다.

for coin in coins:
    dp[value] = min(dp[value], dp[value - coin] + 1)

먼저 동전이 현재 금액을 넘지 않는지 확인한다.

for coin in coins:
    if coin <= value and dp[value - coin] != inf:
        dp[value] = min(dp[value], dp[value - coin] + 1)

동전 사용 조건이 바뀌어도 상태를 유지한다

값이 4인 동전이 한 개뿐인데 금액 8을 만들어야 한다고 하자. 무제한 사용 점화식을 그대로 쓰면 4를 두 번 사용해 답을 2로 계산한다. 이 문제에서는 단순히 반복문의 문법을 고칠 것이 아니라 동전의 사용 가능 정보를 다시 정의해야 한다.

한 번만 쓸 수 있는 동전을 무제한 문제 함수에 전달하는 다음 코드는 조건을 표현하지 못한다.

# 값 4인 동전이 실제로는 한 개뿐인 상황이다.
answer = min_coins_table((4,), 8)

이 작은 사례는 보유한 동전 한 개를 쓰는 경우와 쓰지 않는 경우로 직접 구분할 수 있다.

def min_with_one_coin(coin, amount):
    if amount == 0:
        return 0
    if amount == coin:
        return 1
    return -1


answer = min_with_one_coin(4, 8)

여러 종류의 보유 수량까지 다루려면 상태에 어떤 정보를 더 담을지 새로 설계해야 한다. 현재 장의 함수에는 “각 종류를 무제한 사용한다”는 계약이 붙어 있음을 기억한다.

한눈에 보기

상태를 정의한 뒤 초기값과 전이를 같은 의미로 연결한다

항목	계단 순서 세기	최소 동전 개수
상태	위치 i까지 가는 순서 수	금액 a를 만드는 최소 개수
초기값	ways[0] = 1, ways[1] = 1	best[0] = 0
결합	마지막 이동별 경우의 수를 더함	마지막 동전별 후보의 최솟값
정확성 근거	겹치지 않는 마지막 이동 분류	최적 부분 구조와 모든 후보 비교

동전 문제의 세 구현은 같은 점화식의 계산과 저장 방식을 달리한다

방식	계산 방식	시간	추가 공간
단순 재귀	요청마다 다시 계산	k ≥ 2에서 O(k의 A제곱) 상한	O(A) 호출 스택
메모	요청된 상태의 답 저장	O(Ak)	O(A), 호출 스택 포함
표	작은 금액부터 순서대로 계산	O(Ak)	O(A)

문제를 풀 때는 먼저 상태를 한 문장으로 적는다. 다음으로 가장 작은 상태의 답을 정하고, 큰 상태의 마지막 선택을 나눈다. 마지막으로 참조하는 작은 상태가 언제 확정되는지 확인한다. 이 순서를 거치면 배열의 크기와 반복문의 방향도 근거를 갖고 정할 수 있다.

연습 문제

1. 한 칸 또는 두 칸씩 오르는 계단에서 위치 5까지 가는 순서의 수를 구한다. 상태 0부터 5까지의 값을 쓰고, 위치 0의 답을 0으로 두면 어떤 문제가 생기는지 설명한다.
2. 동전이 3과 5일 때 금액 0부터 8까지의 최소 개수를 표로 작성한다. 만들 수 없는 금액은 -1로 표시한다. 금액 8의 최솟값이 어느 작은 상태에서 오는지도 설명한다.
3. 계단 문제를 표 방식으로 구현한다. 저장하지 않는 재귀도 만들고, 위치 0부터 12까지 두 함수의 결과를 전수 대조한다. 모두 같으면 검사한 입력 수를 출력한다.
4. 동전 목록에 0을 허용하면 재귀와 표의 근거가 어떻게 달라지는지 설명한다. 완성 코드에서 어느 입력 조건이 이 문제를 막는지도 찾는다.

정답과 해설

1. 상태 값은 차례대로 1, 1, 2, 3, 5, 8이다. 위치 5의 마지막 이동을 나누면 위치 4의 다섯 순서와 위치 3의 세 순서를 합쳐 8이 된다. 위치 0을 0으로 두고 위치 1만 1로 두면 위치 2가 1로 계산되어, 바닥에서 곧바로 두 칸 오르는 순서가 빠진다.

2. 금액 0부터 8까지의 답은 0, -1, -1, 1, -1, 1, 2, -1, 2다. 금액 8에서는 3을 마지막에 쓰면 금액 5의 답 1에 하나를 더하고, 5를 마지막에 쓰면 금액 3의 답 1에 하나를 더한다. 두 후보 모두 2다. 두 경로가 같은 동전 구성을 다른 순서로 나타내더라도 최솟값 비교에는 문제가 없다.

3. 다음 코드를 별도로 실행하면 계단 대조: 13건 통과가 출력된다. 위치 0도 검사하므로 검사 수는 12가 아니라 13이다.

   def stairs_recursive(n):
       if n <= 1:
           return 1
       return stairs_recursive(n - 1) + stairs_recursive(n - 2)
   
   
   def stairs_table(n):
       ways = [0] * (n + 1)
       ways[0] = 1
       for position in range(1, n + 1):
           ways[position] += ways[position - 1]
           if position >= 2:
               ways[position] += ways[position - 2]
       return ways[n]
   
   
   checked = 0
   for n in range(13):
       slow = stairs_recursive(n)
       fast = stairs_table(n)
       if slow != fast:
           raise AssertionError((n, slow, fast))
       checked += 1
   print(f"계단 대조: {checked}건 통과")

   표 방식은 각 위치를 한 번씩 계산하므로 덧셈 횟수와 공간이 O(n)이다. 재귀는 중복 계산이 있지만 검사 범위를 작게 제한했으므로 기준 풀이로 사용할 수 있다.

4. 재귀에서 0을 빼면 남은 금액이 줄지 않는다. 아직 답을 저장하기 전에 같은 상태를 다시 호출하므로 메모 방식도 종료 조건에 가까워지지 않는다. 표에서는 현재 칸 자신을 참조해 “작은 금액의 확정된 답만 읽는다”는 근거가 사라진다. 최소 개수 문제에서 값 0인 동전은 답을 개선하지 못하므로 제거할 수도 있지만, 이 프로그램은 입력 계약을 단순하게 유지하도록 거부한다. any(coin <= 0 for coin in coins)가 그 검사다.

상태가 충분한 정보를 담고, 작은 상태로 이동하는 규칙이 분명하면 구현은 재귀와 반복문 중에서 선택할 수 있다. 다음 장에서는 선택 제약이나 두 대상의 위치처럼 정보가 더 필요한 문제에서 상태를 확장하는 방법을 살펴본다.