Chapter 14 - 동적 계획법 (Dynamic Programming)

Chapter 14

동적 계획법

Dynamic Programming

Part 1  동적 계획법의 개념과 등장 배경 · Concept & Background
Part 2  동적 계획법의 이해와 구현 · Understanding & Implementation
Part 3  동적 계획법의 응용 · Applications

01

Part 1

동적 계획법의 개념과 등장 배경

Concept & Background of Dynamic Programming

동적 계획법이 왜 필요한지, 어떤 문제를 해결하기 위해 등장했는지 알아봅니다.

생활 속의 동적 계획법

Dynamic Programming in Daily Life

한국어

동적 계획법이란?

나폴레옹의 전쟁 전략

나폴레옹은 자신보다 큰 군대를 상대할 때, 적을 작게 분할해서 각각 공격하는 방식으로 승리했습니다. 동적 계획법도 마찬가지로 큰 문제를 작은 문제로 쪼개서 해결합니다!

쉬운 비유: 시험 공부

시험 범위가 300페이지라면, 한 번에 외우려 하면 힘듭니다. 하지만 10페이지씩 나눠서 공부하고, 앞에서 공부한 내용을 메모해두면 훨씬 효율적입니다. 동적 계획법은 바로 이런 방식입니다!

        동적 계획법(Dynamic Programming, DP): 큰 문제를 작은 하위 문제로 나누고, 한 번 계산한 결과를 저장(메모)해두어 같은 계산을 반복하지 않는 알고리즘
      

핵심 아이디어 2가지

1

분할: 큰 문제를 작은 문제로 나눈다

2

메모이제이션: 한 번 풀은 작은 문제의 답을 저장해두고, 나중에 같은 문제를 만나면 다시 풀지 않고 저장된 답을 꺼내 쓴다

왜 "동적"이라고 부를까? "Dynamic"이라는 이름은 문제를 단계적으로(시간에 따라) 풀어간다는 의미입니다. 프로그래밍의 "동적 메모리"와는 다른 뜻입니다.

English

What is Dynamic Programming?

Napoleon's War Strategy

Napoleon defeated larger armies by dividing them into smaller groups and attacking each one. Dynamic Programming works the same way — break a big problem into smaller ones!

Easy Analogy: Studying for an Exam

If the exam covers 300 pages, memorizing all at once is hard. But studying 10 pages at a time and keeping notes of what you've learned is much more efficient. That's exactly how DP works!

        Dynamic Programming (DP): Divide a big problem into smaller subproblems, store the results of solved subproblems, and reuse them to avoid redundant computation.
      

Two Core Ideas

1

Divide: Break a big problem into smaller subproblems

2

Memoization: Store the answer to each subproblem so you never solve it twice — just look up the stored answer

Why "Dynamic"? The word "Dynamic" here means solving problems step by step over stages — it has nothing to do with "dynamic memory" in programming.

배낭 문제란?

The Knapsack Problem

한국어

동적 계획법의 대표 문제: 배낭 문제

보물섬 모험!

당신은 보물섬에 도착했습니다! 보석이 가득하지만, 배낭에는 최대 7kg까지만 담을 수 있습니다. 어떤 보석을 담아야 가장 비싼 조합이 될까요?

보물섬의 보석 목록

보석	무게(kg)	가격(억 원)
금괴	6	13
수정	4	8
루비	3	6
진주	5	12

배낭 최대 무게: 7kg

문제: 배낭에 넣을 수 있는 보석의 조합 중에서 가격 합계가 가장 큰 조합을 찾아라!

주의: 보석은 쪼갤 수 없습니다! 통째로 넣거나 안 넣거나 둘 중 하나입니다 (0/1 배낭 문제).

English

The Classic DP Problem: Knapsack

Treasure Island Adventure!

You've arrived at Treasure Island! There are lots of gems, but your bag can hold at most 7kg. Which gems should you take to get the most expensive combination?

Gem List on Treasure Island

Gem	Weight(kg)	Value(billion)
Gold Bar	6	13
Crystal	4	8
Ruby	3	6
Pearl	5	12

Max bag weight: 7kg

Problem: Among all possible gem combinations that fit in the bag, find the one with the highest total value!

Note: You cannot split a gem! Each gem is either fully included or excluded (0/1 Knapsack Problem).

해결 방법 1: 브루트 포스

Approach 1: Brute Force

한국어

모든 경우의 수를 다 해보자!

자물쇠 비밀번호 찾기

4자리 자물쇠 비밀번호를 모르면? 0000부터 9999까지 하나씩 다 시도해보면 반드시 열립니다. 이것이 브루트 포스(무차별 대입)입니다!

브루트 포스(Brute Force)란?

모든 가능한 조합을 전부 나열한 후, 그 중에서 최선의 답을 찾는 방법입니다. 확실하지만 매우 느립니다!

보석 4개의 모든 조합

각 보석을 "넣는다/안 넣는다" 2가지 선택이 있으므로:

경우의 수 = 2⁴ = 16가지

조합	금괴	수정	루비	진주	무게	가격	가능?
1	X	X	X	X	0	0	O
2	X	X	X	O	5	12	O
3	X	X	O	X	3	6	O
4	X	X	O	O	8	-	X(초과)
5	X	O	X	X	4	8	O
6	X	O	X	O	9	-	X(초과)
7	X	O	O	X	7	14	O
...	나머지 조합도 계산...

결과: 수정(4kg, 8억) + 루비(3kg, 6억) = 7kg, 14억이 최적의 답!

English

Try All Possible Combinations!

Finding a Lock Combination

Don't know the 4-digit code? Try every number from 0000 to 9999 — you'll eventually open it. That's brute force!

What is Brute Force?

List ALL possible combinations, then pick the best answer. It guarantees the right answer but is very slow!

All Combinations of 4 Gems

Each gem has 2 choices: "include" or "exclude":

Number of cases = 2⁴ = 16 combinations

The Problem with Brute Force

4 items → 16 cases
10 items → 1,024 cases
20 items → 1,048,576 cases
40 items → 1,099,511,627,776 cases!

As the number of items grows, the combinations explode exponentially. Time complexity is O(2ⁿ).

Result: Crystal(4kg, 8B) + Ruby(3kg, 6B) = 7kg, 14 billion is the optimal answer!

해결 방법 2: 탐욕 알고리즘

Approach 2: Greedy Algorithm

한국어

가장 비싼 것부터 넣자!

뷔페에서 먹기

뷔페에 갔을 때, 가장 비싼 음식부터 먹는 전략! 눈앞의 최고를 바로 선택하는 방법이 탐욕 알고리즘입니다.

탐욕 알고리즘(Greedy Algorithm)이란?

매 순간 가장 좋아 보이는 것을 선택하는 방법입니다. 빠르지만, 항상 최적의 답을 보장하지는 않습니다!

배낭 문제에 적용

1

가격 순으로 정렬: 금괴(13억) > 진주(12억) > 수정(8억) > 루비(6억)

2

금괴(6kg) 넣기 → 남은 무게: 7-6 = 1kg

3

진주(5kg) → 안 됨! 수정(4kg) → 안 됨! 루비(3kg) → 안 됨!

탐욕 결과: 금괴만 담음 → 13억
하지만 최적의 답은 수정+루비 = 14억!
탐욕 알고리즘이 실패했습니다!

English

Pick the Most Expensive First!

Buffet Strategy

At a buffet, eat the most expensive dishes first! Always picking the best-looking option right now is the Greedy approach.

What is Greedy Algorithm?

At each step, choose what looks best at the moment. It's fast but doesn't always guarantee the optimal answer!

Applied to Knapsack

1

Sort by value: Gold(13B) > Pearl(12B) > Crystal(8B) > Ruby(6B)

2

Put Gold(6kg) → remaining capacity: 7-6 = 1kg

3

Pearl(5kg) → too heavy! Crystal(4kg) → too heavy! Ruby(3kg) → too heavy!

Greedy result: Only Gold = 13 billion
But optimal is Crystal + Ruby = 14 billion!
Greedy algorithm failed!

        Lesson: Greedy is fast (no need to check all combinations), but it can miss the best answer because it never reconsiders earlier choices. We need a smarter approach!
      

세 가지 방법 비교

Comparing Three Approaches

한국어

어떤 방법이 가장 좋을까?

브루트 포스

모든 경우의 수를 시도
정확하지만 매우 느림
O(2ⁿ)

탐욕 알고리즘

눈앞의 최선만 선택
빠르지만 틀릴 수 있음
O(n log n)

동적 계획법

체계적 + 메모이제이션
정확하고 빠름!
O(n × W)

비교 항목	브루트 포스	탐욕 알고리즘	동적 계획법
정확성	항상 정확	가끔 틀림	항상 정확
속도	매우 느림	빠름	빠름
시간복잡도	O(2ⁿ)	O(n log n)	O(n × W)
보석 4개	16회	4회	28회
보석 40개	1조 회!	40회	280회

결론: 동적 계획법은 브루트 포스처럼 정확하면서, 탐욕 알고리즘처럼 빠릅니다! 두 방법의 장점만 모았습니다.

n: 물건의 수, W: 배낭의 최대 무게

English

Which Approach is Best?

Brute Force

Try every combination
Accurate but very slow
O(2ⁿ)

Greedy

Pick local optimum
Fast but sometimes wrong
O(n log n)

Dynamic Prog.

Systematic + Memoization
Accurate AND fast!
O(n × W)

Criteria	Brute Force	Greedy	DP
Accuracy	Always correct	Sometimes wrong	Always correct
Speed	Very slow	Fast	Fast
Complexity	O(2ⁿ)	O(n log n)	O(n × W)
4 items	16 ops	4 ops	28 ops
40 items	1 trillion!	40 ops	280 ops

Conclusion: DP is accurate like Brute Force and fast like Greedy! It combines the best of both worlds.

n: number of items, W: max bag weight

왜 동적 계획법이 필요한가?

Why Do We Need DP?

한국어

보석이 40개라면?

더 큰 보물섬!

보물섬에서 보석을 36개 더 발견했습니다! 이제 총 40개의 보석 중에서 골라야 합니다.

브루트 포스로 풀 수 있을까?

        240 = 1,099,511,627,776 (약 1조)

        컴퓨터가 1초에 1억 번 계산해도 약 3시간 걸립니다!

탐욕 알고리즘으로 풀 수 있을까?

빠르긴 하지만, 앞에서 봤듯이 최적의 답을 보장하지 않습니다.

동적 계획법이면?

40 × 7 = 280번의 계산만 하면 됩니다!
1조 번 vs 280번 — 엄청난 차이!

English

What if There Are 40 Gems?

A Bigger Treasure Island!

You found 36 more gems on the island! Now you need to choose from a total of 40 gems.

Can Brute Force Handle It?

        240 = 1,099,511,627,776 (~1 trillion)

        Even at 100 million calculations per second, it takes ~3 hours!

Can Greedy Handle It?

It's fast, but as we saw, it doesn't guarantee the optimal answer.

What About DP?

Only 40 × 7 = 280 calculations!
1 trillion vs 280 — an enormous difference!

Key Insight

DP avoids redundant work by remembering what it already calculated. Instead of checking every combination, it builds the answer step by step, reusing previous results.

        This is why we need DP:

        When brute force is too slow and greedy is too inaccurate, Dynamic Programming gives us both speed and correctness.

동적 계획법의 핵심 원리

Core Principles of DP

한국어

DP가 작동하는 두 가지 조건

조건 1: 최적 부분 구조 (Optimal Substructure)

큰 문제의 최적의 답이 작은 문제들의 최적의 답으로 구성된다.

서울→부산 최단 경로

서울→부산 최단 경로가 서울→대전→부산이라면, 서울→대전 구간도 최단 경로여야 합니다. 전체 최적이 부분 최적을 포함합니다!

조건 2: 중복되는 하위 문제 (Overlapping Subproblems)

같은 작은 문제가 여러 번 반복해서 나타난다.

수학 시험 준비

미적분 문제를 풀다 보면 "덧셈, 곱셈"을 계속 반복합니다. 매번 덧셈을 처음부터 배우지 않고 이미 아는 것을 활용하죠. 이것이 메모이제이션!

메모이제이션(Memoization)

        한 번 계산한 결과를 표(배열)에 저장해두고, 같은 계산이 필요하면 다시 계산하지 않고 저장된 값을 바로 사용하는 기법
      

English

Two Conditions for DP to Work

Condition 1: Optimal Substructure

The optimal solution to the big problem is made up of optimal solutions to smaller subproblems.

Seoul → Busan Shortest Path

If the shortest Seoul→Busan route goes through Daejeon, then the Seoul→Daejeon segment must also be the shortest. The whole optimal solution contains optimal sub-solutions!

Condition 2: Overlapping Subproblems

The same small problem appears repeatedly during computation.

Studying for a Math Exam

When solving calculus problems, you keep repeating addition and multiplication. You don't re-learn addition each time — you reuse what you already know. That's memoization!

Memoization

        Store computed results in a table (array), and when the same calculation is needed again, look it up instead of recalculating.
      

Memo = Memory + Optimization
Think of it as writing answers on a cheat sheet so you never solve the same problem twice!

동적 계획법 처리 흐름

DP Processing Flow

한국어

DP 문제 풀이 순서

1

문제 분석: 큰 문제를 어떤 작은 문제로 나눌 수 있는지 파악

2

점화식 세우기: 작은 문제의 답으로 큰 문제의 답을 구하는 공식(규칙) 발견

3

메모 테이블 만들기: 결과를 저장할 2차원 배열(표) 준비

4

초기값 채우기: 가장 작은 문제(기본 경우)의 답을 먼저 입력

5

테이블 채우기: 점화식을 이용해 작은 문제부터 큰 문제까지 순서대로 답 계산

6

결과 추출: 테이블의 마지막 칸이 전체 문제의 최적 답!

        배낭 문제의 점화식:

        물건 무게 > 배낭 용량 → 이전 행 값 그대로

        물건 무게 ≤ 배낭 용량 → max(물건 가격 + 여유분 가격, 이전 행 값)

English

DP Problem-Solving Steps

1

Analyze: Identify how to break the big problem into smaller subproblems

2

Find recurrence: Discover the formula that relates big problems to small problems

3

Create memo table: Prepare a 2D array to store results

4

Fill base cases: Enter answers for the smallest subproblems first

5

Fill the table: Use the recurrence to compute from small to big, in order

6

Extract result: The last cell in the table is the optimal answer!

        Knapsack Recurrence:

        If item weight > capacity → copy value from row above

        If item weight ≤ capacity → max(item value + leftover value, value from row above)

Bottom-Up Approach: DP fills the table from smallest subproblems to largest — this is called "bottom-up" or "tabulation," and it avoids the overhead of recursive calls.

Part 1 연습문제

Part 1 Practice Problems

한국어

개념 확인 문제

문제 1: 브루트 포스 경우의 수

보석이 5개일 때 브루트 포스로 확인해야 하는 경우의 수는?

# 각 보석마다 넣기/안넣기 2가지
25 = 32가지

보석이 n개이면 경우의 수는 2ⁿ이므로, 2⁵ = 32가지입니다.

문제 2: 탐욕 알고리즘의 한계

배낭 최대 무게가 10kg일 때, 다음 물건으로 탐욕 알고리즘을 적용하면?
물건A: 7kg, 10만원 / 물건B: 5kg, 6만원 / 물건C: 5kg, 6만원

탐욕: 가장 비싼 A(10만원) 먼저 선택 → 남은 3kg → B,C 불가 → 10만원

최적: B(6만원) + C(6만원) = 10kg → 12만원!

탐욕 알고리즘이 최적이 아닌 답을 줍니다.

문제 3: 메모이제이션이란?

메모이제이션의 핵심 아이디어를 한 줄로 설명하세요.

한 번 계산한 결과를 저장해두고, 같은 계산이 필요하면 다시 풀지 않고 저장된 답을 재사용하는 기법입니다.

English

Concept Check

Q1: Brute Force Combinations

How many combinations must brute force check with 5 gems?

Each gem: include or exclude → 2 choices

2⁵ = 32 combinations

Q2: Greedy Limitation

Bag capacity 10kg. Item A: 7kg/$10, B: 5kg/$6, C: 5kg/$6. What does Greedy pick?

Greedy: Picks A ($10) first → 3kg left → can't fit B or C → $10

Optimal: B + C = 10kg → $12!

Greedy gives a suboptimal answer.

Q3: What is Memoization?

Explain memoization in one sentence.

Store computed results and reuse them when the same calculation is needed again, avoiding redundant work.

02

Part 2

동적 계획법의 이해와 구현

Understanding & Implementation

배낭 문제를 단계별로 풀며 동적 계획법의 작동 원리를 이해하고, Python으로 구현합니다.

메모이제이션 테이블 초기화

Initializing the Memo Table

한국어

2차원 표 만들기

학교 시험 성적표 만들기

성적표에 학생(행)과 과목(열)을 배치하듯, DP 테이블도 행(보석)과 열(배낭 무게)로 구성합니다. 처음에는 모두 0으로 시작합니다!

테이블 구성

행: 보석 종류 (없음, 금괴, 수정, 루비, 진주) → 5행
열: 배낭 무게 (0kg ~ 7kg) → 8열

보석\무게	1kg	2kg	3kg	4kg	5kg	6kg	7kg
없음(0)	0	0	0	0	0	0	0
금괴(1)
수정(2)
루비(3)
진주(4)

"없음" 행과 "0kg" 열이 왜 필요할까?
보석이 0개이거나 배낭 무게가 0이면, 담을 수 있는 가격은 당연히 0! 이 기본 경우(base case)가 있어야 나머지 칸을 계산할 수 있습니다.

Python 초기화 코드

maxWeight = 7    # 배낭 최대 무게
rowCount = 4    # 보석 숫자
array = [[0 for _ in range(maxWeight+1)]
         for _ in range(rowCount+1)]

English

Creating the 2D Table

Like a School Report Card

Just as a report card has students (rows) and subjects (columns), the DP table has gems (rows) and bag weights (columns). Everything starts at 0!

Table Structure

Rows: gem types (none, gold, crystal, ruby, pearl) → 5 rows
Columns: bag weight (0kg ~ 7kg) → 8 columns

        Why the "None" row and "0kg" column?

        With 0 gems or 0kg capacity, value is always 0. These base cases are needed to compute all other cells.

Python Initialization

maxWeight = 7    # max bag weight
rowCount = 4    # number of gems
array = [[0 for _ in range(maxWeight+1)]
         for _ in range(rowCount+1)]

List Comprehension Review:
[0 for _ in range(8)] creates [0,0,0,0,0,0,0,0]
Wrapping it creates a 5×8 grid of zeros — our memo table!

단계 1: 물건이 1개일 때 (금괴)

Step 1: One Item (Gold Bar)

한국어

금괴(6kg, 13억)만 고려

쉽게 생각하기

금괴는 6kg입니다. 배낭이 6kg 이상이면 넣을 수 있고, 5kg 이하면 넣을 수 없습니다!

1~5kg 배낭: 금괴가 안 들어감!

금괴(6kg)가 배낭보다 무거우므로, 위 행(없음)의 값을 그대로 복사합니다. 즉 0억.

6kg 배낭: 금괴가 들어감!

비교

넣는 경우: 금괴 13억 + 여유분(6-6=0kg) 가격 0억 = 13억
안 넣는 경우: 위 행 값 = 0억
max(13, 0) = 13억!

7kg 배낭: 같은 방식

비교

금괴 13억 + 여유분(7-6=1kg) 가격 0억 = 13억
max(13, 0) = 13억!

보석\무게	0	1	2	3	4	5	6	7
없음	0	0	0	0	0	0	0	0
금괴	0	0	0	0	0	0	13	13

English

Only Gold Bar (6kg, 13B)

Think Simply

Gold bar weighs 6kg. If bag can hold 6+ kg → put it in. If 5kg or less → it doesn't fit!

Bags 1-5kg: Gold doesn't fit!

Gold (6kg) is heavier than the bag, so copy the value from the row above (0).

Bag 6kg: Gold fits!

Compare

Include: Gold 13B + leftover(6-6=0kg) value 0B = 13B
Exclude: row above = 0B
max(13, 0) = 13 billion!

The Decision Rule

        For each cell [row][col]:

        If item weight > col → array[row-1][col]

        If item weight ≤ col → max(

          money[row] + array[row-1][col-weight[row]],

          array[row-1][col]

        )

Key: "leftover" = current bag weight - item weight. Look up that leftover capacity in the previous row (already solved subproblem)!

단계 2: 물건이 2개일 때 (수정 추가)

Step 2: Two Items (Add Crystal)

한국어

수정(4kg, 8억)을 추가로 고려

1~3kg 배낭: 수정 안 들어감

수정(4kg)이 배낭보다 무거우므로, 위 행(금괴만)의 값을 그대로 → 0

4kg 배낭: 수정이 들어감!

비교

넣기: 수정 8억 + 여유분(4-4=0kg) 가격 0억 = 8억
안 넣기: 위 행 = 0억
max(8, 0) = 8억!

6kg 배낭: 핵심!

비교

넣기: 수정 8억 + 여유분(6-4=2kg) 가격 0억 = 8억
안 넣기: 위 행(금괴만 6kg) = 13억
max(8, 13) = 13억! ← 금괴가 더 좋음!

보석\무게	4	5	6	7
없음	0	0	0	0
금괴	0	0	13	13
수정	8	8	13	13

6kg, 7kg에서 금괴(13억)가 수정(8억)보다 낫다!
DP는 이렇게 매 칸마다 "넣기 vs 안 넣기"를 비교합니다.

English

Add Crystal (4kg, 8B)

Bags 1-3kg: Crystal doesn't fit

Crystal (4kg) is heavier, copy row above → 0

Bag 4kg: Crystal fits!

Compare

Include: 8B + leftover(0kg) = 8B
Exclude: row above = 0B
max(8, 0) = 8 billion!

Bag 6kg: Key Decision!

Compare

Include: Crystal 8B + leftover(2kg) = 8 + 0 = 8B
Exclude: row above (Gold at 6kg) = 13B
max(8, 13) = 13B! ← Gold bar alone is better!

        Reading the table: Each cell tells us the best possible value we can get using only the gems available up to that row, with a bag of that column's capacity.
      

This is the power of DP: At each cell, we systematically compare "include this item" vs "exclude this item" and always keep the better option.

단계 3: 물건이 3개일 때 (루비 추가)

Step 3: Three Items (Add Ruby)

한국어

루비(3kg, 6억) 추가 — 핵심 단계!

3kg 배낭: 루비 들어감

루비 6억 + 여유분(0kg)=0억 = 6억 vs 위 행 0억 → 6억

4~5kg 배낭

루비 6억 + 여유분 가격 vs 위 행(수정 포함) 8억 → 8억! (수정이 더 좋음)

★ 7kg 배낭: DP의 마법!

        넣기: 루비 6억 + 여유분(7-3=4kg) 가격

        → 4kg은 위 행(수정 행)에서 이미 계산됨 = 8억 (수정)

        → 6억 + 8억 = 14억!

        안 넣기: 위 행(수정 행) 7kg = 13억

        max(14, 13) = 14억!!!

보석\무게	3	4	5	6	7
없음	0	0	0	0	0
금괴	0	0	0	13	13
수정	0	8	8	13	13
루비	6	8	8	13	14

이것이 DP의 핵심! 루비를 넣고 남은 4kg에, 이전에 이미 계산한 최적값(수정 8억)을 재활용합니다. 이것이 바로 메모이제이션!

English

Add Ruby (3kg, 6B) — The Key Step!

Bag 3kg: Ruby fits

Ruby 6B + leftover(0kg)=0 = 6B vs above 0B → 6B

★ Bag 7kg: DP Magic!

        Include: Ruby 6B + leftover(7-3=4kg) value

        → 4kg was already computed in row above = 8B (Crystal)

        → 6B + 8B = 14 billion!

        Exclude: row above at 7kg = 13B

        max(14, 13) = 14 billion!!!

This IS the essence of DP! After putting Ruby in, the remaining 4kg capacity looks up the previously computed optimal value (Crystal, 8B). This is memoization in action!

Ruby(3kg) + Crystal(4kg) = 7kg, 14 billion
DP found that combining these two is better than the single Gold bar (13B). The greedy algorithm missed this because it always picked Gold first!

단계 4: 완성 (진주 추가)

Step 4: Complete Table (Add Pearl)

한국어

진주(5kg, 12억) 추가 → 테이블 완성!

같은 규칙으로 마지막 행 채우기

1~4kg: 진주(5kg) 안 들어감 → 위 행 복사

5kg: 진주 12억 + 여유분(0kg) 0억 = 12억 vs 위 행 8억 → 12억

6kg: 진주 12억 + 여유분(1kg) 0억 = 12억 vs 위 행 13억 → 13억

7kg: 진주 12억 + 여유분(2kg) 0억 = 12억 vs 위 행 14억 → 14억

보석\무게	3	4	5	6	7
없음	0	0	0	0	0
금괴	0	0	0	13	13
수정	0	8	8	13	13
루비	6	8	8	13	14
진주	6	8	12	13	14

        최종 답: array[4][7] = 14억!

        수정(4kg, 8억) + 루비(3kg, 6억) = 7kg, 14억이 최적!

테이블의 마지막 칸(오른쪽 아래)이 항상 전체 문제의 최적 답입니다!

English

Add Pearl (5kg, 12B) → Complete!

Fill the Last Row

1-4kg: Pearl(5kg) doesn't fit → copy row above

5kg: Pearl 12B + leftover(0kg) = 12B vs above 8B → 12B

6kg: Pearl 12B + leftover(1kg) = 12B vs above 13B → 13B

7kg: Pearl 12B + leftover(2kg) = 12B vs above 14B → 14B

        Final answer: array[4][7] = 14 billion!

        Crystal(4kg, 8B) + Ruby(3kg, 6B) = 7kg, 14B is optimal!

Reading the Complete Table

The bottom-right cell always contains the optimal answer to the full problem. Each cell builds on previously solved subproblems — that's the beauty of DP!

Summary of the Rule:
if weight[row] > col: → copy above
else: → max(include, exclude)

배낭 문제 점화식 정리

Knapsack Recurrence Formula

한국어

공식으로 정리하기

점화식 (Recurrence Relation):

# 경우 1: 물건이 배낭에 안 들어갈 때
if weight[row] > col :
    array[row][col] = array[row-1][col]

# 경우 2: 물건이 배낭에 들어갈 때
else :
    value1 = money[row] + array[row-1][col-weight[row]]
    value2 = array[row-1][col]
    array[row][col] = max(value1, value2)

각 변수의 의미

변수	의미
`weight[row]`	현재 행의 보석 무게
`col`	현재 열(배낭 무게)
`money[row]`	현재 보석의 가격
`array[row-1][col]`	이 보석을 안 넣은 경우의 최적값
`array[row-1][col-weight[row]]`	여유분에 해당하는 이전 최적값

English

The Formula Explained

Recurrence Relation:

# Case 1: Item doesn't fit in bag
if weight[row] > col:
    array[row][col] = array[row-1][col]

# Case 2: Item fits in bag
else:
    value1 = money[row] + array[row-1][col-weight[row]]
    value2 = array[row-1][col]
    array[row][col] = max(value1, value2)

Variable Meanings

Variable	Meaning
`weight[row]`	Weight of current item
`col`	Current bag capacity
`money[row]`	Value of current item
`value1`	Value if we INCLUDE this item
`value2`	Value if we EXCLUDE this item

The genius: array[row-1][col-weight[row]] looks up the best value for the leftover capacity — and that was already computed! No redundant work.

Code14-01: 배낭 문제 구현

Code14-01: Knapsack Implementation

한국어

Python으로 구현하기

## 함수 선언 부분 ##
def knapsack():
    print('## 메모이제이션 배열 ##')
    array = [[0 for _ in range(maxWeight+1)]
             for _ in range(rowCount+1)]

    for row in range(1, rowCount+1):
        print(row, '개 -->', end=' ')
        for col in range(1, maxWeight+1):
            if weight[row] > col:
                array[row][col] = array[row-1][col]
            else:
                value1 = money[row] + array[row-1][col-weight[row]]
                value2 = array[row-1][col]
                array[row][col] = max(value1, value2)
            print('%2d' % array[row][col], end=' ')
        print()
    return array[rowCount][maxWeight]

## 전역 변수 선언 부분 ##
maxWeight = 7
rowCount = 4
weight = [0, 6, 4, 3, 5]
money  = [0, 13, 8, 6, 12]

## 메인 코드 부분 ##
maxValue = knapsack()
print()
print('배낭에 담을 수 있는 보석의 최대 가격 -->', maxValue, '억원')

실행 결과

## 메모이제이션 배열 ##
1 개 -->  0  0  0  0  0 13 13
2 개 -->  0  0  0  8  8 13 13
3 개 -->  0  0  6  8  8 13 14
4 개 -->  0  0  6  8 12 13 14

배낭에 담을 수 있는 보석의 최대 가격 --> 14 억원

English

Python Implementation

Code Walkthrough

1

Line 4-5: Create a (rowCount+1) × (maxWeight+1) table filled with zeros

2

Line 7-8: Double loop — outer for each gem, inner for each bag weight

3

Line 9-10: If item is too heavy → copy value from row above

4

Line 11-14: If item fits → compare include vs exclude, take the max

5

Line 16: Return the bottom-right cell = optimal answer

Key Data Structures

weight = [0, 6, 4, 3, 5]
# index:   0   1   2   3   4
# item:  none gold crys ruby pearl

money = [0, 13, 8, 6, 12]
# Values match weights above
# Index 0 is a placeholder ("no item")

Note: Both arrays start with 0 at index 0 to match the "none" row in our table.

코드 핵심 부분 상세 설명

Detailed Code Explanation

한국어

한 줄씩 이해하기

1. 배열 초기화

array = [[0 for _ in range(8)] for _ in range(5)]

5행 × 8열의 2차원 배열을 0으로 초기화. 행=보석 개수+1, 열=최대무게+1

2. 이중 반복문

for row in range(1, 5):    # 보석 1~4
    for col in range(1, 8):  # 무게 1~7

0행과 0열은 이미 0이므로, 1부터 시작합니다.

3. 핵심 비교

if weight[row] > col:  # 보석이 안 들어가면
    array[row][col] = array[row-1][col]  # 위 행 복사
else:  # 보석이 들어가면
    value1 = money[row] + array[row-1][col-weight[row]]
    # ↑ 넣기: 보석 가격 + 여유분의 이전 최적값
    value2 = array[row-1][col]
    # ↑ 안 넣기: 이전 행의 같은 무게 최적값
    array[row][col] = max(value1, value2)
    # ↑ 둘 중 큰 값 선택!

예시 (row=3, col=7, 루비):
value1 = 6 + array[2][4] = 6 + 8 = 14
value2 = array[2][7] = 13
max(14, 13) = 14!

English

Line-by-Line Understanding

1. Array Initialization

array = [[0 for _ in range(8)] for _ in range(5)]

Creates a 5×8 grid of zeros. Rows = gems+1, Cols = maxWeight+1

2. The Double Loop

Outer loop: each gem (row 1 to 4)
Inner loop: each bag capacity (col 1 to 7)
Row 0 and Col 0 are already 0 (base cases).

3. The Core Comparison

        Case 1 (doesn't fit):

        weight[row] > col → item too heavy

        Copy the value from previous row (without this item)

        Case 2 (fits):

        weight[row] ≤ col → item can go in

        Compare: include it vs exclude it → take max

Tracing Example (row=3, col=7, Ruby):

# Ruby: weight=3, money=6
# col=7, weight[3]=3 → 3 ≤ 7, so else branch
value1 = 6 + array[2][7-3]  # = 6 + array[2][4] = 6+8 = 14
value2 = array[2][7]         # = 13
array[3][7] = max(14, 13)  # = 14!

배낭 문제 알고리즘 흐름도

Knapsack Algorithm Flowchart

한국어

전체 흐름 한눈에 보기

English

Complete Flow at a Glance

1

Initialize a 2D array with all zeros

2

Outer loop: for each item (row 1 to n)

3

Inner loop: for each capacity (col 1 to W)

4

Decision: Can the item fit? (weight[row] ≤ col?)

5a

No: Copy value from row above

5b

Yes: Compare include vs exclude → keep max

6

Return array[n][W] — the optimal value!

        Time Complexity: O(n × W)

        n = number of items, W = max weight

        4 items × 7kg = only 28 operations!

Space Complexity: O(n × W)
We need a 2D array of size (n+1) × (W+1) to store all subproblem results.

Part 2 연습문제

Part 2 Practice (Self14-01)

한국어

Self14-01: 보석 순서 변경 배낭 문제

문제: 보석 순서를 바꿔서 풀기

Code14-01에서 보석 순서를 진주, 루비, 금괴, 수정으로 변경하여 같은 결과(14억)가 나오는지 확인하세요.

힌트: weight와 money 배열의 순서만 바꾸면 됩니다.

## 전역 변수부
maxWeight = 7
rowCount = 4
weight = [0, 5, 3, 6, 4]   # 진주,루비,금괴,수정
money =  [0, 12, 6, 13, 8]  # 진주,루비,금괴,수정

결과는 동일하게 14억! 보석의 순서를 바꿔도 DP는 항상 같은 최적값을 찾습니다.

문제: 테이블 직접 채우기

다음 데이터로 메모이제이션 테이블을 직접 채워보세요.
배낭 최대 무게: 5kg
물건A: 2kg, 3만원 / 물건B: 3kg, 4만원 / 물건C: 4kg, 5만원

\	2	3	4	5
없음	0	0	0	0
A	3	3	3	3
B	3	4	4	7
C	3	4	5	7

최적 답: A(2kg)+B(3kg) = 5kg, 7만원!

English

Self14-01: Changed Order Knapsack

Problem: Change Gem Order

In Code14-01, change the gem order to Pearl, Ruby, Gold, Crystal. Verify the result is still 14 billion.

weight = [0, 5, 3, 6, 4]  # Pearl,Ruby,Gold,Crystal
money =  [0, 12, 6, 13, 8]

Same result: 14 billion! DP finds the optimal value regardless of item order.

Problem: Fill the Table Yourself

Max bag: 5kg. A: 2kg/$3, B: 3kg/$4, C: 4kg/$5. Fill the memo table.

Optimal: A(2kg) + B(3kg) = 5kg, $7!

Note: C alone at 4kg gives $5, but A+B at 5kg gives $7 — DP finds this combination!

03

Part 3

동적 계획법의 응용

Applications of Dynamic Programming

황금 미로 문제, 피보나치 수열 비교 등 DP의 다양한 응용을 배웁니다.

황금 미로에서 부자 되기

Getting Rich in the Gold Maze

한국어

두 번째 DP 문제: 황금 미로

보드게임 비유

5×5 보드게임에서 왼쪽 위에서 출발해 오른쪽 아래까지 이동합니다. 각 칸에 황금이 있고, 오른쪽 또는 아래쪽으로만 이동 가능합니다. 최대 황금을 모으며 도착하세요!

황금 미로 (5×5)

1	4	4	2	2
1	3	3	0	5
1	2	4	3	0
3	3	0	4	2
1	3	4	5	3

        규칙:

        • 출발: [0][0] (왼쪽 위)

        • 도착: [4][4] (오른쪽 아래)

        • 이동: 오른쪽(→) 또는 아래(↓)만 가능

        • 목표: 경로의 황금 합계를 최대로!

왜 DP가 필요할까? 모든 경로를 시도하면 경우의 수가 매우 많습니다. 5×5에서도 수십 가지 경로가 있고, 크기가 커지면 폭발적으로 증가!

English

Second DP Problem: Gold Maze

Board Game Analogy

In a 5×5 board game, start at the top-left and reach the bottom-right. Each cell has gold. You can only move right (→) or down (↓). Collect the maximum gold!

Gold Maze (5×5)

        Rules:

        • Start: [0][0] (top-left)

        • End: [4][4] (bottom-right)

        • Movement: right (→) or down (↓) only

        • Goal: maximize total gold on the path!

Why DP Works Here

The maximum gold at any cell = that cell's gold + max(gold from left, gold from above). Each cell's optimal value depends on previously solved cells — perfect for DP!

Recurrence:
memo[r][c] = goldMaze[r][c] + max(memo[r][c-1], memo[r-1][c])
First row: cumulative sum from left
First col: cumulative sum from top

황금 미로 메모이제이션

Gold Maze Memoization

한국어

단계별 메모 테이블 채우기

1단계: 첫 번째 행 (→ 방향만 가능)

왼쪽부터 누적합: 1, 1+4=5, 5+4=9, 9+2=11, 11+2=13

2단계: 첫 번째 열 (↓ 방향만 가능)

위에서부터 누적합: 1, 1+1=2, 2+1=3, 3+3=6, 6+1=7

3단계: 나머지 칸 채우기

각 칸 = 현재 황금 + max(왼쪽 메모, 위쪽 메모)

완성된 메모이제이션 테이블

1	5	9	11	13
2	8	12	12	18
3	10	16	19	19
6	13	16	23	25
7	16	20	28	31

        최대 황금: 31개!

        [4][4] = 31이 최적 경로의 황금 합계입니다.

예시: memo[1][1] 계산
goldMaze[1][1] = 3
max(memo[1][0], memo[0][1]) = max(2, 5) = 5
memo[1][1] = 3 + 5 = 8

English

Step-by-Step Memo Table

Step 1: First Row (can only go →)

Cumulative sum: 1, 5, 9, 11, 13

Step 2: First Column (can only go ↓)

Cumulative sum: 1, 2, 3, 6, 7

Step 3: Fill Remaining Cells

Each cell = current gold + max(left memo, above memo)

        Maximum gold: 31!

        memo[4][4] = 31 is the optimal path total.

Tracing memo[1][1]:

# goldMaze[1][1] = 3
# Left: memo[1][0] = 2
# Above: memo[0][1] = 5
memo[1][1] = 3 + max(2, 5) = 3 + 5 = 8

The approach is identical to Knapsack: build a table, fill base cases first, then use the recurrence for remaining cells. The bottom-right cell = optimal answer.

Code14-02: 황금 미로 구현

Code14-02: Gold Maze Implementation

한국어

Python 코드

## 함수 선언 부분 ##
def growRich():
    memo = [[0 for _ in range(COL)] for _ in range(ROW)]
    memo[0][0] = goldMaze[0][0]

    # 첫 행 채우기 (→ 방향만)
    rowSum = memo[0][0]
    for i in range(1, ROW):
        rowSum += goldMaze[0][i]
        memo[0][i] = rowSum

    # 첫 열 채우기 (↓ 방향만)
    colSum = memo[0][0]
    for i in range(1, COL):
        colSum += goldMaze[i][0]
        memo[i][0] = colSum

    # 나머지 칸 채우기
    for row in range(1, ROW):
        for col in range(1, COL):
            if memo[row][col-1] > memo[row-1][col]:
                memo[row][col] = memo[row][col-1] + goldMaze[row][col]
            else:
                memo[row][col] = memo[row-1][col] + goldMaze[row][col]

    return memo[ROW-1][COL-1]

## 전역 변수 선언 부분 ##
ROW, COL = 5, 5
goldMaze = [[1, 4, 4, 2, 2],
            [1, 3, 3, 0, 5],
            [1, 2, 4, 3, 0],
            [3, 3, 0, 4, 2],
            [1, 3, 4, 5, 3]]

## 메인 코드 부분 ##
maxGold = growRich()
print('황금 미로에서 얻은 최대 황금 개수 -->', maxGold)

실행 결과

황금 미로에서 얻은 최대 황금 개수 --> 31

English

Code Walkthrough

1

Line 3-4: Create ROW×COL memo table, set [0][0] to maze start value

2

Lines 7-9: Fill first row with cumulative sums (can only go right)

3

Lines 12-14: Fill first column with cumulative sums (can only go down)

4

Lines 17-21: For remaining cells: compare left vs above, add current gold

5

Line 23: Return bottom-right cell = maximum gold

        Key difference from Knapsack:

        • Knapsack: max(include, exclude)

        • Gold Maze: max(from left, from above) + current cell

        Both use the same DP principle: build on previous results!

Complexity: O(ROW × COL) = O(n²) for an n×n maze. Much better than trying all paths!

Ex14-01: 황금 미로 길 표시하기

Ex14-01: Showing the Path

한국어

최적 경로 역추적하기

길 찾기

최대 황금 31개를 얻을 수 있다는 것은 알았는데, 실제로 어떤 경로로 이동해야 할까요? 도착점에서 출발점으로 거꾸로 추적합니다!

역추적 방법

1

도착점 [4][4]에서 시작

2

왼쪽 memo와 위쪽 memo를 비교

3

더 큰 쪽에서 왔으므로, 그 방향으로 이동

4

[0][0]에 도착할 때까지 반복

역추적 코드 핵심

row, col = ROW-1, COL-1
memo[row][col] = 0  # 경로 표시: 0으로 설정
while row != 0 or col != 0:
    if row-1 >= 0 and col-1 >= 0:
        if memo[row-1][col] > memo[row][col-1]:
            row -= 1    # 위에서 왔음
        else:
            col -= 1    # 왼쪽에서 왔음
    elif row-1 < 0:
        col -= 1        # 첫 행이면 왼쪽으로만
    else:
        row -= 1        # 첫 열이면 위로만
    memo[row][col] = 0

English

Backtracking the Optimal Path

Finding the Way Back

We know the maximum gold is 31, but which path should we take? Trace back from the destination to the start!

Backtracking Method

1

Start at destination [4][4]

2

Compare left memo vs above memo

3

The larger value = where we came from → move there

4

Repeat until reaching [0][0]

        Path found by marking 0s:

        The cells set to 0 show the optimal path. All other cells keep their memo values, making the path visually clear.

Why backtrack? The memo table tells us the TOTAL value at each cell, but not which direction we chose. By comparing neighbors backward, we reconstruct the decisions.

Ex14-02: 피보나치 수열과 DP

Ex14-02: Fibonacci & DP

한국어

재귀 vs DP 비교

같은 문제, 다른 방식

피보나치 수열: 1, 1, 2, 3, 5, 8, 13, 21, ...
규칙: F(n) = F(n-1) + F(n-2)
재귀로 풀면? DP로 풀면? 속도가 엄청나게 달라집니다!

재귀 방식 (느림!)

def recu_fibo(n):
    global count_recu
    count_recu += 1
    if n < 2:
        return 1
    else:
        return recu_fibo(n-1) + recu_fibo(n-2)

DP 방식 (빠름!)

def dp_fibo(n):
    global count_dp
    memo = [1, 1]
    if n < 2:
        return memo[n]
    else:
        for i in range(2, n+1):
            memo.append(memo[i-1] + memo[i-2])
            count_dp += 1
        return memo[n]

30번째 피보나치 수열 결과

재귀 방식 --> 답: 1346269, 반복수: 2692537
DP 방식  --> 답: 1346269, 반복수: 29

같은 답인데, 재귀는 269만 번, DP는 29번!

English

Recursion vs DP Comparison

Same Problem, Different Approaches

Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, ...
Rule: F(n) = F(n-1) + F(n-2)
Recursive? DP? The speed difference is enormous!

Why Recursion is Slow

Result for 30th Fibonacci

Method	Answer	Operations
Recursion	1,346,269	2,692,537
DP	1,346,269	29

DP avoids redundant calls! Each F(k) is computed only once and stored in the memo list.

재귀 vs DP: 왜 이렇게 다를까?

Why Such a Big Difference?

한국어

중복 계산의 폭발

같은 숙제를 100번?

선생님이 수학 숙제를 내주셨는데, 매번 처음부터 다시 풀어야 한다면? DP는 한 번 풀고 답을 적어두고 다음에 바로 꺼내 씁니다!

재귀의 문제점

F(30)을 구하려면 F(29)+F(28)이 필요하고, F(29)를 구하려면 F(28)+F(27)이 필요하고... F(28)이 두 번 계산됩니다! 이런 중복이 눈덩이처럼 불어납니다.

비교 표

n	재귀 호출 횟수	DP 계산 횟수	배율
10	177	9	약 20배
20	21,891	19	약 1,152배
30	2,692,537	29	약 92,846배!
40	331,160,281	39	약 849만 배!!

        재귀 시간복잡도: O(2n) — 지수적 증가

        DP 시간복잡도: O(n) — 선형 증가

English

The Explosion of Redundant Work

Doing the Same Homework 100 Times?

Imagine if your teacher asked you to solve a math problem, but you had to start from scratch every time? DP solves it once, writes down the answer, and just looks it up next time!

The Recursion Problem

To compute F(30), we need F(29)+F(28). But F(29) also needs F(28)+F(27)... F(28) is computed twice! This snowball effect multiplies exponentially.

Comparison

n	Recursive Calls	DP Computations	Ratio
10	177	9	~20×
20	21,891	19	~1,152×
30	2,692,537	29	~92,846×!
40	331,160,281	39	~8.5 million×!!

        Recursion: O(2n) — exponential growth

        DP: O(n) — linear growth

        This is why DP matters: it turns impossible problems into trivial ones by eliminating redundant computation!

Self14-02: 압정 미로 (최소 경로)

Self14-02: Thumbtack Maze (Min Path)

한국어

반대로 생각하기: 최소를 찾자!

위험한 미로!

이번에는 각 칸에 압정이 놓여 있습니다. 압정을 최소한으로 밟으며 도착점까지 가야 합니다. 황금 미로와 반대!

문제: 황금 미로 코드를 수정하여 압정을 최소로 밟는 경로를 찾으세요

힌트: max를 어떤 함수로 바꾸면 될까요?

핵심 변경: max → 부등호 반대!

# 변경 부분 (max를 min 개념으로)
if memo[row][col-1] < memo[row-1][col]:
    memo[row][col] = memo[row][col-1] + goldMaze[row][col]
else:
    memo[row][col] = memo[row-1][col] + goldMaze[row][col]

부등호만 >에서 <로 바꾸면 왼쪽과 위쪽 중 작은 값을 선택하게 됩니다.

압정 미로에서 밟은 최소 압정 개수 --> 19

최대를 구하던 알고리즘이 부등호 하나로 최소 경로 알고리즘이 됩니다!

DP의 유연함: 같은 구조에서 비교 연산만 바꾸면 최대→최소 문제로 전환 가능!

English

Think in Reverse: Find the Minimum!

Dangerous Maze!

This time, each cell has thumbtacks. You need to reach the end stepping on as few as possible. The opposite of the gold maze!

Problem: Modify the gold maze code to find the path with minimum thumbtacks

Hint: What should you change max to?

Key Change: Flip the comparison!

# Change > to < in the comparison
if memo[row][col-1] < memo[row-1][col]:
    # Pick the SMALLER value (fewer tacks)
    memo[row][col] = memo[row][col-1] + maze[row][col]

Just changing > to < switches from "maximum gold" to "minimum thumbtacks"!

Result: 19 thumbtacks

Flexibility of DP: The same structure works for both max and min problems — just change the comparison operator!

동적 계획법이 쓰이는 곳

Where DP is Used

한국어

DP가 활용되는 다양한 문제들

배낭 문제

제한된 용량에서 최대 가치 조합 찾기

최단/최장 경로

그래프에서 최적 경로 탐색

피보나치 수열

중복 계산 제거로 효율화

문자열 편집 거리

두 문자열의 유사도 측정

DP를 사용할 수 있는 조건

✓

최적 부분 구조: 큰 문제의 답이 작은 문제의 답으로 구성

✓

중복되는 하위 문제: 같은 작은 문제가 반복 등장

        DP 문제 풀이 체크리스트:

        1. 점화식을 세울 수 있는가?

        2. 메모 테이블을 만들 수 있는가?

        3. 기본 경우(base case)를 정의할 수 있는가?

        → 모두 "예"라면 DP로 풀 수 있습니다!

English

Problems Where DP Shines

Knapsack

Find max value within weight limit

Shortest/Longest Path

Find optimal routes in graphs

Fibonacci

Eliminate redundant computation

Edit Distance

Measure string similarity

Checklist for Using DP

✓

Optimal Substructure: Big answer = composed of small answers

✓

Overlapping Subproblems: Same small problem appears repeatedly

        DP Problem-Solving Checklist:

        1. Can you write a recurrence relation?

        2. Can you create a memo table?

        3. Can you define base cases?

        → If all "yes," DP can solve it!

14장 전체 요약

Chapter 14 Summary

한국어

동적 계획법 핵심 정리

개념	설명
동적 계획법	큰 문제를 작은 문제로 나누고 결과를 저장하는 알고리즘
메모이제이션	한 번 계산한 결과를 표에 저장해 재사용
점화식	작은 문제의 답으로 큰 문제를 푸는 규칙
배낭 문제	무게 제한 내 최대 가치 조합 찾기
황금 미로	최대/최소 경로 합계 찾기

알고리즘 비교 최종 정리

방법	정확성	속도	특징
브루트 포스	O	O(2ⁿ)	모든 경우 시도
탐욕	△	O(n log n)	눈앞의 최선
DP	O	O(n×W)	메모이제이션

        DP = 정확 + 빠름!

        "이전에 풀었던 문제의 답을 기억한다"는 단순한 아이디어가 놀라운 성능 향상을 만듭니다.

핵심 코드 패턴:
① 메모 테이블 초기화
② 기본 경우 채우기
③ 점화식으로 나머지 채우기
④ 마지막 칸 = 최적 답

English

Key Takeaways

Concept	Description
DP	Divide + Store results = No redundant work
Memoization	Save computed results in a table for reuse
Recurrence	Rule linking small answers to big answers
Knapsack	Max value within weight limit
Gold Maze	Max/min path sum in a grid

Algorithm Comparison

Method	Accuracy	Speed	Trait
Brute Force	Always	O(2ⁿ)	Try everything
Greedy	Sometimes	O(n log n)	Local best
DP	Always	O(n×W)	Memoization

        DP = Accurate + Fast!

        The simple idea of "remembering previous answers" creates amazing performance gains.

Part 3 종합 연습문제

Part 3 Comprehensive Practice

한국어

종합 문제

문제 1: 배낭 문제 변형

배낭 최대 무게가 6kg이고, 보석이 다음과 같을 때 최대 가격은?
다이아: 3kg, 10억 / 에메랄드: 2kg, 7억 / 사파이어: 4kg, 9억

\	2	3	4	5	6
없음	0	0	0	0	0
다이아	0	10	10	10	10
에메랄드	7	10	10	17	17
사파이어	7	10	10	17	17

최대 가격: 17억! 다이아(3kg, 10억) + 에메랄드(2kg, 7억) = 5kg

문제 2: 황금 미로 3×3

다음 3×3 미로에서 최대 황금은?

2	3	1
1	5	2
4	2	1

2	5	6
3	10	12
7	12	13

최대 황금: 13개! 경로: 2→3→5→2→1 또는 2→3→5→2→1

문제 3: DP vs 재귀 피보나치

F(20)을 재귀로 구할 때 함수 호출 횟수는 약 몇 번인가?

약 21,891번!

재귀는 O(2ⁿ)이므로 약 2²⁰ ≈ 100만에 가까운 호출이 일어나지만, 실제로는 트리 구조 때문에 약 21,891번입니다. DP라면 단 19번이면 충분합니다.

English

Comprehensive Problems

Q1: Knapsack Variation

Max weight 6kg. Diamond: 3kg/10B, Emerald: 2kg/7B, Sapphire: 4kg/9B. Maximum value?

Max value: 17 billion!
Diamond(3kg) + Emerald(2kg) = 5kg, 17B

Q2: 3×3 Gold Maze

Find the maximum gold in a 3×3 maze: [[2,3,1],[1,5,2],[4,2,1]]

Memo table: [[2,5,6],[3,10,12],[7,12,13]]

Maximum gold: 13!

Q3: F(20) Recursive Calls?

How many function calls does recursive Fibonacci need for F(20)?

About 21,891 calls!

DP needs only 19 computations. That's a 1,152× difference!