한 번 푼 건 적어둔다냥! 동적계획법
안녕, 나 코딩냥이다냥! 오늘은 이름부터 무섭다냥 — 동적계획법, 영어로 DP라냥. 그런데 사실 7장에서 이미 절반은 배웠다냥.
피보나치를 재귀로 짰더니 같은 걸 몇 번이고 다시 계산해서 느렸다냥. 그래서 한 번 계산한 걸 적어뒀다냥. 그게 DP의 전부라냥. 오늘은 그걸 제대로 세우는 법을 배운다냥.
오늘의 학습 목표
- DP가 통하는 두 가지 조건을 안다.
- 위에서 아래로(메모)와 아래에서 위로(표) 두 방식을 안다.
- 상태와 점화식을 세우는 법을 안다.
- 2차원 표가 필요한 경우를 안다.
- 같은 입력이라도 점화식이 다르면 다른 문제임을 안다.
1단계 · DP가 통하는 조건 (10분)
아무 문제나 DP로 풀리는 건 아니라냥. 두 가지가 맞아떨어져야 한다냥.
- 겹치는 부분 문제 — 같은 작은 문제를 여러 번 다시 풀게 된다
- 최적 부분 구조 — 작은 문제의 답으로 큰 문제의 답을 만든다
피보나치가 딱 이거였다냥. fib(5) 안에서 fib(2) 를 세 번이나 불렀다냥
(겹치는 부분 문제). 그리고 fib(n) 은 fib(n-1) 과 fib(n-2) 로
만들어진다냥 (최적 부분 구조).
비유로 이해하기 — 계단을 세는 냥이
계단을 한 번에 1칸이나 2칸씩 오를 수 있다냥. "5칸을 오르는 방법이 몇 가지냥?" 을 세려면, 4칸까지 오는 방법과 3칸까지 오는 방법을 알면 된다냥. 마지막에 1칸 뛰거나 2칸 뛰거나니까라냥.
그러니 5칸의 답 = 4칸의 답 + 3칸의 답이라냥. 작은 답으로 큰 답을 만든다냥.
11장의 완전탐색과 뭐가 다르냥?
완전탐색은 5칸 오르는 모든 경로를 하나하나 다 그려봤다냥. DP는 "4칸까지 몇 가지"라는 답만 기억한다냥. 경로가 몇 개든 상관없이 숫자 하나로 압축하는 거라냥.
그래서 완전탐색이 터지는 크기도 DP는 눈 깜짝할 새에 푼다냥.
2단계 · 두 가지 방식 (12분)
DP를 짜는 길은 두 갈래라냥. 답은 똑같이 나오니 편한 쪽을 고르면 된다냥.
큰 문제에서 시작해서 재귀로 쪼개 내려가되, 한 번 구한 답을 적어두는 방식이라냥. 7장에서 배운 그거라냥.
from functools import lru_cache
@lru_cache(None)
def ways(i):
if i == 0:
return 1
total = ways(i - 1)
if i >= 2:
total += ways(i - 2)
if i >= 3:
total += ways(i - 3)
return total장점 — 점화식을 그대로 함수로 옮기면 되니 떠올리기 쉽다냥.
가장 작은 답부터 표를 순서대로 채워 올라가는 방식이라냥.
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1]
if i >= 2:
dp[i] += dp[i - 2]
if i >= 3:
dp[i] += dp[i - 3]장점 — 재귀가 없어서 깊이 걱정이 없다냥. 큰 입력에서 안전하다냥.
둘 중 뭘 쓰냥? 입문 단계에서는 아래에서 위로(표) 를 기본으로 하자냥.
10장에서 봤듯 재귀는 깊이가 깊어지면 RecursionError 로 터진다냥. 표
방식은 그냥 반복문이라 그 걱정이 없다냥. 오늘 문제도 전부 표로 풀 수 있다냥.
3단계 · 상태와 점화식 (13분)
DP의 진짜 어려움은 코드가 아니라냥. "무엇을 표에 적을 거냥?" 을 정하는 거라냥. 이걸 상태라고 한다냥.
- 상태 —
dp[i]가 무슨 뜻인지 한 문장으로 정한다 - 점화식 —
dp[i]를 더 작은 dp 값으로 어떻게 만드는지 적는다
계단 문제라면 —
- 상태:
dp[i]=i칸까지 오는 방법의 수 - 점화식:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
상태를 말로 정확히 못 하면 점화식도 안 나온다냥.
dp[i] 가 "i까지의 뭔가" 처럼 흐릿하면 안 된다냥. "i칸까지 오는
방법의 수" 처럼 딱 떨어져야 한다냥.
그리고 시작값을 조심하자냥. dp[0] 을 잘못 잡으면 전부 어긋난다냥.
계단에서 dp[0] = 1 인 건 "아무 칸도 안 오른 방법이 한 가지(가만히 있기)"
라는 뜻이라냥.
점화식에 + 만 있는 건 아니라냥. 가장 작은 값을 구하는 문제도 많다냥.
"n 을 1로 만드는 최소 연산" 이라면 —
- 상태:
dp[i]=i를 1로 만드는 최소 연산 횟수 - 점화식:
dp[i] = min(dp[i-1], dp[i//2], dp[i//3]) + 1
이때는 min 을 쓴다냥. 오늘 2번 문제가 이거라냥.
왜 이런 건 그리디로 안 되냥?
"1로 만들기"에서 "나눌 수 있으면 무조건 나눈다"는 그리디는 틀린다냥.
10 을 보자냥.
- 그리디:
10→5(÷2) →4(-1) →2(÷2) →1(÷2) = 4번 - 최적:
10→9(-1) →3(÷3) →1(÷3) = 3번
당장 나누는 게 손해일 때가 있다냥. 12장에서 배운 그거라냥 — 눈앞만 보면 틀린다냥. DP 는 모든 경우를 표에 담아서 이런 함정을 피한다냥.
4단계 · 2차원 표가 필요할 때 (13분)
상태가 하나로 안 되는 문제도 있다냥. 배낭 문제가 고전이라냥.
물건이 여럿 있고 각각 무게와 가치가 있다냥. 배낭이 버티는 무게 안에서 가치 합을 최대로 담고 싶다냥. 각 물건은 한 번만 담을 수 있다냥.
11장에서 본 그 재귀라냥
11장 부분집합에서 각 물건마다 고른다 / 안 고른다 두 갈래로 뻗었다냥. 배낭도 똑같다냥 — 각 물건을 담거나 말거나라냥.
다른 점은 남은 무게를 같이 기억해야 한다는 거라냥. 그래서 상태가 두 개가 된다냥.
- 상태:
dp[i][w]= 앞에서i개까지 봤고 무게w를 쓸 수 있을 때 최대 가치 - 점화식: 담으면
dp[i-1][w - 무게] + 가치, 안 담으면dp[i-1][w], 둘 중 큰 값
사실 배낭은 한 줄짜리 표로도 된다냥. dp[w] 하나만 두고, 물건마다
무게를 큰 쪽에서 작은 쪽으로 훑으며 갱신하는 거라냥.
dp = [0] * (cap + 1)
for w, v in items:
# 큰 무게부터 거꾸로 훑는다냥
for c in range(cap, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)왜 큰 무게부터냥? 작은 쪽부터 하면 방금 담은 물건을 같은 칸에서 또 담아버린다냥. 각 물건은 한 번만 담아야 하니 거꾸로 도는 거라냥.
처음에는 2차원으로 또박또박 짜고, 익으면 이렇게 줄이자냥.
배낭도 그리디로는 안 된다냥.
"비율(가치÷무게)이 높은 것부터" 담는 그리디는 그럴듯하지만 틀린다냥. 비율 높은 작은 물건을 먼저 담으면, 자리를 조금 남겨서 더 좋은 조합을 놓친다냥. 오늘 3번 문제의 숨겨진 테스트가 정확히 그걸 잡는다냥.
5단계 · 같은 입력, 다른 점화식 (12분)
마지막이라냥. 입력이 똑같은데 점화식만 바꾸면 완전히 다른 답이 나온다냥. DP의 유연함을 보여주는 대목이라냥.
동전 종류가 주어지고 금액 k 를 만든다냥. 두 가지를 물을 수 있다냥.
- 최소 개수 —
dp[a] = min(dp[a], dp[a - 동전] + 1) - 방법의 수 —
dp[a] = dp[a] + dp[a - 동전]
상태(dp[a] = 금액 a 를 만드는 답)는 똑같다냥. 채우는 식만 min 이냐
+ 냐로 갈린다냥. 오늘 4번과 5번 문제라냥.
12장 그리디와 이어지는 대목이라냥.
12장에서 동전 거스름돈은 "큰 동전은 작은 동전의 배수" 일 때만 그리디로 됐다냥. 그 조건이 없으면 그리디가 틀렸다냥 (1, 3, 4 로 6 만들기).
DP 는 그 조건이 없어도 된다냥. 모든 금액을 표에 담으니 배수든 아니든 항상 최소 개수를 찾는다냥. 오늘 4번 문제에 배수가 아닌 동전이 나온다냥.
방법의 수를 셀 때는 반복문 순서가 중요하다냥.
for c in coins: # 동전이 바깥이라냥
for a in range(c, k + 1):
dp[a] += dp[a - c]동전을 바깥에 두면 각 동전을 한 번씩만 고려해서 조합을 센다냥
(1 + 2 와 2 + 1 이 같은 것).
두 반복문을 뒤집으면 순서를 세서 답이 커진다냥. 1, 2 로 3 을
만드는 방법이 조합으로는 2가지인데, 뒤집으면 3가지가 나온다냥. 오늘 5번
문제의 첫 예시가 정확히 그걸 확인해준다냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번은 계단, 2번은 min 점화식, 3번은 2차원 배낭, 4번과 5번은 입력이 똑같은데 점화식이 다른 동전 짝이라냥.
풀기 전에 항상 이 두 개를 먼저 적어보자냥 — dp[i] 가 무슨 뜻이냥? 그리고 더 작은 dp 로 어떻게 만드냥? 가보자냥~