E-4: 동적 계획법 ① 기초 — 한 번 푼 건 적어 두고 다시 쓴다
목차 48
안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간 마지막, 우리는 거스름돈 앞에서 딱한 처지에 놓였습니다. 그리디는 빠른데 [1, 3, 4]로 6원을 거슬러 보면 틀린 답을 냈고, 완전탐색은 답을 맞히긴 하는데 지수 시간이라 금액이 조금만 커지면 무너졌죠. 빠른 쪽은 틀리고, 맞는 쪽은 느리다. 그 사이에 세 번째 길이 필요하다 — 그게 오늘의 출발점입니다.
그 세 번째 길로 가는 문은 E-3 마지막에 이미 열려 있었어요. 거스름돈 완전탐색 나무를 다시 떠올려 보세요. remaining=3(남은 3원)이 여러 갈래에서 되풀이해서 등장했습니다. 1+1+1로 닿든 3으로 닿든, "남은 3원을 최소 동전으로 만드는 법"은 완전히 똑같은데, 완전탐색은 새 갈래로 닿을 때마다 처음부터 다시 계산했어요. 그때 이런 생각이 들었죠. "한 번 푼 건 어디 적어 두고 다시 쓰면 되지 않나?"
바로 그 한 문장이 오늘 배울 동적 계획법(dynamic programming, DP)입니다. 그리디는 매 순간의 최적을 믿고 되돌아보지 않았지만, DP는 겹치는 계산을 기억해 두고 전체 최적을 계산해요. 오늘 우리는 이 단순한 생각 하나로 지수 시간을 다항 시간으로 끌어내립니다.
오늘의 여정 — 한 번 푼 건 적어 두고 다시 쓴다
중복 부분 문제 같은 작은 문제를 몇 번이고 다시 푼다
│ fib(5) 하나 그려 봐도 fib(2)가 세 번 불린다
│
최적 부분 구조 큰 문제의 답이 작은 문제의 답으로 조립된다
│ 이 둘이 맞으면 DP가 통한다
▼
┌─ 메모이제이션 재귀 그대로, 푼 값을 공책에 적어 둔다 (top-down)
│ dict 한 겹 · @cache 한 줄
│
└─ 타뷸레이션 작은 문제부터 표를 채워 올라간다 (bottom-up)
재귀 스택 없이 공간을 O(1)까지
▼
1차원 DP 대표 계단 · 타일링 · 1로 만들기 · 동전 조합 수
지수 O(2ⁿ) → 다항 O(n)
💡 오늘 수업의 핵심 — "동적 계획법은 겹치는 부분 문제를 한 번만 풀어 적어 두고 다시 꺼내 쓰는 전략이라, 완전탐색의 지수 시간을 다항 시간으로 끌어내린다"
🎯 학습 목표
- 중복 부분 문제와 최적 부분 구조 — DP가 통하는 두 조건이 무엇인지 피보나치와 거스름돈에서 확인한다.
- 같은 점화식을 메모이제이션(top-down)과 타뷸레이션(bottom-up) 두 방향으로 풀고, 빅오와 공간의 트레이드오프를 따진다.
- 계단·타일링 같은 1차원 DP 대표 유형에서 "상태 정의가 점화식을 결정한다"를 익혀 지수 시간을 다항으로 내려앉힌다.
Step 1: "같은 문제를 또 푼다" (중복 부분 문제)
DP를 이야기할 때 가장 먼저 꺼내는 예제가 피보나치 수열입니다. 왜 하필 피보나치냐면, DP가 왜 필요한지를 이보다 선명하게 보여 주는 문제가 없거든요. 정의부터 볼게요.
피보나치 수는 앞의 두 수를 더해서 만듭니다. 0번째가 0, 1번째가 1, 그다음부터는 바로 앞 둘의 합이에요. 0, 1, 1, 2, 3, 5, 8, 13, 21… 이렇게 이어집니다. 수식으로 쓰면 fib(n) = fib(n-1) + fib(n-2)이고, 시작값은 fib(0)=0, fib(1)=1이죠.
이 정의를 그대로 코드로 옮기면 재귀 함수가 됩니다. E-1에서 배운 재귀 그대로예요.
# algorithms/dp.py
def fibonacci_naive(n, counter=None):
if counter is not None:
counter[0] += 1 # 이 함수가 몇 번 불렸는지 기록(폭발 실측용)
if n < 2: # fib(0)=0, fib(1)=1 — 종료 조건
return n
return fibonacci_naive(n - 1, counter) + fibonacci_naive(n - 2, counter)
n이 2보다 작으면(0이나 1이면) 그 값을 그대로 돌려주는 게 종료 조건이고, 그 위로는 정의 그대로 fib(n-1)과 fib(n-2)를 더합니다. counter는 잠시 뒤 Step 3에서 이 함수가 몇 번 불리는지 실측할 때 쓰는 도구라, 지금은 없다고 생각하고 넘어가셔도 됩니다.
깔끔하죠? 정의를 문장 그대로 옮겼으니 틀릴 리가 없어요. 그런데 문제는 속도입니다. fib(5) 하나를 구하는 과정을 나무로 펼쳐 보면 뭔가 이상한 게 눈에 들어와요.
fib(5) 호출 나무 — 정의를 그대로 재귀로 풀면
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
fib(2)는 세 번, fib(3)은 두 번 불린다.
n이 5인데도 벌써 같은 값을 처음부터 다시 푸는 낭비가 보인다.
보이시나요? fib(2)가 나무 곳곳에서 세 번, fib(3)이 두 번 불립니다. 이미 한 번 계산해서 답(fib(2)=1)을 알았는데도, 다른 갈래에서 만나면 그걸 모르고 처음부터 다시 계산해요. n이 커질수록 이 되풀이가 눈덩이처럼 불어납니다.
중복 부분 문제라는 이름
이렇게 큰 문제를 풀다가 같은 작은 문제를 여러 번 다시 만나는 성질을 중복 부분 문제(overlapping subproblems, 겹치는 부분 문제)라고 부릅니다. 오늘 배울 DP의 첫 번째 열쇠예요.
그리고 이건 우리가 이미 본 장면입니다. E-3의 거스름돈 완전탐색에서 remaining=3이 여러 갈래에서 되풀이 등장했던 것 — 그게 바로 중복 부분 문제였어요. 피보나치의 fib(2)와 거스름돈의 remaining=3은 이름만 다를 뿐 똑같은 낭비입니다. 한 번 푼 걸 또 푸는 것.
빅오로 따지면 순수 재귀 피보나치는 시간 O(2ⁿ)입니다. 호출이 갈래마다 대략 두 배씩 늘어나거든요. 공간은 O(n)이에요. 호출 횟수는 지수로 폭발해도, 재귀 스택은 한 갈래씩 깊이 n까지만 내려갔다 올라오니까요. 이 O(2ⁿ)이 얼마나 무서운 숫자인지는 Step 3에서 직접 세어 보겠습니다.
💡 한 줄 정리
피보나치를 정의 그대로 재귀로 풀면 fib(5)만 그려 봐도 fib(2)가 세 번, fib(3)이 두 번 불린다. 이렇게 같은 작은 문제를 여러 번 다시 푸는 성질이 중복 부분 문제(overlapping subproblems)다. E-3 거스름돈에서 remaining=3이 되풀이되던 것과 똑같은 낭비이고, 그 대가로 시간이 O(2ⁿ)까지 폭발한다.
🙋 학생 질문 — "재귀는 E-1에서 이미 배웠잖아요. 그때 팩토리얼도 재귀로 짰는데 왜 피보나치만 느린가요?"
핵심을 정확히 짚으셨어요. 둘 다 재귀인데 속도가 하늘과 땅 차이인 이유는 갈래가 몇 개로 갈라지느냐에 있습니다.
팩토리얼을 떠올려 보세요. factorial(n) = n * factorial(n-1). 자기를 부르는데 한 번만 부릅니다. 그러니 factorial(5)는 factorial(4), factorial(3)… 이렇게 한 줄기로 쭉 내려가요. 갈래가 하나뿐이라 호출 수가 n번, 빅오도 O(n)입니다. 되풀이되는 값이 없어요.
그런데 피보나치는 fib(n-1)과 fib(n-2)를 두 번 부릅니다. 한 번 부를 때마다 갈래가 둘로 갈라지니, 나무가 아래로 갈수록 두 배씩 넓어져요. 그리고 그 넓어진 갈래들이 서로 같은 값을 중복해서 계산합니다. 갈래가 둘 이상으로 갈라지면서 겹치는 순간, 재귀는 지수로 폭발해요.
그래서 "재귀라서 느리다"가 아니라 "갈래가 갈라지면서 겹치는 재귀라서 느리다"가 정확합니다. 그리고 바로 이 "겹친다"는 성질이 DP를 쓸 수 있는 신호예요. 겹치지 않는 재귀(팩토리얼)는 적어 둘 값어치가 없지만, 겹치는 재귀(피보나치)는 적어 두면 극적으로 빨라집니다. 그 방법을 Step 4부터 배웁니다.
Step 2: "큰 문제를 작은 답으로" (최적 부분 구조와 점화식)
Step 1에서 DP의 첫 번째 열쇠(중복 부분 문제)를 봤습니다. 이제 두 번째 열쇠를 손에 넣을 차례예요. 그런데 그 전에, DP를 실제로 짤 때 가장 중요한 한 줄부터 짚고 가겠습니다. 바로 점화식입니다.
점화식 — DP의 진짜 관문
점화식이라는 말이 어렵게 들리지만, 뜻은 단순해요. "지금 문제의 답을 더 작은 문제의 답으로 어떻게 표현할 것인가"를 적은 한 줄입니다. 피보나치는 이미 정의 자체가 점화식이었죠.
점화식 세우기 — 지금 문제를 더 작은 문제의 답으로 표현한다
fib(n) = fib(n-1) + fib(n-2)
│ │ │
구하려는 이미 아는 이미 아는
큰 문제 작은 답 작은 답
이 한 줄만 세우면 코드는 거의 저절로 나옵니다. 반대로 이 한 줄을 못 세우면 아무것도 못 해요. 그래서 DP 문제를 만나면 "점화식이 뭐지?"부터 묻는 게 실전의 첫걸음입니다.
최적 부분 구조 — 점화식이 성립하는 이유
그런데 점화식이 아무 문제에서나 세워지는 건 아닙니다. 큰 문제의 답이 작은 문제의 답으로 조립될 수 있어야 세울 수 있어요. 이 성질을 최적 부분 구조(optimal substructure)라고 부릅니다. DP의 두 번째 열쇠예요.
거스름돈으로 보면 확 와닿습니다. amount원을 만드는 최소 동전 수를 구한다고 해 봐요. 만약 마지막에 coin짜리 동전 하나를 썼다면, 남은 (amount-coin)원은 여전히 "최소 동전으로 만들어야 하는 똑같은 문제"입니다. 그러니 이렇게 조립돼요.
거스름돈의 최적 부분 구조
dp[amount] = min( dp[amount-coin] + 1 ) coins의 coin마다
│ │ │
amount원의 (amount-coin)원의 이번에 쓴
최소 동전 수 최소 동전 수 동전 하나
"amount원의 최소 = 동전 하나 뺀 자리들의 최소 중 가장 작은 것 + 1"
큰 문제(amount원)의 최적해가 작은 문제(amount-coin원)의 최적해로 만들어지죠? 이게 최적 부분 구조입니다. 이 성질이 있어야 "작은 답을 알면 큰 답을 안다"가 성립하고, 그래야 점화식을 세울 수 있어요.
DP가 통하는 두 조건 정리
이제 두 열쇠가 다 모였습니다. 어떤 문제에 DP를 쓸 수 있는지는 딱 두 가지로 판별해요.
| DP의 두 조건 | 뜻 | 없으면 |
|---|---|---|
| 겹치는 부분 문제 | 같은 작은 문제를 여러 번 다시 만난다 | 적어 둘 값어치가 없다 (팩토리얼처럼) |
| 최적 부분 구조 | 큰 문제의 답이 작은 문제의 답으로 조립된다 | 점화식을 세울 수 없다 |
두 조건이 다 맞으면 DP가 통합니다. 겹치니까 적어 두는 게 이득이고(첫째), 조립되니까 점화식으로 표현할 수 있어요(둘째). 오늘 만날 모든 문제 — 피보나치, 거스름돈, 계단, 타일링 — 가 이 두 조건을 모두 갖춘 문제들입니다.
💡 한 줄 정리
점화식은 "지금 문제의 답을 더 작은 문제의 답으로 표현한 한 줄"이고, DP의 진짜 관문이다. 이 점화식은 큰 문제의 답이 작은 문제의 답으로 조립되는 최적 부분 구조가 있어야 세워진다. DP가 통하는 조건은 두 가지 — 겹치는 부분 문제(적어 둘 값어치)와 최적 부분 구조(점화식을 세울 수 있음)다.
🙋 학생 질문 — "점화식을 어떻게 세우는지 감이 안 와요. 문제를 보면 바로 나오는 건가요?"
처음엔 아무도 바로 안 나옵니다. 저도 그랬어요. 다만 점화식을 세우는 데는 거의 항상 통하는 질문 하나가 있습니다. "마지막 한 걸음은 무엇인가?"
무슨 뜻이냐면, 큰 문제의 답에 도달하는 마지막 선택이 무엇인지를 생각해 보는 거예요. 거스름돈이라면 "마지막에 어떤 동전을 썼을까?"를 묻습니다. 어떤 동전을 썼든, 그 동전 하나를 빼면 더 작은 거스름돈 문제가 남죠. 그 작은 문제의 답을 안다고 치면, 거기에 "이번 동전 하나(+1)"만 더하면 됩니다. 이게 점화식이에요.
Step 6에서 만날 계단 오르기도 똑같아요. "n칸에 도착하는 마지막 한 걸음은 1칸일까 2칸일까?" 이 질문 하나로 점화식이 곧장 나옵니다. 마지막 걸음이 1칸이었다면 그 전엔 (n-1)칸에 있었을 거고, 2칸이었다면 (n-2)칸에 있었을 테니, 두 경우를 합치면 되죠.
그래서 점화식이 막힐 땐 이렇게 물어보세요. "이 답에 도달하는 마지막 선택은 몇 가지이고, 각각을 빼면 어떤 작은 문제가 남는가?" 마지막 선택으로 문제를 한 겹 벗겨 내면, 그 아래 드러나는 작은 문제가 점화식의 오른쪽 항입니다. 오늘 문제들을 하나씩 풀다 보면 이 감각이 붙어요.
Step 3: "재귀로 몇 번을 도나" (O(2ⁿ)의 벽)
Step 1에서 순수 재귀 피보나치가 O(2ⁿ)이라고 했죠. 말로만 들으면 감이 안 오니, 직접 세어 보겠습니다. 아까 코드에 있던 counter가 이때 쓰는 도구예요. 함수가 불릴 때마다 counter[0]을 1씩 올리도록 해 뒀으니, 이걸로 "몇 번 불렸나"를 실측할 수 있습니다.
fibonacci_naive(30)에 counter를 달아 돌려 보면 호출 수가 이렇게 찍힙니다.
fib(n) 순수 재귀 호출 수 — 지수로 폭발한다
n=10 177 번
n=20 21,891 번
n=30 2,692,537 번 ← 겨우 30인데 벌써 270만 번
n=40 331,160,281 번 ← 3.3억, 1초(1억)를 훌쩍 넘긴다
n=50 40,730,022,147 번 ← 407억, 사실상 끝나지 않는다
n이 10 늘 때마다 호출이 약 100배씩 뛴다 = O(2ⁿ)
fib(30) 하나 구하는 데 269만 번을 호출합니다. 답은 고작 832040인데, 그 답을 얻으려고 함수를 270만 번 불러요. 대부분이 아까 본 그 중복 계산이고요.
A-1의 "1초에 1억 연산" 잣대로 재 보면
A-1에서 세운 잣대 기억하시죠? 컴퓨터는 1초에 대략 1억 번 연산을 합니다. 이 자로 피보나치를 재 보면 벽이 정확히 어디인지 보여요.
fib(40)은 3.3억 번 호출이니 이미 1초를 넘깁니다. fib(50)은 407억 번 — 1초에 1억이니 400초, 거의 7분이에요. 코딩테스트에서 7분짜리 풀이는 그냥 시간 초과입니다. 순수 재귀 피보나치는 n이 40 근처만 돼도 손도 못 대는 알고리즘이에요.
여기서 E-3에서 봤던 그 딱한 처지가 그대로 돌아옵니다. 거스름돈 완전탐색도 "금액이 조금만 커지면 무너진다"였죠. 원인이 똑같아요. 겹치는 계산을 매번 처음부터 다시 하니까 호출이 지수로 폭발하는 겁니다.
왜 이렇게 느린가 — 나무가 아래로 두 배씩 넓어진다
깊이 0 : 1개 fib(n)
깊이 1 : 2개 fib(n-1), fib(n-2)
깊이 2 : 4개
깊이 3 : 8개
... 한 번 부를 때마다 갈래가 둘로 → 잎이 대략 2ⁿ개
깊이 n : 2ⁿ개 겹치는 값을 매번 다시 세면서 지수로 부푼다
그런데 우리는 이미 답을 알고 있습니다. Step 1 나무에서 봤듯이, fib(2)나 fib(3)은 한 번만 계산하면 되는 값이에요. 두 번째부터는 다시 계산할 게 아니라 적어 둔 걸 꺼내 쓰면 됩니다. 그 방법을 이제 배웁니다.
💡 한 줄 정리
순수 재귀 피보나치는 fib(30)에 269만 번, fib(40)에 3.3억 번, fib(50)에 407억 번 호출한다 — n이 10 늘 때마다 약 100배씩 뛰는 O(2ⁿ)이다. A-1의 "1초에 1억 연산" 잣대로는 fib(40)부터 시간 초과다. 원인은 E-3 거스름돈과 똑같이 겹치는 계산을 매번 처음부터 다시 하는 것이다.
🙋 학생 질문 — "호출 수가 269만인데 재귀 스택 공간은 왜 O(n)인가요? 269만 칸이 쌓이는 거 아닌가요?"
아주 예리한 질문이에요. 호출 횟수와 동시에 스택에 쌓이는 깊이를 구분하면 풀립니다.
재귀는 한 번에 한 갈래씩만 내려갑니다. fib(5)가 fib(4)를 부르면, fib(4)가 완전히 끝날 때까지 파고들어요. fib(4)는 fib(3)을, fib(3)은 fib(2)를… 이렇게 한 줄로 바닥까지 내려갑니다. 이때 스택에 쌓인 깊이는 n이에요. 바닥을 찍으면 하나씩 값을 돌려주며 되돌아 올라오고, 스택에서 빠집니다.
그러고 나서야 fib(5)가 두 번째 갈래인 fib(3)을 부르죠. 즉 269만 번의 호출이 동시에 쌓이는 게 아니라, 한 갈래를 끝까지 내려갔다 올라오고, 다음 갈래를 또 내려갔다 올라오는 식으로 순차적으로 일어납니다. 어느 순간이든 스택에 동시에 쌓여 있는 건 지금 내려가는 한 갈래뿐이라, 최대 깊이가 n입니다.
비유하면 이래요. 미로를 269만 번 걸음으로 헤매도, 내 손에 든 실타래(스택)는 입구부터 지금 위치까지의 한 줄뿐이죠. 지나온 다른 길들은 이미 되돌아 나왔으니 실이 감겨 있어요. 시간(총 걸음 수)은 2ⁿ, 공간(동시에 쌓인 깊이)은 n — 이 둘이 다르다는 걸 구분하는 게 재귀 복잡도 분석의 핵심입니다.
Step 4: "적어 두고 다시 쓴다" (메모이제이션, top-down)
드디어 그 한 문장을 코드로 옮길 차례입니다. "한 번 푼 건 적어 두고 다시 쓴다." E-3 마지막에 남겨 뒀던 그 생각이에요. 이 방식에 이름이 붙어 있습니다. 메모이제이션(memoization). 메모(memo)를 남긴다는 뜻 그대로예요.
핵심 아이디어는 놀랍도록 단순합니다. 순수 재귀는 그대로 두고, 함수 입구에 딱 한 겹만 씌웁니다. "이미 푼 값이면 계산하지 말고 꺼내 쓰고, 처음 보는 값이면 계산해서 적어 둔다." 적어 두는 공책 역할은 딕셔너리(dict)가 맡아요.
직접 만든 공책 — dict 메모이제이션 (원리 트랙)
먼저 원리를 눈으로 보기 위해 dict를 손으로 만들어 짜 보겠습니다.
def fibonacci_memo(n, counter=None):
memo = {} # 부분 문제의 답을 적어 두는 공책(top-down)
def fib(k):
if counter is not None:
counter[0] += 1
if k < 2: # 종료 조건: fib(0)=0, fib(1)=1
return k
if k in memo: # 이미 푼 값이면 계산하지 않고 꺼낸다
return memo[k]
memo[k] = fib(k - 1) + fib(k - 2) # 처음 보는 값만 계산해서 적어 둔다
return memo[k]
return fib(n)
fibonacci_naive와 점화식은 완전히 같아요. fib(k) = fib(k-1) + fib(k-2). 딱 두 줄만 추가됐습니다. if k in memo: return memo[k] — 이미 공책에 있으면 꺼내 쓰고, memo[k] = ... — 처음 계산한 값만 공책에 적어 둡니다. 이 두 줄이 지수를 선형으로 바꿔요.
공책이 채워지는 과정을 따라가 보면 왜 빨라지는지 한눈에 보입니다.
메모 공책이 채워지는 과정 — fib(5)를 값마다 딱 한 번씩만 푼다
fib(5)를 부르면 정의대로 아래로 내려간다.
처음 보는 값만 계산하고, 그 즉시 memo에 적는다:
fib(2) 계산 → memo = {2: 1}
fib(3) 계산 → memo = {2: 1, 3: 2}
fib(4) 계산 → memo = {2: 1, 3: 2, 4: 3}
fib(5) 계산 → memo = {2: 1, 3: 2, 4: 3, 5: 5}
두 번째부터 fib(2)·fib(3)을 다시 만나면 계산하지 않고 memo에서 즉시 꺼낸다.
→ Step 1에서 세 번·두 번 불리던 나무가 한 줄기로 접힌다.
Step 1의 폭발하던 나무가 기억나시죠? 그 나무에서 중복 갈래가 통째로 잘려 나갑니다. 각 값을 한 번씩만 계산하니까요.
실제로 호출 수를 세어 보면 극적입니다. fibonacci_memo(30)에 counter를 달면 59번이 찍혀요. 순수 재귀가 269만 번이던 바로 그 fib(30)을, 메모이제이션은 59번에 끝냅니다. 답은 물론 똑같은 832040이고요.
fib(30) — 같은 답, 호출 수는 하늘과 땅
순수 재귀 : 2,692,537 번
메모이제이션: 59 번 ← 269만 번이 59번으로
O(2ⁿ) → O(n)
내장 데코레이터 — @functools.cache (실전 트랙)
원리를 봤으니, 이제 실전 코딩테스트에서 쓰는 방식을 보겠습니다. 파이썬에는 방금 그 dict 공책을 자동으로 만들어 주는 도구가 표준 라이브러리에 있어요. functools.cache 데코레이터입니다.
@functools.cache
def fibonacci_cache(n):
if n < 2: # 종료 조건: fib(0)=0, fib(1)=1
return n
return fibonacci_cache(n - 1) + fibonacci_cache(n - 2)
파일 맨 위에 import functools 한 줄만 있으면 됩니다. 놀랍지 않나요? 함수 위에 @functools.cache 한 줄을 얹었을 뿐인데, 이건 순수 재귀 코드와 글자 하나 다르지 않아요. memo를 손으로 만들지도, if k in memo를 쓰지도 않았습니다. 그런데도 논리는 fibonacci_memo와 완전히 똑같이 돌아가요.
비결은 데코레이터입니다. @functools.cache는 함수 인자를 열쇠로, 반환값을 자동으로 적어 둬요. 같은 인자로 다시 부르면 함수 본문을 실행하지 않고 적어 둔 값을 꺼내 줍니다. 우리가 손으로 짠 공책 로직을 표준 라이브러리가 대신 해 주는 거예요.
이게 이 과목이 늘 강조하는 두 트랙입니다. 원리는 직접 짜서 무엇이 적히는지 눈으로 보고, 실전에서는 검증된 내장을 씁니다.
| 방식 | 코드 | 언제 쓰나 |
|---|---|---|
dict 직접 구현 (fibonacci_memo) |
memo = {}를 손으로 관리 |
원리를 볼 때 · 면접에서 물을 때 · 캐시를 세밀히 제어할 때 |
@functools.cache (fibonacci_cache) |
데코레이터 한 줄 | 🌟 실전 코딩테스트 — C로 구현돼 빠르고 버그가 없다 |
빅오는 둘 다 시간 O(n)·공간 O(n)입니다. 서로 다른 부분 문제가 0부터 n까지 n+1개뿐이고 각각 한 번씩만 계산하니 시간이 O(n)이고, 공책(memo)이 n칸에 재귀 스택이 n 깊이라 공간이 O(n)이에요. O(2ⁿ)이 O(n)으로 내려앉았습니다. 딱 두 줄, 혹은 데코레이터 한 줄로요.
💡 한 줄 정리
메모이제이션(top-down)은 순수 재귀에 "이미 푼 값이면 꺼내고 처음이면 적어 둔다"는 한 겹만 씌우는 방식이다. dict를 손으로 만들면 무엇이 적히는지 원리가 보이고(fibonacci_memo), 실전에선 @functools.cache 한 줄로 같은 효과를 낸다(fibonacci_cache). fib(30) 호출 수가 269만에서 59로 줄며 O(2ⁿ)이 O(n)이 된다.
🙋 학생 질문 — "코드를 위에서 아래로 읽으니까 큰 fib(30)부터 부르는데, 왜 이걸 top-down이라고 부르나요?"
이름의 "위(top)"가 코드의 위가 아니라 문제 크기의 위를 뜻해서 그래요. 문제를 큰 것에서 작은 것 순으로 풀어 나가는 방향이라 top-down입니다.
메모이제이션이 도는 순서를 따라가 보면 확실해져요. fib(30)을 부르면, 이 큰 문제를 풀기 위해 fib(29)와 fib(28)을 부릅니다. 큰 문제가 자기보다 작은 문제를 부르며 점점 아래로 내려가요. 바닥(fib(0), fib(1))에 닿으면 그때부터 값이 채워지며 되돌아 올라오죠. 그러니까 "가장 큰 문제에서 출발해 필요한 작은 문제를 그때그때 파고든다" — 이게 위에서 아래로(top-down)입니다.
반대 방향도 있습니다. fib(0), fib(1)처럼 가장 작은 문제부터 차곡차곡 풀어서 표를 채워 올라가는 방식이에요. 작은 것에서 큰 것으로 가니 아래에서 위로(bottom-up), 이걸 타뷸레이션이라고 부릅니다. 바로 다음 Step에서 배울 건데, 같은 점화식을 정반대 방향으로 푸는 거예요.
정리하면 top/bottom은 코드를 읽는 방향이 아니라 문제 크기를 다루는 방향입니다. 큰 문제에서 시작해 내려가면 top-down, 작은 문제에서 시작해 올라오면 bottom-up. 이 한 쌍이 오늘 수업의 뼈대예요.
Step 5: "표를 채워 올라간다" (타뷸레이션, bottom-up)
메모이제이션은 큰 문제에서 출발해 필요한 작은 문제를 파고들었죠(top-down). 이번엔 정반대로 가 봅니다. 가장 작은 문제부터 차례로 풀어 표를 채워 올라가는 방식, 타뷸레이션(tabulation)이에요. 표(table)를 채운다는 뜻입니다.
같은 피보나치를 이 방향으로 짜 볼게요.
def fibonacci_tabulation(n):
if n < 2: # fib(0)=0, fib(1)=1
return n
prev, curr = 0, 1 # dp[0], dp[1]
for _ in range(2, n + 1): # dp[2]부터 dp[n]까지 아래에서 위로
prev, curr = curr, prev + curr # 창 두 칸을 한 칸씩 민다 = dp[i]=dp[i-1]+dp[i-2]
return curr
재귀가 사라졌습니다. 대신 fib(0), fib(1)에서 출발해 반복문으로 fib(2), fib(3)… fib(n)까지 순서대로 올라가요. 점화식은 여전히 똑같아요. dp[i] = dp[i-1] + dp[i-2]. 방향만 반대일 뿐입니다.
표 전체가 필요 없다 — 롤링으로 공간 O(1)
여기서 눈여겨볼 게 있어요. 코드에 dp 배열이 안 보이고 prev, curr 변수 두 개만 있습니다. 왜냐면 dp[i]를 구하는 데 필요한 건 바로 앞 두 값(dp[i-1], dp[i-2])뿐이거든요. 표를 통째로 남길 이유가 없어요. 직전 두 값만 들고 한 칸씩 밀고 나가면 됩니다.
타뷸레이션 — 아래에서 위로, 창(window) 두 칸을 밀며 올라간다
dp: 0 1 1 2 3 5
[0] [1] [2] [3] [4] [5]
prev curr
prev curr prev, curr = curr, prev+curr
prev curr 를 되풀이하면 창이 오른쪽으로
prev curr 한 칸씩 밀려 올라간다
prev curr
표 전체를 남기지 않고 직전 두 값만으로 fib(n)에 닿는다 → 공간 O(n)이 O(1)로
이렇게 필요한 최근 값 몇 개만 변수로 굴리는 기법을 롤링(rolling)이라고 불러요. 피보나치·계단·타일링처럼 "직전 두 값만 있으면 되는" 점화식은 전부 이 롤링으로 공간을 O(1)까지 줄입니다.
top-down과 bottom-up, 나란히 놓고 보기
이제 같은 문제를 푸는 두 방향을 정리해 봅시다. 점화식은 완전히 똑같은데, 다루는 방향과 성질이 갈려요.
| 메모이제이션 (top-down) | 타뷸레이션 (bottom-up) | |
|---|---|---|
| 방향 | 큰 문제 → 작은 문제 (위→아래) | 작은 문제 → 큰 문제 (아래→위) |
| 구현 | 재귀 + 공책(memo) | 반복문 + 표(dp) |
| 재귀 스택 | 있음 (깊이 O(n)) | 🌟 없음 (깊은 입력에도 안전) |
| 점화식 | dp[i]=dp[i-1]+dp[i-2] |
dp[i]=dp[i-1]+dp[i-2] (같다) |
| 공간 | O(n) (memo) | 🌟 O(1)까지 (롤링 가능) |
시간은 둘 다 O(n)입니다. 각 부분 문제를 한 번씩만 푸니까요. 갈리는 건 공간과 재귀 스택이에요. 타뷸레이션은 재귀가 없어 스택이 넘칠 걱정이 없고, 롤링으로 공간을 O(1)까지 줄일 수 있습니다. 대신 메모이제이션은 순수 재귀 코드에 두 줄만 얹으면 되니 원래 완전탐색에서 가장 적게 고친다는 장점이 있죠. 어느 쪽이 나은지는 문제마다 다른데, 그 판단 기준은 오늘 마지막 생각해볼 주제에서 다룹니다.
💡 한 줄 정리
타뷸레이션(bottom-up)은 가장 작은 문제부터 반복문으로 표를 채워 올라가는 방식이다. 점화식은 top-down과 똑같지만 재귀가 없어 스택이 넘칠 걱정이 없고, 직전 두 값만 필요한 피보나치는 변수 두 개로 굴리는 롤링으로 공간을 O(n)에서 O(1)로 줄인다. 같은 점화식을 메모이제이션은 위에서 아래로, 타뷸레이션은 아래에서 위로 푼다.
🙋 학생 질문 — "둘이 시간도 같고 답도 같은데, 왜 굳이 두 방식을 다 배우나요? 하나만 쓰면 안 되나요?"
같은 답을 내니 얼핏 하나만 알면 될 것 같지만, 실전에서 둘을 가려 쓰면 낭패를 피할 수 있어요. 결정적인 차이가 하나 있거든요. 재귀 스택입니다.
파이썬은 재귀 깊이에 기본 한계가 있습니다(대략 1000). 메모이제이션은 재귀라서, 부분 문제가 아주 깊게 이어지는 문제(예: n이 10만인 계단)에서는 이 한계에 부딪혀 RecursionError로 죽어요. 물론 sys.setrecursionlimit으로 한계를 올릴 수 있지만, 너무 올리면 이번엔 실제 스택 메모리가 터집니다. 반면 타뷸레이션은 반복문이라 이런 걱정이 아예 없어요. n이 아무리 커도 안전합니다.
그래서 실전 감각은 이래요. 부분 문제가 얕으면(수백 깊이) 메모이제이션이 편합니다. 완전탐색 코드에 데코레이터 한 줄만 얹으면 되니까요. 그런데 입력이 커서 재귀가 깊어질 것 같거나, 공간을 O(1)로 짜내야 하면 타뷸레이션으로 갑니다.
또 하나, 직관의 차이도 있어요. 어떤 문제는 "큰 문제를 어떻게 쪼갤까"가 자연스럽고(top-down이 편함), 어떤 문제는 "작은 것부터 어떻게 쌓을까"가 자연스럽습니다(bottom-up이 편함). 두 방향을 다 손에 익혀 두면, 문제를 만났을 때 더 자연스러운 쪽을 골라 잡을 수 있어요. 그래서 오늘 거의 모든 문제를 두 방식으로 짝지어 봅니다.
Step 6: "마지막 걸음은 1칸일까 2칸일까" (계단 오르기)
피보나치로 도구는 다 갖췄습니다. 이제 그 도구를 진짜 문제에 써 볼 차례예요. 첫 타자는 코딩테스트 단골, 계단 오르기입니다.
문제는 이래요. n칸짜리 계단이 있고, 한 번에 1칸 또는 2칸씩 오를 수 있습니다. 꼭대기까지 오르는 방법이 몇 가지일까요? 3칸이면 (1,1,1), (1,2), (2,1) 세 가지죠.
점화식 세우기 — "마지막 한 걸음"으로 벗겨 낸다
Step 2의 질문 토글에서 예고한 그 방법을 씁니다. "n칸에 도착하는 마지막 한 걸음은 무엇인가?" 마지막 걸음은 딱 두 가지밖에 없어요. 1칸을 올라 도착했거나, 2칸을 올라 도착했거나.
n칸에 도착하는 마지막 한 걸음은 두 갈래뿐
... [n-2] [n-1] [ n ]
│ ↑
└ 1칸 올라 도착 → 그 전엔 (n-1)칸에 있었다 = dp[n-1]가지
│ ↑
└ 2칸 올라 도착 → 그 전엔 (n-2)칸에 있었다 = dp[n-2]가지
두 경우는 겹치지 않고 이 둘이 전부다
dp[n] = dp[n-1] + dp[n-2]
마지막 걸음이 1칸이었다면 그 직전엔 (n-1)칸에 서 있었을 테고, 그때까지 오는 방법은 dp[n-1]가지입니다. 2칸이었다면 (n-2)칸에 있었을 테니 dp[n-2]가지고요. 두 경우가 겹치지 않고 이 둘이 전부니, 합치면 dp[n] = dp[n-1] + dp[n-2]입니다.
어라, 이거 피보나치와 똑같은 점화식이네요! 다른 건 초깃값 하나뿐이에요. 계단은 dp[0]=1입니다. "0칸을 오르는 방법"은 "가만히 있는 한 가지"로 세거든요. 피보나치가 fib(0)=0이었던 것과 여기서만 갈립니다.
두 트랙으로 짜 보기
타뷸레이션(bottom-up)부터 볼게요. 피보나치 타뷸레이션과 판박이입니다. 초깃값만 다르죠.
def climb_stairs(n):
if n < 2: # 0칸·1칸은 한 가지뿐
return 1
prev, curr = 1, 1 # dp[0]=1, dp[1]=1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr # dp[i]=dp[i-1]+dp[i-2]
return curr
같은 문제를 메모이제이션(top-down)으로도 짜 봅니다. 방향만 반대예요.
def climb_stairs_memo(n):
memo = {}
def climb(k):
if k < 2: # 0칸·1칸은 한 가지
return 1
if k in memo: # 이미 구한 칸이면 꺼낸다
return memo[k]
memo[k] = climb(k - 1) + climb(k - 2)
return memo[k]
return climb(n)
두 함수는 같은 값을 냅니다. climb_stairs(5)도 climb_stairs_memo(5)도 8이에요. 실제로 값을 나열해 보면 dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8 — 피보나치 수열이 한 칸 밀린 모습입니다. 빅오는 둘 다 시간 O(n), 타뷸레이션은 롤링으로 공간 O(1), 메모이제이션은 공간 O(n)이고요.
코테에서 이렇게 나온다
계단 오르기는 "1차원 DP의 첫 관문"이라 불릴 만큼 자주 나옵니다. 그리고 변형이 무궁무진해요. 한 번에 1·2칸이 아니라 1·2·3칸씩 오를 수 있으면? 마지막 걸음이 세 갈래가 되니 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]으로 늘어납니다(오늘 기초 과제예요). 계단마다 점수가 있어 최댓값을 구하라면 +가 max로 바뀌고요. "마지막 한 걸음"으로 점화식을 세우는 감각 하나만 잡으면, 이 변형들이 전부 같은 골격에서 나옵니다.
💡 한 줄 정리
계단 오르기는 "n칸에 도착하는 마지막 걸음이 1칸이냐 2칸이냐"로 dp[n]=dp[n-1]+dp[n-2] 점화식이 나온다 — 피보나치와 같고 초깃값만 dp[0]=1로 다르다. 타뷸레이션(climb_stairs)과 메모이제이션(climb_stairs_memo) 두 트랙 모두 시간 O(n)이고, climb_stairs(5)=8이다. 걸음이 1·2·3칸이면 3항 점화식으로 자연스레 확장된다.
🙋 학생 질문 — "왜 첫 걸음이 아니라 하필 마지막 걸음으로 나누나요? 첫 걸음으로 나눠도 되지 않나요?"
첫 걸음으로 나눠도 답은 똑같이 나옵니다. 다만 마지막 걸음으로 나누는 게 점화식과 코드로 옮기기 훨씬 매끄러워서 관습처럼 그렇게 잡아요.
첫 걸음으로 나눠 볼게요. n칸을 오르는데 첫 걸음이 1칸이면 남은 건 (n-1)칸, 2칸이면 남은 건 (n-2)칸이죠. 그러니 방법(n) = 방법(n-1) + 방법(n-2). 어라, 결과는 똑같네요? 맞아요. 계단은 대칭적이라 첫 걸음이든 마지막 걸음이든 같은 점화식이 나옵니다.
그런데 마지막 걸음 기준이 편한 이유가 있어요. DP의 dp[i]는 보통 "i까지 오는(만드는) 방법·최솟값"으로 정의합니다. 즉 인덱스가 도착점을 가리켜요. 그러면 "dp[n]에 도달하는 마지막 선택"을 묻는 게 정의와 자연스럽게 맞아떨어집니다. dp[n]을 구하려고 dp[n-1], dp[n-2]라는 이미 계산해 둔 작은 인덱스를 참조하는 흐름이 딱 떨어지거든요.
거스름돈에서도 그랬죠. "마지막에 쓴 동전"을 빼면 더 작은 금액이 남았습니다. 배열 DP는 대부분 "지금 이 지점에 도달하는 마지막 선택은 몇 가지인가"로 점화식을 세워요. 그래서 마지막 걸음 기준을 익혀 두면, 계단이든 거스름돈이든 앞으로 만날 대부분의 1차원 DP에 그대로 통합니다.
Step 7: "격자를 도미노로 채우기" (2×n 타일링)
계단에서 "마지막 한 걸음"으로 점화식을 세웠죠. 이번엔 겉모습이 완전히 달라 보이는 문제를 하나 가져올게요. 그런데 풀어 보면 똑같은 점화식이 밑에 깔려 있습니다. DP의 묘미가 바로 여기예요.
문제는 타일링입니다. 2×n 격자(세로 2칸, 가로 n칸)를 2×1 도미노로 빈틈없이 채우는 방법이 몇 가지일까요? 도미노는 세로로 세우거나 가로로 눕힐 수 있어요.
A-2에서 격자를 좌표로 다뤄 봤고, E-2에서 미로를 격자로 훑어 봤죠. 그 격자 감각을 여기서 다시 씁니다. 2×5 격자면 이렇게 생겼어요.
2×5 격자 (세로 2칸 × 가로 5칸)
+--+--+--+--+--+
| | | | | |
+--+--+--+--+--+
| | | | | |
+--+--+--+--+--+
└ 맨 오른쪽 이 열을 어떻게 덮느냐로 경우가 갈린다
점화식 세우기 — "마지막 열"로 벗겨 낸다
계단에선 "마지막 걸음"이었죠. 타일링에선 "맨 오른쪽 열을 어떻게 채우는가"를 묻습니다. 방법이 딱 둘뿐이에요.
2×n 격자의 마지막 열(맨 오른쪽)을 채우는 방법은 둘뿐
[ 세로 도미노 1개 ] 마지막 한 열을 통째로 덮는다 → 남는 건 2×(n-1) = dp[n-1]
[ 가로 도미노 2개 ] 마지막 두 열을 위·아래로 덮는다 → 남는 건 2×(n-2) = dp[n-2]
두 경우가 전부이고 겹치지 않는다
dp[n] = dp[n-1] + dp[n-2] 계단·피보나치와 똑같은 점화식
세로 도미노 하나로 마지막 한 열을 통째로 덮으면, 남는 건 2×(n-1) 격자 — 방법은 dp[n-1]가지죠. 가로 도미노 두 개로 마지막 두 열을 위아래로 덮으면, 남는 건 2×(n-2) 격자 — dp[n-2]가지고요. (가로 도미노는 반드시 짝으로 두 열을 채운다는 걸 짚어 두세요. 위 칸만 가로로 덮으면 아래 칸이 붕 떠서 격자를 못 채웁니다.)
두 경우가 전부이고 겹치지 않으니 dp[n] = dp[n-1] + dp[n-2]. 또 피보나치입니다. 계단이랑 초깃값까지 똑같아요(dp[0]=1, dp[1]=1).
def tile_2xn(n):
if n < 2: # 0열은 빈 채움 한 가지, 1열은 세로 하나뿐
return 1
prev, curr = 1, 1 # dp[0]=1, dp[1]=1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr # dp[i]=dp[i-1]+dp[i-2]
return curr
climb_stairs와 코드가 글자까지 똑같죠? tile_2xn(5)는 8을 냅니다. 빅오도 같은 시간 O(n)·공간 O(1)이에요.
같은 점화식이 다른 문제 밑에 깔려 있다
여기서 오늘 수업에서 꼭 챙겨 갈 통찰이 나옵니다. 피보나치, 계단 오르기, 타일링 — 셋은 소재가 완전히 다릅니다. 수열, 계단, 도미노. 그런데 점화식은 모두 dp[n] = dp[n-1] + dp[n-2] 예요.
이게 DP를 배우는 진짜 이유입니다. 문제의 겉모습(수열이냐 계단이냐 격자냐)에 속지 않고, "지금 문제의 답이 어떤 작은 문제들로 조립되는가"라는 뼈대를 보는 눈을 기르는 거예요. 그 뼈대가 같으면, 소재가 아무리 달라도 같은 코드로 풀립니다. 코딩테스트에서 처음 보는 문제가 낯익게 느껴지는 순간이 바로 이 뼈대가 보일 때고요.
한 가지만 덧붙일게요. 타일링 같은 "경우의 수" 문제는 n이 커지면 답이 어마어마하게 커집니다. 그래서 실전 코테는 흔히 "답을 1,000,000,007로 나눈 나머지를 출력하라"고 요구해요(%1_000_000_007). 큰 수를 그대로 다루면 느려지니 매 단계에서 나머지만 들고 가는 건데, 파이썬은 큰 정수를 자동으로 다뤄서 오늘 코드엔 넣지 않았습니다. 개념만 기억해 두세요.
💡 한 줄 정리
2×n 타일링은 "맨 오른쪽 열을 세로 하나로 덮느냐(2×(n-1) 남음), 가로 둘로 덮느냐(2×(n-2) 남음)"로 dp[n]=dp[n-1]+dp[n-2] 점화식이 나온다 — 계단·피보나치와 완전히 같다. tile_2xn(5)=8, 시간 O(n)·공간 O(1). 소재가 달라도 같은 점화식이 밑에 깔린다는 게 DP의 묘미다.
🙋 학생 질문 — "소재가 다른데 점화식이 같은 게 우연인가요? 어떻게 미리 알아채나요?"
우연이 아니라 문제의 구조가 같아서 그래요. 그리고 알아채는 감각은 훈련으로 붙습니다.
세 문제의 공통점을 벗겨 보면 이렇습니다. 전부 "한 걸음에 두 종류의 선택이 있고, 하나는 크기를 1 줄이고 다른 하나는 2 줄인다"는 구조예요. 계단은 1칸/2칸 오르기, 타일링은 세로 하나(한 열)/가로 둘(두 열), 피보나치는 정의 자체가 앞의 하나·둘을 더하기. 선택지가 "1 줄이기"와 "2 줄이기" 두 개인 순간, 점화식은 무조건 dp[n] = dp[n-1] + dp[n-2]가 됩니다. 겉옷만 다를 뿐 뼈대가 같은 거죠.
그럼 어떻게 미리 알아채느냐. 처음엔 못 알아챕니다. 정상이에요. 그런데 이 세 문제를 직접 풀어 본 사람은, 네 번째로 "개구리가 1칸·2칸씩 징검다리를 건넌다" 같은 문제를 만나면 "어, 이거 계단이랑 같잖아?" 하고 알아봅니다. 소재는 개구리인데 구조가 판박이거든요.
그래서 실전 감각은 소재를 지우고 선택지의 개수와 크기만 보는 겁니다. "이 문제에서 한 걸음에 갈 수 있는 선택은 몇 가지고, 각각 문제를 얼마나 줄이나?" 이 질문으로 뼈대를 뽑으면, 처음 보는 문제도 이미 아는 점화식으로 내려앉아요. 유형을 다섯 개쯤 풀면 여섯 번째부터 눈에 들어오기 시작합니다.
Step 8: "상태 정의가 점화식을 결정한다" (1차원 DP 정리)
지금까지 만난 세 문제(피보나치·계단·타일링)는 점화식이 전부 +, 즉 더하기였어요. 그런데 DP 점화식이 늘 더하기인 건 아닙니다. 이번 Step에서 세 가지 다른 모양의 점화식을 보고, 마지막으로 E-3 거스름돈의 복선을 완전히 회수하겠습니다.
거스름돈의 최종 회수 — 지수를 다항으로
먼저 오늘의 출발점이었던 거스름돈으로 돌아갑니다. E-3에서 완전탐색은 답을 맞혔지만 지수 시간이라 무너졌죠. 이제 DP로 다시 풀어 봅시다. Step 2에서 점화식을 이미 세워 뒀어요. dp[a] = min(dp[a-coin] + 1).
메모이제이션(top-down)부터 볼게요. E-3 완전탐색 재귀에 공책 한 겹만 씌운 겁니다.
def min_coins_memo(amount, coins):
memo = {} # 남은 금액 → 그 금액의 최소 동전 수
def search(remaining):
if remaining == 0: # 딱 맞췄다 — 더 쓸 동전이 없다
return 0
if remaining < 0: # 넘어섰다 — 이 가지는 가망 없다
return float("inf")
if remaining in memo: # 이미 푼 금액이면 다시 파지 않고 꺼낸다
return memo[remaining]
fewest = float("inf")
for coin in coins: # 동전 하나를 쓰는 모든 경우 중 최소
fewest = min(fewest, search(remaining - coin) + 1)
memo[remaining] = fewest # 처음 푼 금액만 적어 둔다
return fewest
result = search(amount)
return -1 if result == float("inf") else result
E-3의 min_coins_bruteforce와 뼈대가 똑같은 게 보이시죠? if remaining in memo와 memo[remaining] = fewest 두 줄만 추가됐습니다. 이 두 줄이 E-3에서 remaining=3을 몇 번이고 다시 파던 낭비를 없애요. 한 번 푼 금액은 공책에서 꺼내 쓰니까요.
타뷸레이션(bottom-up)으로도 짜 봅니다. 0원부터 위로 표를 채워 올라가요.
def min_coins_tabulation(amount, coins):
dp = [0] + [float("inf")] * amount # dp[0]=0, 나머지는 아직 못 만듦(inf)
for a in range(1, amount + 1): # 1원부터 amount원까지 아래에서 위로
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1 # 동전 하나 뺀 자리 + 1이 더 적으면 갱신
return -1 if dp[amount] == float("inf") else dp[amount]
dp[0]=0(0원은 동전 0개)에서 시작해, 아직 못 만든 금액은 무한대(inf)로 둡니다. 그리고 각 금액마다 "동전 하나 뺀 자리의 값 + 1"이 지금보다 적으면 갱신해요. 끝까지 무한대로 남으면 만들 수 없다는 뜻이라 -1을 돌려줍니다.
세 함수가 같은 답을 내는지 확인해 볼게요. [1, 3, 4]로 6원을 거스르면 — E-3의 min_coins_bruteforce도, 오늘의 min_coins_memo도, min_coins_tabulation도 전부 2(3+3)를 냅니다. [3]으로 5원은 셋 다 -1(못 만듦)이고요.
거스름돈 — E-3 완전탐색의 복선을 회수한다
6원을 [1,3,4]로 : E-3 min_coins_bruteforce → 2 (지수 시간)
E-4 min_coins_memo → 2 (다항 O(amount×종류))
E-4 min_coins_tabulation → 2 (다항 O(amount×종류))
같은 답, 다른 속도. 지수 O(len(coins)^(amount/최소동전)) → O(amount × len(coins))
답은 똑같은데 빅오가 완전히 달라졌어요. 시간이 O(amount × len(coins))입니다. 서로 다른 부분 문제(남은 금액)가 0부터 amount까지 amount+1개뿐이고, 각 금액에서 동전 종류 수만큼만 살펴보니까요. E-3에서 지수라 손도 못 대던 큰 금액이, 이제 눈 깜짝할 사이에 풀립니다. E-3 마지막에 흘려 뒀던 복선이 여기서 회수됐어요.
최소형 점화식 — 1로 만들기 (그리디가 틀리는 문제)
거스름돈의 min처럼, 점화식이 여러 갈래 중 가장 작은 것을 고르는 유형을 하나 더 보겠습니다. 1로 만들기예요. 어떤 수 n에 세 가지 연산(1 빼기, 2로 나누기, 3으로 나누기)을 써서 1로 만드는 최소 연산 수를 구합니다.
def make_1(n):
dp = [0] * (n + 1) # dp[0], dp[1]=0에서 시작
for i in range(2, n + 1):
best = dp[i - 1] # 1을 빼는 경우
if i % 2 == 0:
best = min(best, dp[i // 2]) # 2로 나누는 경우
if i % 3 == 0:
best = min(best, dp[i // 3]) # 3으로 나누는 경우
dp[i] = best + 1 # 셋 중 가장 짧은 자리 + 이번 연산 1번
return dp[n]
make_1(10)은 3을 냅니다(10→9→3→1). 여기서 중요한 건, 이 문제가 그리디로는 틀린다는 거예요. "가장 큰 나눗셈부터 하면 빨리 줄겠지" 싶어 10을 2로 나눠 5로 가면 손해입니다. 5에서 1까지 또 여러 번 걸리거든요. 오히려 1을 빼서 9로 간 다음 3으로 두 번 나누는 게 짧아요(10→9→3→1, 3번). E-3에서 배운 그대로, 눈앞의 최선(큰 나눗셈)이 전체의 최선이 아닌 경우입니다.
그래서 그리디처럼 한 갈래만 믿지 않고, 세 연산으로 갈 수 있는 경우들을 표에 다 채워 두고 그중 최소를 고르는 DP가 필요해요. 점화식이 +가 아니라 min(...) + 1인 이유가 이겁니다. "여러 선택 중 최선"을 골라야 하니까요.
한 가지 짚을 게 있어요. 이 문제는 롤링으로 공간을 O(1)로 못 줄입니다. dp[i//2], dp[i//3]이 바로 앞이 아니라 멀리 떨어진 칸을 참조하거든요. 그래서 표 전체가 필요해 공간 O(n)입니다. 시간은 각 수마다 최대 세 갈래만 보니 O(n)이고요.
경우의 수형 점화식 — 동전 조합 수 (누적합)
세 번째 모양은 누적합입니다. 같은 동전 문제인데 이번엔 "최소 개수"가 아니라 "몇 가지 조합으로 만들 수 있나"를 세요. [1, 2]로 3원을 만드는 조합은 {1,1,1}과 {1,2} 두 가지죠.
def coin_change_ways(amount, coins):
dp = [1] + [0] * amount # dp[0]=1: 0원은 '아무것도 안 쓰는' 한 가지
for coin in coins: # 동전을 바깥 루프에 두면 순서 무관 조합만 센다
for a in range(coin, amount + 1):
dp[a] += dp[a - coin] # coin을 한 번 더 쓰는 조합들을 더한다
return dp[amount]
coin_change_ways(5, [1, 2, 5])는 4를 냅니다. 점화식이 min도 +1도 아니라 dp[a] += dp[a-coin], 즉 여러 갈래를 모두 더하는 누적합이에요. "최소 하나"를 고르는 게 아니라 "가능한 방법을 전부 세는" 문제라 더하기가 맞죠.
여기서 미묘한 포인트 하나. 동전을 바깥 루프에 둔 게 핵심입니다. 이렇게 하면 늘 "작은 동전 → 큰 동전" 순서로만 조합을 쌓아서, {1,2}와 {2,1}을 같은 조합으로 한 번만 세요. 만약 동전을 안쪽 루프에 두면 순서를 구분해 순열을 세게 됩니다 — 아예 다른 문제가 돼요. 루프 순서 하나가 "조합이냐 순열이냐"를 가릅니다.
상태 정의가 점화식을 결정한다
오늘 만난 여섯 문제의 점화식을 세 유형으로 묶어 볼게요.
| 유형 | 점화식 모양 | 대표 함수 | 무엇을 하나 |
|---|---|---|---|
| 합형 | dp[i] = dp[i-1] + dp[i-2] |
피보나치·계단·타일링 | 앞의 답들을 더한다 |
| 최소형 | dp[i] = min(...) + 1 |
거스름돈·1로 만들기 | 여러 갈래 중 가장 작은 것 |
| 경우의 수형 | dp[a] += dp[a-coin] |
동전 조합 수 | 여러 갈래를 모두 더한다 |
점화식 모양이 문제마다 다르죠? 그런데 이 모양을 결정하는 건 딱 하나예요. dp[i]를 무엇으로 정의했는가. "i까지의 방법 수"로 정의하면 더하기가 나오고, "i를 만드는 최소 연산"으로 정의하면 min이 나오고, "i를 만드는 조합 수"로 정의하면 누적합이 나옵니다. 그래서 DP의 진짜 첫 단추는 점화식이 아니라 상태 정의 — "dp[i]가 정확히 무슨 값인가"를 한 문장으로 분명히 정하는 것이에요. 이게 정해지면 점화식은 따라 나옵니다.
상태가 하나면 1차원, 여럿이면? (다음 시간의 문)
여기서 다음 시간을 향한 문을 하나 열어 두겠습니다. 오늘 우리가 다룬 모든 dp를 보세요. dp[n], dp[a] — 전부 숫자 하나로 상태를 표현했습니다. 계단은 "몇 번째 칸(n)", 거스름돈은 "남은 금액(a)". 상태가 하나라서 dp가 1차원 배열 하나면 충분했어요.
그런데 상태를 하나로는 표현할 수 없는 문제들이 있습니다. 배낭에 물건을 담는데 "몇 번째 물건까지 봤나"와 "남은 무게가 얼마나"를 동시에 기억해야 하는 문제. 두 문자열이 얼마나 닮았나를 재는데 "첫 문자열의 몇 번째"와 "둘째 문자열의 몇 번째"를 함께 들고 가야 하는 문제. 이런 건 상태가 둘이라, dp[i][j]처럼 2차원 표가 필요해요.
상태가 하나면 1차원, 여럿이면 2차원. 다음 시간(E-5)에 이 2차원 DP의 세계로 넘어갑니다. 오늘 잡은 "상태 정의 → 점화식" 감각이 그대로 한 차원 위로 올라갈 뿐이에요.
💡 한 줄 정리
DP 점화식은 세 모양이 있다 — 합형(dp[i]=dp[i-1]+dp[i-2], 피보나치·계단·타일링), 최소형(min(...)+1, 거스름돈·1로 만들기), 경우의 수형(dp[a]+=dp[a-coin], 동전 조합 수). 이 모양을 결정하는 건 "dp[i]가 무슨 값인가"라는 상태 정의다. E-3 거스름돈이 DP로 지수에서 O(amount×종류)로 내려앉았고, 상태가 하나라 전부 1차원 배열로 풀렸다.
🙋 학생 질문 — "같은 동전 문제인데 min_coins랑 coin_change_ways가 왜 완전히 다른 코드인가요?"
정말 좋은 관찰이에요. 입력(금액과 동전)이 똑같은데 코드가 딴판인 이유는, 묻는 게 다르기 때문입니다. 그리고 묻는 게 다르면 상태 정의가 다르고, 상태 정의가 다르면 점화식이 다릅니다.
min_coins는 "최소 몇 개의 동전으로 만드나"를 묻습니다. 그러니 상태 정의가 "a원을 만드는 최소 동전 수"예요. 여러 갈래(어떤 동전을 마지막에 쓰나) 중 가장 적은 것을 골라야 하니 점화식에 min이 들어갑니다. 그리고 "가장 좋은 하나"만 세니 {1,2}와 {2,1}이 같은지 다른지는 신경 쓸 필요가 없어요.
coin_change_ways는 "몇 가지 조합으로 만드나"를 묻죠. 상태 정의가 "a원을 만드는 조합의 수"입니다. 가능한 방법을 전부 세야 하니 점화식이 +=(누적합)이고, 이번엔 {1,2}와 {2,1}을 한 번만 세도록 동전을 바깥 루프에 두는 장치가 반드시 필요해요. "최소"에선 안 중요하던 중복 문제가 "가짓수"에선 결정적이 됩니다.
그래서 얻어 갈 교훈은 이거예요. "동전 문제"라는 소재가 아니라 "무엇을 묻는가"가 알고리즘을 정한다. 최소를 물으면 min형, 가짓수를 물으면 누적합형, 방법의 존재만 물으면 또 다른 형(True/False)이 됩니다. 코딩테스트에서 비슷해 보이는 문제에 낚이지 않으려면, 소재를 지우고 "정확히 무슨 값을 구하라는 거지?"를 먼저 분명히 정하는 습관이 중요해요. 그게 상태 정의고, DP의 첫 단추입니다.
마무리
오늘은 "문제를 푸는 다섯 사고법"의 마지막, 동적 계획법의 문을 열었습니다. E-3 마지막에 남겨 둔 "한 번 푼 건 적어 두고 다시 쓴다"는 한 문장이 출발점이었죠. 피보나치로 중복 부분 문제가 어떻게 지수로 폭발하는지 봤고, 메모이제이션과 타뷸레이션 두 방향으로 그걸 다항으로 접었어요. 계단과 타일링에서 같은 점화식이 다른 소재 밑에 깔려 있다는 걸 확인했고, 마지막으로 거스름돈 완전탐색을 DP로 다시 풀어 E-3의 복선을 회수했습니다.
오늘 배운 핵심 세 가지
- 💡 하나 — DP는 겹치는 부분 문제를 한 번만 풀어 적어 두는 전략이다. 순수 재귀 피보나치는
fib(2)를 세 번 다시 풀며 O(2ⁿ)으로 폭발했다(fib(30)에 269만 번). DP가 통하는 조건은 둘 — 같은 작은 문제가 되풀이되는 겹치는 부분 문제와, 큰 답이 작은 답으로 조립되는 최적 부분 구조다. 이 둘이 맞으면 "지금 문제 = 더 작은 문제들"이라는 점화식을 세울 수 있다. - 💡 둘 — 같은 점화식을 두 방향으로 푼다. 메모이제이션(top-down)은 순수 재귀에 공책 한 겹을 씌우고(
dict직접 또는@functools.cache한 줄), 타뷸레이션(bottom-up)은 작은 문제부터 표를 채워 올라간다. 둘 다 시간 O(n)이지만, 타뷸레이션은 재귀 스택이 없어 깊은 입력에 안전하고 롤링으로 공간을 O(1)까지 줄인다.fib(30)호출이 269만에서 59로 접혔다. - 💡 셋 — 상태 정의가 점화식을 결정한다.
dp[i]를 "방법 수"로 정의하면 합형(+), "최소 연산"으로 정의하면 최소형(min), "조합 수"로 정의하면 누적합형(+=)이 나온다. 거스름돈이 지수에서 O(amount×종류)로 내려앉으며, 상태가 하나뿐이라 전부 1차원 배열로 풀렸다.
돌아보면 오늘의 한 줄기는 "겹치는 걸 알아챈다 → 점화식으로 표현한다 → 적어 두고 다시 쓴다"였어요. E-3에서 "그리디는 매 순간의 최적을 믿고, DP는 전체 최적을 계산한다"고 했죠. 오늘 그 "전체 최적을 계산하는 법"의 기초를 손에 넣었습니다.
다음 시간 예고
다음 시간(E-5)엔 동적 계획법 ②로 넘어갑니다. 오늘 우리가 다룬 dp는 전부 숫자 하나로 상태를 표현했어요. dp[n](몇 번째 칸), dp[a](남은 금액). 상태가 하나라 1차원 배열 하나면 충분했죠.
그런데 상태를 하나로는 담을 수 없는 문제들이 있습니다. 배낭 문제 — "몇 번째 물건까지 봤나"와 "남은 무게가 얼마인가"를 동시에 기억해야 해요. 최장 공통 부분 수열(LCS) — 두 문자열의 위치를 각각 들고 가야 하고요. 상태가 둘이면 dp[i][j], 즉 2차원 표가 필요합니다.
핵심 감각은 오늘 그대로예요. "상태를 무엇으로 정의할 것인가" 를 먼저 못 박고, 거기서 점화식을 끌어냅니다. 오늘 1차원에서 잡은 그 첫 단추가 한 차원 위로 올라갈 뿐이에요. 상태가 하나 늘면 표가 한 차원 늘어난다 — 다음 시간엔 그 2차원 표를 채우는 법을 배웁니다.
과제
오늘 배운 1차원 DP를 손에 붙이는 문제들입니다. 코드베이스 algorithms/dp.py의 함수를 참고하되, 각 문제를 점화식부터 한 줄로 세운 다음 메모이제이션·타뷸레이션 중 편한 방식으로 짜 보세요. 그리고 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.
[기초] 1·2·3칸 계단 오르기
Step 6의 계단 오르기를 확장합니다. 이번엔 한 번에 1칸, 2칸, 또는 3칸씩 오를 수 있어요. n칸 계단을 오르는 방법의 수를 구하는 climb_stairs_123(n)을 작성하세요. 예를 들어 climb_stairs_123(3)은 4입니다((1,1,1), (1,2), (2,1), (3) 네 가지).
- 마지막 한 걸음이 이번엔 몇 갈래인가요? 1칸·2칸이면 두 갈래라
dp[n-1]+dp[n-2]였습니다. 세 갈래가 되면 점화식이 어떻게 늘어날까요? - 초깃값을 조심하세요.
dp[0],dp[1],dp[2]를 각각 손으로 세어 두고 시작해야 합니다. - 시간·공간 복잡도를 빅오로 적으세요. 직전 세 값만 필요하다면 롤링으로 공간을 어디까지 줄일 수 있을까요?
[응용] 이웃하지 않게 골라 최대합
정수 리스트 nums가 주어질 때, 서로 이웃한 원소는 함께 고를 수 없다는 규칙 아래 고른 원소들의 합을 최대로 만드는 max_non_adjacent_sum(nums)을 작성하세요. 예를 들어 max_non_adjacent_sum([3, 2, 7, 10])은 13(3+10), max_non_adjacent_sum([3, 2, 5, 10, 7])은 15(3+5+7)입니다.
- "i번째 원소를 고르는가 마는가"로 갈래를 나눠 보세요. i번째를 고르면 i-1번째는 절대 못 고릅니다. 그럼 i-2번째까지의 최선에
nums[i]를 더해야겠죠. - i번째를 안 고르면? i-1번째까지의 최선이 그대로 이어집니다. 이 두 경우 중 큰 쪽을 고르는 게 점화식이에요 —
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). - 최소형이 아니라 최대형이라는 것만 다릅니다. 빅오는 얼마이고, 공간은 롤링으로 어디까지 줄일 수 있나요?
[심화] 최소 연산의 경로까지 복원하기
Step 8의 make_1(n)은 최소 연산 횟수만 돌려줬습니다. 이번엔 그 최소 횟수에 더해, 실제로 어떤 연산을 거쳤는지 경로까지 복원하는 make_1_path(n)을 작성하세요. 예를 들어 make_1_path(10)은 (3, [10, 9, 3, 1])처럼 최소 횟수와 거쳐 간 수의 순서를 함께 돌려줍니다.
dp[i]를 채울 때, "어느 자리에서 왔는지"를 함께 기록하는 배열을 하나 더 두세요.dp[i]가dp[i-1]에서 왔다면 그 사실을from[i] = i-1처럼 남기는 겁니다.- 표를 다 채운 뒤,
n에서 시작해from을 거꾸로 따라가면 경로가 나옵니다. 1에 닿을 때까지 되짚어 올라간 다음 뒤집으면 되죠. - DP에서 "값"뿐 아니라 "그 값이 어디서 왔는지"를 함께 기록하는 이 역추적(backtracking) 기법은 최단 경로 복원 등에서 두고두고 쓰입니다. 시간·공간 복잡도가 원래
make_1과 비교해 어떻게 바뀌는지도 적어 보세요.
생각해볼 주제
1. 메모이제이션과 타뷸레이션, 실전에선 무엇을 언제 꺼낼까
오늘 같은 문제를 두 방향으로 풀어 봤습니다. 답도 같고 시간 복잡도도 같았죠. 그런데 실전에선 선택이 갈립니다. 메모이제이션은 완전탐색 코드에 한 겹만 얹으면 되지만 재귀 깊이 한계에 걸릴 수 있고, 타뷸레이션은 그런 걱정이 없는 데다 롤링으로 공간을 O(1)까지 줄일 수 있지만 점화식을 아래에서부터 다시 짜야 합니다. 입력 크기, 재귀 깊이, 공간 제약, 그리고 "어느 쪽이 더 직관적인가"까지 엮어서, 여러분이라면 어떤 기준으로 둘 중 하나를 고를지 정리해 보세요.
2. 처음 보는 문제가 DP인지 어떻게 알아챌까
DP가 통하는 조건은 겹치는 부분 문제와 최적 부분 구조 두 가지라고 배웠습니다. 하지만 시험장에서 문제를 처음 만나면 이 두 성질이 대놓고 적혀 있지 않죠. 완전탐색으로 접근했더니 같은 계산이 되풀이되는 게 보인다거나, "최소·최대·경우의 수"를 묻는다거나, 입력 크기가 완전탐색엔 크고 그리디엔 반례가 있다거나 — 이런 신호들을 어떻게 조합해 "아, 이건 DP구나"를 감지할 수 있을까요? A-1의 입력 크기 잣대와 E-3의 그리디 반례 감각까지 함께 엮어 여러분만의 판별 체크리스트를 만들어 보세요.
3. @functools.cache를 실전에서 믿고 써도 될까
오늘 dict를 손으로 짠 메모이제이션과 @functools.cache 한 줄을 나란히 봤습니다. 내장이 더 짧고 빠르고 버그도 없으니 늘 이걸 쓰면 될 것 같지만, 캐시가 함수에 눌러붙어 호출 사이에 값이 남는다는 성질(전역 상태처럼 동작)이 때로 발목을 잡습니다. 같은 함수를 다른 입력 집합으로 여러 번 부르거나, 캐시가 메모리를 계속 붙잡고 있는 상황을 상상해 보세요. 내장 캐시를 믿고 쓸 때와 직접 dict로 제어해야 할 때를 무엇으로 가를지, 그리고 애초에 원리를 직접 짜 보는 값어치가 어디에 있는지 정리해 보세요.
✅ 예시 답안정답 보기
🎯 [과제 1 예시답안] 1·2·3칸 계단 오르기
채점 포인트
| 포인트 | 설명 | 배점 |
|---|---|---|
| 3항 점화식 유도 | 마지막 걸음이 세 갈래(1·2·3칸)라 dp[n]=dp[n-1]+dp[n-2]+dp[n-3]으로 넓혔는가 |
상 |
| 초깃값 dp[0..2] | dp[0]=1, dp[1]=1, dp[2]=2를 손으로 세어 못 박았는가 |
상 |
| 롤링 O(1) | 직전 세 값만 변수로 굴려 공간을 O(1)로 줄였는가 | 중 |
| 빅오 표기 | 시간 O(n)·공간 O(1)을 명시했는가 | 중 |
| 트리보나치 인식 | 2항 피보나치의 3항 확장(트리보나치)임을 알아챘는가 | 하 |
풀이 예시
Step 6에서 "마지막 한 걸음이 1칸이냐 2칸이냐"로 dp[n]=dp[n-1]+dp[n-2]를 세웠죠. 이번엔 한 걸음이 1·2·3칸 세 갈래입니다. 그러니 n칸에 닿는 마지막 걸음도 세 가지 — (n-1)칸에서 1칸, (n-2)칸에서 2칸, (n-3)칸에서 3칸을 올라온 경우예요. 세 경우가 겹치지 않고 이 셋이 전부니 그냥 셋을 더합니다. 피보나치(2항)가 트리보나치(3항)로 넓어진 것뿐이에요.
def climb_stairs_123(n):
if n == 0: # 0칸은 가만히 있는 한 가지
return 1
if n == 1: # 1칸은 한 걸음뿐
return 1
if n == 2: # (1,1)·(2) 두 가지
return 2
a, b, c = 1, 1, 2 # dp[0], dp[1], dp[2]
for _ in range(3, n + 1): # dp[3]부터 dp[n]까지 아래에서 위로
a, b, c = b, c, a + b + c # 창 세 칸을 한 칸씩 민다 = dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
return c
빅오는 시간 O(n)·공간 O(1)입니다. 3부터 n까지 한 번씩만 훑고, 직전 세 값(a, b, c)만 들고 한 칸씩 밀어 가니까요. 계단·피보나치에서 쓴 롤링 그대로예요. dp 배열을 통째로 들면 공간이 O(n)이지만, 필요한 건 늘 창 세 칸뿐이라 O(1)로 짜냅니다.
climb_stairs_123(5) — 직전 세 값을 더하며 아래에서 위로
dp[0] = 1 가만히 있는 한 가지
dp[1] = 1 한 걸음
dp[2] = 2 (1,1)·(2)
dp[3] = dp[2]+dp[1]+dp[0] = 2+1+1 = 4
dp[4] = dp[3]+dp[2]+dp[1] = 4+2+1 = 7
dp[5] = dp[4]+dp[3]+dp[2] = 7+4+2 = 13
실행 예시로 확인하면 climb_stairs_123(3)은 4((1,1,1)·(1,2)·(2,1)·(3)), (4)는 7, (5)는 13입니다.
흔한 실수 둘을 짚을게요. 첫째, 2항 점화식을 그대로 쓰기입니다. dp[n-3]을 빼먹고 dp[n-1]+dp[n-2]로 두면 climb_stairs_123(3)이 4가 아니라 3이 나와요. 3칸을 한 번에 오르는 (3) 한 가지가 통째로 빠지거든요. 둘째, 초깃값 dp[2]=2를 놓치기입니다. dp[2]를 1로 잘못 두면 그 오차가 위로 계속 번져 답이 어긋나요. 새 갈래가 생기면 점화식만 고치는 게 아니라 초깃값을 손으로 다시 세는 습관이 필요합니다.
💡 튜터의 한마디: 백준 9095 "1, 2, 3 더하기"가 이 문제 그대로예요(n을 1·2·3의 합으로 만드는 방법의 수 = 이 계단). 챙길 감각은 "선택지가 늘면 점화식의 항이 늘고, 초깃값도 함께 늘어난다"입니다. 계단이 1·2·3칸이면 3항, 계단마다 점수를 매겨 최댓값을 구하라면 +가 max로 바뀌고요. 소재가 아무리 달라도 "마지막 한 걸음이 몇 갈래인가"만 세면 점화식은 저절로 나옵니다. 이건 정답 공식이라기보다 1차원 DP를 읽는 가장 빠른 입구예요.
🎯 [과제 2 예시답안] 이웃하지 않게 골라 최대합
채점 포인트
| 포인트 | 설명 | 배점 |
|---|---|---|
| 점화식 유도 | dp[i]=max(dp[i-1], dp[i-2]+nums[i])를 "고른다/안 고른다"로 세웠는가 |
상 |
| 한 칸 건넌 앞 참조 | 고를 때 바로 앞(dp[i-1])이 아니라 한 칸 건넌 dp[i-2]를 참조했는가 |
상 |
| 음수 처리 규칙 | "안 골라도 되며 최소 0" 규칙으로 전부 음수면 0을 돌려주는가 | 중 |
| 롤링 O(1) | 직전 두 dp 값만 변수로 굴렸는가 | 중 |
| 빅오 표기 | 시간 O(n)·공간 O(1) | 하 |
풀이 예시
각 원소 앞에서 판단은 딱 둘입니다 — 고르거나, 안 고르거나. 안 고르면 바로 앞까지의 최선(dp[i-1])이 그대로 이어져요. 고르면 이웃한 앞 원소는 못 쓰니, 한 칸 건넌 앞의 최선(dp[i-2])에 지금 값을 더합니다. 둘 중 큰 쪽이 여기까지의 최선이에요. 이웃 제약 때문에 "바로 앞"이 아니라 "한 칸 건넌 앞"을 참조하는 게 이 DP의 핵심입니다.
# algorithms/exercises_e4.py
def max_non_adjacent_sum(nums):
prev2, prev1 = 0, 0 # dp[i-2], dp[i-1] — 0에서 시작(안 고르면 0)
for num in nums:
cur = max(prev1, prev2 + num) # 안 고른다(prev1) vs 고른다(한 칸 건넌 자리 + num)
prev2, prev1 = prev1, cur # 창 두 칸을 한 칸씩 민다
return prev1
두 롤링 변수 prev2, prev1을 0에서 시작한 게 음수 처리의 핵심입니다. 두 값이 늘 0 이상으로 유지되니, 음수를 더한 후보는 "안 고른" 후보(0 이상)에 밀려 절대 뽑히지 않아요. "아무것도 안 골라도 되며 합의 최소는 0"이라는 규칙이 코드 한 줄 없이 저절로 지켜집니다.
max_non_adjacent_sum([3, 2, 7, 10]) — 고른다 vs 안 고른다
시작 prev2=0 prev1=0
3 → max(0, 0+3) = 3 안 고름 0 vs 고름 0+3 → prev1=3
2 → max(3, 0+2) = 3 안 고름 3 vs 고름 0+2 → prev1=3
7 → max(3, 3+7) = 10 안 고름 3 vs 고름 3+7 → prev1=10
10 → max(10, 3+10)= 13 안 고름 10 vs 고름 3+10 → prev1=13
답 13 (3+10)
빅오는 시간 O(n)·공간 O(1)입니다. 리스트를 한 번 훑고 변수 두 개만 굴리니까요. 실행 예시로 확인하면 max_non_adjacent_sum([3, 2, 7, 10])은 13(3+10), ([3, 2, 5, 10, 7])은 15(3+5+7), ([-1, -2])는 0(음수뿐이라 안 고름)입니다.
흔한 실수 둘입니다. 첫째, 바로 앞을 참조하기. dp[i-2]+nums[i]가 아니라 dp[i-1]+nums[i]로 두면 이웃한 두 원소를 함께 골라 버려 규칙이 깨집니다. [3, 2, 7, 10]에서 2와 7을 나란히 고르는 답이 나오는 식이죠. 둘째, 음수뿐일 때 0을 못 내기. 시작값을 nums[0]으로 잡거나 음수 처리를 빼먹으면 [-1, -2]가 -1을 돌려줍니다. "안 골라도 된다"는 규칙을 초깃값 0으로 심어 두는 게 안전해요.
💡 튜터의 한마디: LeetCode 198 "House Robber"(Medium)와 백준 "도둑" 유형이 이 문제 그대로예요(이웃한 집은 함께 못 털죠). 챙길 감각은 "고른다 / 안 고른다"의 이진 선택으로 상태를 나누는 골격입니다. 이 발상이 앞으로 배울 배낭 문제(물건을 담느냐 마느냐)·부분집합 DP로 그대로 이어져요(배낭은 다음 시간 E-5라 지금은 개념만). "매 원소에서 넣을까 뺄까"를 저울질하는 유형이 보이면, 오늘 이 점화식이 뼈대라는 걸 기억하세요.
🎯 [과제 3 예시답안] 최소 연산의 경로까지 복원하기
채점 포인트
| 포인트 | 설명 | 배점 |
|---|---|---|
| came_from 기록 | dp[i]를 정할 때 고른 연산의 도착지를 came_from[i]에 함께 남겼는가 |
상 |
| 역추적 복원 | n에서 came_from을 따라 1까지 거슬러 경로를 만들었는가 |
상 |
| make_1과 횟수 일치 | 반환 최소 횟수가 Step 8 make_1(n)과 같은지 확인했는가 |
중 |
| 복수 경로 인지 | 최소 횟수가 같은 경로가 여럿일 수 있음을 알고 대표 하나를 고르는가 | 중 |
| 빅오 표기 | 시간 O(n)·공간 O(n)(표 전체 필요) | 중 |
풀이 예시
Step 8의 make_1(n)은 최소 연산 횟수만 돌려줬죠. 여기선 "어떤 순서로 줄였는지" 경로까지 복원합니다. 방법은 단순해요. 표를 채울 때 각 칸마다 "어디서 왔는지"를 함께 적어 두는 겁니다. dp[i]를 정할 때 고른 연산의 도착지(i-1·i//2·i//3 중 하나)를 came_from[i]에 기록해요. 표를 다 채운 뒤 n에서 시작해 came_from을 따라 1까지 거슬러 올라가면 경로가 나옵니다.
# algorithms/exercises_e4.py
def make_1_path(n):
dp = [0] * (n + 1) # dp[0], dp[1]=0에서 시작
came_from = [0] * (n + 1) # came_from[i] = i를 만든 연산의 도착지
for i in range(2, n + 1):
best = dp[i - 1] # 1을 빼는 경우
prev = i - 1
if i % 2 == 0 and dp[i // 2] < best: # 2로 나누는 게 더 짧으면 갈아탄다
best = dp[i // 2]
prev = i // 2
if i % 3 == 0 and dp[i // 3] < best: # 3으로 나누는 게 더 짧으면 갈아탄다
best = dp[i // 3]
prev = i // 3
dp[i] = best + 1 # 셋 중 가장 짧은 자리 + 이번 연산 1번
came_from[i] = prev # 그 자리로 어디서 왔는지 기록
path = []
cur = n
while cur != 1: # n에서 came_from을 따라 1까지 거슬러 올라간다
path.append(cur)
cur = came_from[cur]
path.append(1)
return dp[n], path
복원 부분에서 눈여겨볼 게 있어요. n에서 시작해 append하니 경로가 [n, ..., 1] 순서로 바로 나옵니다. 과제 힌트는 "되짚어 올라간 다음 뒤집으라"고 했지만, 뒤집는 방향은 시작점을 어디로 잡느냐에 달려 있어요. 1쪽에서 쌓아 올라오면 [1, ..., n]이 되어 뒤집어야 하지만, n쪽에서 내려오며 append하면 reverse()가 필요 없습니다. 어느 쪽이든 답은 같고, 뒤집기를 깜빡해 경로가 거꾸로 나오는 게 이 문제의 단골 실수예요.
make_1_path(10) — came_from을 따라 n에서 1까지 거슬러 온다
표를 채우며 기록: came_from[10]=9, came_from[9]=3, came_from[3]=1
복원: cur=10 → append 10 → cur=came_from[10]=9
cur=9 → append 9 → cur=came_from[9] =3
cur=3 → append 3 → cur=came_from[3] =1 (반복 종료)
append 1
결과: (dp[10]=3, [10, 9, 3, 1]) 10 −1→ 9 ÷3→ 3 ÷3→ 1
빅오는 시간 O(n)·공간 O(n)입니다. 2부터 n까지 각 칸에서 최대 세 갈래만 보니 시간은 O(n)이고, 복원도 경로 길이만큼만 거슬러 오니 O(n)에 묻혀요. 공간은 dp와 came_from 두 배열이 각각 n칸이라 O(n)입니다. 여기서 롤링으로 O(1)을 못 줄인다는 게 중요해요. dp[i//2]·dp[i//3]이 바로 앞이 아니라 멀리 떨어진 칸을 참조하거든요. 표 전체를 남겨 둬야 아무 칸이나 돌아볼 수 있습니다.
실행 예시로 확인하면 make_1_path(10)은 (3, [10, 9, 3, 1]), make_1_path(2)는 (1, [2, 1]), make_1_path(1)은 (0, [1])입니다. 한 가지 짚을 건, 최소 횟수가 같은 경로가 여럿일 수 있다는 점이에요. 예컨대 10은 세 번에 1로 가는 길이 하나가 아닐 수 있는데, 이 구현은 "나눗셈이 더 짧을 때만 갈아타는" 규칙이라 대표 경로 하나를 고릅니다. 최소 횟수 dp[n]은 언제나 make_1(n)과 일치하고, 경로는 그중 한 대표일 뿐이라는 걸 인지하고 있어야 해요.
💡 튜터의 한마디: 백준 1463 "1로 만들기"가 make_1 그대로고, 거기에 경로 복원 변형이 실전에서 자주 얹힙니다. 챙길 감각은 "DP는 값만 기록하는 게 아니라, 그 값이 어디서 왔는지도 함께 기록할 수 있다"입니다. 이 "값 + 출처" 역추적은 오늘 1로 만들기뿐 아니라, 다음 시간에 배울 최장 공통 부분 수열(LCS)의 문자열 복원, 그리고 앞으로 배울 최단 경로 복원(그래프에서 실제 지나간 노드를 되짚는, F-1의 다익스트라 계열)에서 두고두고 재사용돼요. 최적값을 구하는 DP를 짰다면 "출처 배열 하나만 더 두면 경로도 나온다"는 것, 기억해 두세요.
🤔 [생각해볼 주제 1] 메모이제이션과 타뷸레이션, 실전에선 무엇을 언제 꺼낼까
문제 상황 요약
오늘 같은 점화식을 top-down(메모이제이션)과 bottom-up(타뷸레이션) 두 방향으로 풀었습니다. 답도 같고 시간 복잡도도 O(n)으로 같았죠. 그런데 실전에선 선택이 갈립니다. 입력 크기, 재귀 깊이, 공간 제약, 그리고 "어느 쪽이 더 직관적인가"까지 엮어서, 둘 중 하나를 무엇으로 고를지 정리해 봅시다.
튜터의 가이드 및 해설
두 방식은 같은 점화식의 두 구현일 뿐이라, 답과 시간은 갈리지 않아요. 갈리는 축은 셋입니다 — 재귀 깊이, 공간, 직관.
Option A — 메모이제이션(top-down): 완전탐색 코드에 공책 한 겹(dict 또는 @functools.cache 한 줄)만 얹으면 됩니다. 장점은 원래 완전탐색에서 가장 적게 고친다는 것, 그리고 "큰 문제를 어떻게 쪼갤까"가 자연스러운 문제에서 직관적이라는 것이에요. 단점은 재귀라 파이썬 기본 깊이 한계(대략 1000)에 부딪힐 수 있다는 겁니다. sys.setrecursionlimit으로 한계를 올릴 수는 있지만, 너무 올리면 이번엔 실제 스택 메모리가 터져요. 공간도 memo에 재귀 스택까지 겹쳐 O(n) 밑으로 내려가기 어렵습니다.
Option B — 타뷸레이션(bottom-up): 가장 작은 문제부터 반복문으로 표를 채워 올라갑니다. 재귀가 없어 n이 아무리 커도 스택이 넘칠 걱정이 없고, 직전 값 몇 개만 필요하면 롤링으로 공간을 O(1)까지 줄여요. 단점은 점화식을 아래에서부터 다시 설계해야 하고, "작은 것부터 쌓는" 순서가 곧장 안 떠오르는 문제도 있다는 겁니다.
현업에서는 보통: 부분 문제가 얕으면(수백 깊이) 메모이제이션으로 갑니다. 완전탐색에 데코레이터 한 줄이 제일 빠른 길이니까요. 반면 입력이 커서 재귀가 깊어질 것 같거나(예: n이 10만인 계단), 공간을 O(1)로 짜내야 하면 타뷸레이션을 씁니다. 코테 실전 순서는 보통 이래요 — "일단 메모이제이션으로 맞히고, 재귀 깊이나 공간에서 터지면 타뷸레이션으로 전환한다." 이건 규칙이라기보다 시간을 아끼는 한 가지 방법입니다.
🎯 코테·면접에선 이렇게 나온다
"메모이제이션과 타뷸레이션의 차이는요?"가 단골입니다. "방향이 반대예요"까지는 절반이에요. "시간은 둘 다 O(n)으로 같고, 갈리는 건 공간과 재귀 스택입니다. 타뷸레이션은 스택이 없어 깊은 입력에 안전하고 롤링으로 공간을 O(1)까지 줄일 수 있어요. 대신 메모이제이션은 완전탐색 코드에 한 겹만 얹어 가장 적게 고친다는 장점이 있고요"까지 가면 트레이드오프를 아는 답입니다. "그럼 언제 뭘 쓰나요?"가 따라오면 "재귀 깊이가 걱정되면 타뷸레이션"으로 받으면 돼요.
💡 실무에선
이 판단은 캐싱 일반으로 이어집니다. 계산 결과를 저장해 재사용하는 발상은 DP만의 것이 아니에요. HTTP 응답 캐시, 프런트엔드의 메모이즈드 셀렉터, 서버의 계산 결과 캐시까지 곳곳에 있습니다. 공통 저울은 하나예요 — 저장 비용(메모리) vs 재계산 비용(시간). 그리고 "재귀 깊이 = 콜스택 한계"라는 감각은 실무에서 스택 오버플로를 디버깅할 때 그대로 쓰입니다. 깊은 재귀가 죽는 걸 반복문으로 바꿔 살리는 판단이 오늘 타뷸레이션과 정확히 같은 이야기죠.
🤔 [생각해볼 주제 2] 처음 보는 문제가 DP인지 어떻게 알아챌까
문제 상황 요약
DP가 통하는 조건은 겹치는 부분 문제와 최적 부분 구조 두 가지라고 배웠습니다. 그런데 시험장에서 문제를 처음 만나면 이 두 성질이 대놓고 적혀 있지 않죠. 여러 신호를 어떻게 조합해 "아, 이건 DP구나"를 감지할지, A-1의 입력 크기 잣대와 E-3의 그리디 반례 감각까지 엮어 판별 체크리스트를 만들어 봅시다.
튜터의 가이드 및 해설
판별은 한 신호가 아니라 여러 신호의 조합입니다. 하나씩 쌓아 볼게요.
첫째, 입력 크기(A-1 잣대). 문제에서 가장 먼저 볼 건 제약 조건이에요. n이 완전탐색엔 너무 크고(2ⁿ이 1억을 넘음) 그리디엔 반례가 있으면, 그 사이를 메우는 DP가 유력한 후보로 떠오릅니다. n이 수천에서 수십만인데 "최적"이나 "개수"를 물으면 DP 냄새가 강해요.
둘째, 키워드. "최소·최대·최장·경우의 수·몇 가지"는 DP 단골 표현입니다. 특히 "최적해"를 묻는데 눈앞의 최선을 집는 그리디에 반례가 보이면(E-3에서 기른 감각), 저울이 DP로 기울어요.
셋째, 완전탐색을 머릿속으로 그려 중복을 본다. 이게 가장 확실한 신호예요. 완전탐색 나무를 스케치했을 때 같은 부분 문제가 되풀이되면(피보나치의 fib(2), 거스름돈의 remaining=3), 그게 겹치는 부분 문제 확인입니다. 적어 두면 이득이라는 뜻이죠.
넷째, 최적 부분 구조 확인. "큰 답이 작은 답으로 조립되나"를 봅니다. 마지막 선택을 한 겹 벗겼을 때 같은 모양의 작은 문제가 남으면 예스예요. Step 6의 "마지막 한 걸음"이 이걸 확인하는 도구였죠.
여기서 두 접근이 갈립니다. Option A — 완전탐색부터 그려 중복을 눈으로 확인하는 건 확실하지만 시간이 걸려요. Option B — 키워드와 제약으로 유형을 빠르게 때려맞히는 건 빠르지만 헛다리를 짚을 수 있습니다. 현업(그리고 노련한 응시자)에서는 보통 둘을 순서로 씁니다 — 제약 조건으로 후보를 좁히고("O(n log n) 이하만 가능하네"), 키워드로 유형을 짐작한 뒤("최솟값을 묻네"), 완전탐색 스케치로 중복을 확인하고, 마지막 선택으로 점화식을 시도합니다. 앞의 빠른 필터로 후보를 줄이고 뒤의 확실한 검증으로 못을 박는 거예요.
🎯 코테·면접에선 이렇게 나온다
"이 문제가 DP인 걸 어떻게 알았나요?"가 나옵니다. "감으로요"는 최악의 답이에요. "제약이 n ≤ 10만이라 완전탐색은 불가하고, '최소 연산 수'를 묻는데 그리디로는 반례가 있었습니다. 완전탐색을 그려 보니 같은 부분 문제가 되풀이돼서 겹치는 부분 문제를 확인했고, 마지막 연산을 빼면 같은 모양의 작은 문제가 남아 점화식을 세울 수 있었습니다"처럼 신호를 조합해 말하면 됩니다. 접근을 설계하는 사람이라는 인상을 줘요.
💡 실무에선
문제 유형을 빠르게 분류하는 능력은 결국 경험의 압축입니다. 실무에서도 새 문제를 만나면 "이거 전에 본 그 패턴 아닌가"를 먼저 떠올려요. 캐시 무효화 문제인지, 분산 락 문제인지, 정합성 문제인지를 신호로 분류하고 나면 해법의 후보가 확 줄어듭니다. DP 판별 체크리스트를 만드는 훈련이 곧 "낯선 문제에서 익숙한 뼈대를 뽑는" 실무 근육을 키우는 일이에요.
🤔 [생각해볼 주제 3] @functools.cache를 실전에서 믿고 써도 될까
문제 상황 요약
오늘 dict를 손으로 짠 메모이제이션과 @functools.cache 한 줄을 나란히 봤습니다. 내장이 더 짧고 빠르고 버그도 없으니 늘 이걸 쓰면 될 것 같죠. 그런데 캐시가 함수에 눌러붙어 호출 사이에 값이 남는다는 성질(전역 상태처럼 동작)이 때로 발목을 잡습니다. 내장을 믿고 쓸 때와 직접 dict로 제어할 때를 무엇으로 가를지, 그리고 원리를 직접 짜 보는 값어치가 어디에 있는지 정리해 봅시다.
튜터의 가이드 및 해설
먼저 인정하고 갑시다. 코딩테스트에선 @functools.cache가 최선입니다. 프로세스가 한 번 돌고 끝나는 환경이라 캐시가 메모리를 계속 붙잡아도 문제될 일이 없어요. C로 구현돼 빠르고, 손으로 dict를 관리하다 실수할 여지도 없습니다. 시험장에서 이걸 마다하고 dict를 직접 짜는 건 손해예요.
문제는 장기 실행 서버입니다. @functools.cache의 캐시는 프로세스가 사는 동안 비워지지 않아요. 함수에 눌러붙어 전역 상태처럼 동작하죠.
Option A — @functools.cache / @lru_cache: 짧고 빠르고 버그 없음. 단점은 캐시 크기 제어예요. @cache는 상한이 없어서, 서로 다른 입력이 계속 들어오면 캐시가 무한히 커집니다. 메모리 누수처럼 쌓여요. 그래서 서버에선 @lru_cache(maxsize=...)로 상한을 두고 오래된 항목을 밀어내는 게 안전합니다.
Option B — 직접 dict로 제어: 코드는 길지만 캐시의 생명주기를 손에 쥡니다. 함수 스코프 안에서 만들면 호출이 끝날 때 사라지고, 크기 제한이나 무효화(특정 키만 지우기)를 세밀하게 짤 수 있어요. "이 입력 집합만 캐싱하고 다음 배치에선 비운다" 같은 제어가 필요할 때 이쪽이 답입니다.
현업에서는 보통 이렇게 가릅니다 — 코테나 단발 스크립트처럼 프로세스가 짧게 살면 @cache, 장기 실행 서버이거나 입력 도메인이 넓으면 @lru_cache(maxsize)나 직접 제어. 그리고 애초에 원리를 dict로 짜 본 값어치가 바로 여기서 나와요. "캐시가 언제 눌러붙어 문제가 되는지"를 아는 사람만 내장을 언제 믿고 언제 의심할지 가릅니다. 내장을 믿고 쓰는 것과 모르고 쓰는 건 평소엔 같아 보이지만, 메모리가 새기 시작할 때 갈려요.
🎯 코테·면접에선 이렇게 나온다
"@functools.cache 그냥 써도 되나요?"에 "네 빠르니까요"만 답하면 밋밋해요. "코딩테스트 환경에선 최선입니다. 프로세스가 짧게 살아 캐시 메모리를 걱정할 필요가 없거든요. 다만 장기 실행 서버라면 @cache는 상한이 없어 캐시가 무한히 커질 수 있어서, @lru_cache(maxsize)로 상한을 두거나 직접 제어합니다"까지 가면 환경에 따라 도구를 가려 쓴다는 인상을 줍니다.
💡 실무에선
캐시는 강력하지만 "언제 비우나"가 늘 어렵습니다. 캐시 무효화가 컴퓨터 과학의 어려운 문제로 농담처럼 회자되는 이유죠. 오래된 값을 붙잡고 있으면 틀린 답을 내고, 너무 자주 비우면 캐시의 이점이 사라집니다. 그래서 실무에서 캐시를 넣을 땐 늘 "이 값이 언제 낡는가, 그때 어떻게 비울 것인가"를 함께 설계해요. @functools.cache가 편한 건 이 고민을 안 해도 되는 환경(짧게 사는 프로세스)에 한해서고, 그 경계를 아는 게 원리를 직접 짜 본 사람의 힘입니다.