13강 / 20강

동적 계획법 — 한 번 계산한 건 다시 계산하지 않는다

메모이제이션 = 알고리즘 안의 캐시

12강에서 완전 탐색이 2ⁿ으로 폭발하는 걸 봤습니다. 그런데 그 폭발의 상당 부분은 같은 계산을 반복하는 데서 옵니다.

계산한 결과를 적어 두었다가 다시 쓰면 어떨까요? 이 단순한 아이디어가 동적 계획법(Dynamic Programming, DP)입니다.

이름은 무섭지만, 핵심은 이 한 문장이에요.

이미 푼 문제는 다시 풀지 않는다.

고등학생한 번 계산한 건 다시 계산하지 않는다

동적 계획법(DP) 은 이름이 무섭지만 발상은 한 줄입니다.

이미 계산한 답을 적어 두고 다시 쓴다

왜 필요한가

완전 탐색이 2ⁿ 으로 폭발한다고 했죠(12강). 그런데 자세히 보면 —

같은 계산을 몇 번씩 되풀이하고 있다

피보나치로 보면

F(5) 를 구하려면 F(4) 와 F(3) 이 필요합니다. F(4) 를 구하려면 F(3) 과 F(2) 가 필요하고요.

값	몇 번 계산되나 (F(30) 구할 때)
F(29)	1번
F(20)	수천 번
F(5)	수십만 번

같은 답을 수십만 번 다시 구한다

적어 두면

	계산 횟수
그냥	약 130만 번
적어 두면	30번

4만 배 — 아이디어 하나로

비유 — 시험 공부

같은 문제를 풀 때마다 처음부터 생각하는 것과 풀이를 노트에 적어 두고 다시 보는 것.

두 번째가 훨씬 빠르죠. 메모가 핵심입니다. 그래서 이름이 메모이제이션이에요.

n=30에 이미 130만 번. n=50이면 200억 번입니다.

Python 브라우저에서 실행

import time

# ❌ 같은 계산을 계속 반복하는 피보나치
호출수 = 0
def 느린피보(n):
    global 호출수
    호출수 += 1
    if n <= 1:
        return n
    return 느린피보(n - 1) + 느린피보(n - 2)

for n in (10, 20, 25, 30):
    호출수 = 0
    t0 = time.time()
    결과 = 느린피보(n)
    t = time.time() - t0
    print(f"n={n:>2}  값 {결과:>7,}  함수 호출 {호출수:>10,}번  {t*1000:>7.1f} ms")

print()
print("n이 5씩 늘 때마다 호출 횟수가 약 10배씩 폭발합니다. n=50이면? 💀")

왜 이렇게 폭발할까요

피보(5)를 계산하려면 피보(4)와 피보(3)이 필요합니다. 그런데 피보(4)도 피보(3)을 필요로 해요. 같은 값을 몇 번이고 다시 계산합니다.

계산한 걸 메모해 두면 두 번째부터는 그냥 꺼내 쓰면 됩니다. 이것을 메모이제이션(memoization)이라고 해요.

딕셔너리 한 줄이 O(2ⁿ)를 O(n)으로 만듭니다.

Python 브라우저에서 실행

import time

메모 = {}
호출수 = 0

def 빠른피보(n):
    global 호출수
    호출수 += 1
    if n in 메모:              # ✅ 이미 계산했다 — 꺼내 쓴다
        return 메모[n]
    if n <= 1:
        결과 = n
    else:
        결과 = 빠른피보(n - 1) + 빠른피보(n - 2)
    메모[n] = 결과             # 계산한 것은 반드시 적어 둔다
    return 결과

for n in (30, 50, 100, 300):
    메모.clear(); 호출수 = 0
    t0 = time.time()
    결과 = 빠른피보(n)
    t = time.time() - t0
    print(f"n={n:>3}  함수 호출 {호출수:>4}번  {t*1000:>6.3f} ms")
    print(f"      값 = {결과:,}")

print()
print("n=300 도 601번 호출이면 끝. 메모 없이는 우주가 끝나도 못 끝냅니다.")

고등학생파이썬은 한 줄로 해 줍니다

note 가 알려 줍니다 — 직접 적어 둘 필요가 없어요.

@lru_cache 한 줄이면 끝

데코레이터라는 것

함수 위에 한 줄을 붙이면 그 함수의 동작이 바뀝니다.

붙이기 전	붙인 후
부를 때마다 계산	같은 인자면 저장된 답

함수를 안 고치고 동작만 바꾼다

비유 — 창구에 메모지 붙이기

창구 직원에게 "같은 질문이 오면 적어 둔 답을 주세요" 라고 메모를 붙이는 겁니다.

직원이 하는 일은 그대로인데 훨씬 빨라져요.

그런데 조건이 있습니다

조건	왜
같은 입력 → 같은 출력	답이 바뀌면 저장한 게 틀린다
인자가 해시 가능	딕셔너리 열쇠가 되어야 (8강)

시간에 따라 답이 바뀌는 함수에는 쓰면 안 된다

예를 들어 "지금 재고" 를 돌려주는 함수는 캐시하면 안 되죠 — 재고가 계속 바뀌니까요.

이게 16강의 캐시와 같은 이야기입니다

캐시가 만드는 사고 중 하나가 낡은 값이에요. DP 도 같은 위험을 안고 있습니다.

🎮 메모이제이션 실험실

메모를 켜고 끄면서 호출 횟수를 비교해 보세요. 호출 트리가 그려지는데, 메모를 켜면 가지가 잘려 나가는 모습이 보입니다. n을 조금씩 올려 보면 폭발이 얼마나 무서운지 실감할 수 있어요.

쇼핑몰에서의 DP — 배송비 최소화

실전 문제입니다. 창고가 여러 곳에 있고, 주문을 어느 창고에서 보낼지에 따라 배송비가 달라집니다. 게다가 합배송 할인도 있어요.

모든 조합을 다 해 보면 지수 시간이지만, "i번째 상품까지 처리했을 때의 최소 비용"을 저장해 두면 선형에 가까워집니다.

표 하나를 채워 나가는 것 — 이것이 DP의 전형적인 모습입니다.

Python 브라우저에서 실행

# 계단 오르기 = 배송 묶음 나누기의 축소판
# 상품 n개를 순서대로 상자에 담는데, 한 상자에 1개 또는 2개만 담을 수 있다.
# 상자를 하나 쓸 때마다 포장비가 든다. 최소 비용은?

상품비용 = [0, 3000, 2000, 4000, 1000, 5000, 2000, 3000]   # 1번부터
n = len(상품비용) - 1

# dp[i] = i번 상품까지 처리했을 때의 최소 비용
dp = [0] * (n + 1)
dp[1] = 상품비용[1]

for i in range(2, n + 1):
    혼자담기 = dp[i - 1] + 상품비용[i]              # i를 새 상자에
    같이담기 = dp[i - 2] + max(상품비용[i - 1], 상품비용[i])   # i-1과 i를 한 상자에 (큰 값만 청구)
    dp[i] = min(혼자담기, 같이담기)

print("상품별 비용:", 상품비용[1:])
print("dp 표      :", dp[1:])
print()
print(f"✅ 최소 포장 비용: {dp[n]:,}원")
print(f"   (전부 따로 담으면 {sum(상품비용):,}원)")

고등학생DP 를 쓸 수 있는 두 가지 조건

note 가 조건 둘을 듭니다. 말이 어려우니 일상어로 풀어 봅시다.

조건	어려운 말	쉬운 말
①	최적 부분구조	작은 문제의 최선을 모으면 큰 문제의 최선
②	중복 부분문제	같은 작은 문제가 여러 번 나온다

①이 없으면 답이 틀리고, ②가 없으면 빨라지지 않는다

①을 예로 보면

서울에서 부산 가는 가장 짧은 길을 찾습니다. 그 길이 대전을 지난다면?

서울→대전 구간도 가장 짧은 길이어야 한다

안 그러면 그 구간만 바꿔서 더 짧게 만들 수 있으니까요. 그러니 최선이 아니었던 거죠.

그런데 ①이 안 되는 문제도 있습니다

"가장 긴 단순 경로" 같은 건 안 됩니다. 부분이 최선이라고 전체가 최선이 아니에요.

조건을 확인 안 하고 쓰면 답이 틀린다

②를 예로 보면

중복이 없으면 저장해 봐야 다시 안 씁니다. 메모리만 쓰고 이득이 없죠.

중복이	DP 효과
많다 (피보나치)	극적
없다	없다 — 오히려 손해

모든 최적화는 조건이 맞을 때만 이득이다

탐욕 vs DP vs 완전 탐색 — 정리

	속도	정확도	언제 쓰나
탐욕	가장 빠름 `O(n log n)`	보장 안 됨	구조가 받쳐 줄 때 · 빠른 근사가 필요할 때
DP	보통 `O(n×m)`	✅ 최적 보장	부분 문제가 겹칠 때
완전 탐색	가장 느림 `O(2ⁿ)`	✅ 최적 보장	n이 아주 작을 때 · 정답 검증용

실무 순서는 이렇습니다. ① 완전 탐색으로 정답을 구해 두고 → ② 빠른 알고리즘을 만든 뒤 → ③ 둘의 답을 비교해 검증. 12강 위젯에서 한 것이 바로 이 검증이었어요.

고등학생DP 는 알고리즘 안의 캐시입니다

부제가 "메모이제이션 = 알고리즘 안의 캐시" 라고 하죠. 16강과 같은 발상입니다.

비싼 계산의 결과를 적어 두고 다시 쓴다

이 발상이 여기저기 나옵니다

어디	무엇을 저장	강
DP	함수 계산 결과	13강
캐시	DB 조회 결과	16강
인덱스	정렬된 목록	5강
조회표	이름 → 정보	8강

전부 "미리 해 두고 다시 쓴다" 다

그리고 대가도 같습니다

얻는 것	내주는 것
시간	공간 (메모리)
	값이 낡을 위험

시간과 공간의 거래 — 알고리즘의 가장 흔한 맞바꿈

비유 — 냉장고

매번 장을 보는 대신 냉장고에 쟁여 둡니다.

시간을 아낀다 ✔
공간을 쓴다 (냉장고 자리)
상할 수 있다 (낡은 값)

세 가지가 정확히 같은 구조다

16강에서 캐시가 만드는 사고 셋을 배웁니다. 그중 하나가 낡은 값이에요 — 냉장고에서 상한 음식이죠.

🤔 확인 문제

메모이제이션(memoization)의 핵심 아이디어는?

🤔 확인 문제

메모 없는 재귀 피보나치의 시간 복잡도는?

🤔 확인 문제

DP를 적용할 수 있으려면 문제가 가져야 할 성질은?