Greedy Algorithm | "Best Choice Every Step" Complete Guide
이 글의 핵심
Greedy algorithms make the locally optimal choice at each step. Learn when to use greedy, how to prove correctness, and master common greedy patterns.
Introduction
Greedy algorithms seem simple to implement, but without proving correctness, they can produce wrong answers. This guide helps you master typical greedy patterns and recognize when to switch to DP or other strategies.
”Does Best Choice Every Step Lead to Optimal Solution?”
Greedy algorithms make the best choice at each step. They don’t always guarantee optimal solutions, but when provably correct, they are very efficient.
1. What is Greedy Algorithm?
Concept
Greedy algorithms select only the local optimum at each step. Below is a coin change example that uses the largest denomination first. However, if coin denominations are arbitrary, greedy may not guarantee minimum count, so verify that greedy conditions (exchange property, sorting conditions, etc.) hold for the problem.
# Example: Coin change (500, 100, 50, 10 won)
# Make change for 1260 won
coins = [500, 100, 50, 10]
change = 1260
count = 0
for coin in coins:
count += change // coin # Use as many as possible
change %= coin
print(count) # 6 (500*2 + 100*2 + 50*1 + 10*1)Greedy vs DP
| Feature | Greedy | DP |
|---|---|---|
| Selection | Current best | All cases |
| Time Complexity | O(n log n) | O(n²) ~ O(2ⁿ) |
| Optimal Guarantee | X (proof needed) | O |
| Implementation | Simple | Complex |
2. Representative Problems
Problem 1: Meeting Rooms
def max_meetings(meetings):
"""
Schedule maximum number of meetings
[(start, end), ...]
"""
# Sort by end time
meetings.sort(key=lambda x: x[1])
count = 0
last_end = 0
for start, end in meetings:
if start >= last_end:
count += 1
last_end = end
return count
# Test
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings)) # 4
# Cannot select (1,4), (5,7), (5,9) → Select (1,4), (5,7)Why Sort by End Time?
Sort by start time: ❌
[(0,6), (1,4), (3,5), (5,7)] → Select (0,6) only (1 meeting)
Sort by end time: ✅
[(1,4), (3,5), (0,6), (5,7)] → Select (1,4), (5,7), (5,9) (3 meetings)
Key: Early end time leaves more room for next meetingsProblem 2: Coin Change
def min_coins(coins, amount):
"""
Minimum number of coins
"""
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount >= coin:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# Test
coins = [500, 100, 50, 10]
print(min_coins(coins, 1260)) # 6
# ❌ Greedy fails
coins = [10, 7, 1]
amount = 14
# Greedy: 10 + 1 + 1 + 1 + 1 = 5 coins
# Optimal: 7 + 7 = 2 coins (need DP!)Problem 3: Create Largest Number
def make_largest_number(number, k):
"""
Remove k digits to create largest number
"1924", k=2 → "94"
"""
stack = []
removed = 0
for digit in number:
# Remove stack top if smaller than current
while stack and removed < k and stack[-1] < digit:
stack.pop()
removed += 1
stack.append(digit)
# If haven't removed k digits, remove from end
return ''.join(stack[:len(stack) - (k - removed)])
# Test
print(make_largest_number("1924", 2)) # "94"
print(make_largest_number("1231234", 3)) # "3234"Step-by-Step Trace:
"1924", k=2
Step 1: digit='1', stack=['1']
Step 2: digit='9', stack=['9'] (remove '1', removed=1)
Step 3: digit='2', stack=['9','2']
Step 4: digit='4', stack=['9','4'] (remove '2', removed=2)
Result: "94"3. Greedy Proof
Proof Methods
1) Exchange Argument
"Swapping greedy choice with another choice does not improve solution"2) Proof by Contradiction
"Assume greedy is not optimal → Derive contradiction"Example: Meeting Rooms Proof
"Selecting meeting with earliest end time is optimal"
Proof:
- Selecting another meeting means later end time
- Later end time reduces options for next meetings
- Therefore, earliest end time is optimalWhen Greedy Fails
# Example: Coin change with arbitrary denominations
coins = [10, 7, 1]
amount = 14
# Greedy approach
def greedy_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count
print(greedy_coins(coins, 14)) # 5 (10+1+1+1+1)
# Optimal solution (DP needed)
# 7 + 7 = 2 coins
# Lesson: Greedy fails when larger denomination
# prevents using optimal combination of smaller ones4. Practical Problems
Problem 1: Gym Clothes (Programmers)
def solution(n, lost, reserve):
"""
Lending gym clothes
"""
# Exclude students who have reserve but also lost
lost_set = set(lost) - set(reserve)
reserve_set = set(reserve) - set(lost)
for r in sorted(reserve_set):
# Lend to lower number first
if r - 1 in lost_set:
lost_set.remove(r - 1)
elif r + 1 in lost_set:
lost_set.remove(r + 1)
return n - len(lost_set)
# Test
print(solution(5, [2, 4], [1, 3, 5])) # 5Problem 2: Joystick (Programmers)
def solution(name):
"""
Minimum joystick moves
"""
answer = 0
min_move = len(name) - 1 # Move right only
for i, char in enumerate(name):
# Up/down movement (A → char)
answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
# Optimize left/right movement
next_idx = i + 1
while next_idx < len(name) and name[next_idx] == 'A':
next_idx += 1
# Right → Left vs Left → Right
min_move = min(
min_move,
i + i + len(name) - next_idx, # Right → Left
i + len(name) - next_idx + len(name) - next_idx # Left → Right
)
return answer + min_move
# Test
print(solution("JEROEN")) # 565. Common Greedy Patterns
Pattern 1: Sorting + Selection
# Most greedy problems start with sorting
# 1. Sort by end time (meeting rooms)
meetings.sort(key=lambda x: x[1])
# 2. Sort descending (coin change)
coins.sort(reverse=True)
# 3. Custom sort (largest number)
nums.sort(key=lambda x: x*10, reverse=True)Pattern 2: Stack-Based Greedy
def remove_k_digits(num, k):
"""
Remove k digits to create smallest number
"""
stack = []
removed = 0
for digit in num:
# Remove if stack top is larger
while stack and removed < k and stack[-1] > digit:
stack.pop()
removed += 1
stack.append(digit)
# Remove from end if needed
result = ''.join(stack[:len(stack) - (k - removed)])
# Remove leading zeros
return result.lstrip('0') or '0'
# Test
print(remove_k_digits("1432219", 3)) # "1219"Pattern 3: Two Pointers + Greedy
def assign_cookies(greed, cookies):
"""
Assign cookies to children
greed[i] = minimum cookie size for child i
"""
greed.sort()
cookies.sort()
child = 0
cookie = 0
while child < len(greed) and cookie < len(cookies):
if cookies[cookie] >= greed[child]:
child += 1
cookie += 1
return child
# Test
greed = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(greed, cookies)) # 1Practical Tips
Identifying Greedy Problems
# ✅ Greedy signals
# 1. "Max/min" + sorting hint
# 2. Tight time limit (need O(n log n))
# 3. Hard to find counterexample
# ❌ Greedy not possible
# 1. Counterexample exists
# 2. Need to consider "all cases"
# 3. Previous choices affect future (→ DP)Debugging Strategy
# 1. Test with small examples
# - Manually verify optimal solution
# - Compare with greedy result
# 2. Look for counterexamples
# - Try edge cases
# - Try reverse sorted input
# 3. Compare with DP
# - If greedy fails, try DP
# - If DP too slow, prove greedySummary
Key Points
- Greedy: Best choice every step, O(n log n)
- Proof Required: Check for counterexamples
- Sorting: Most problems require sorting first
- Compare with DP: Greedy is faster but not always optimal
Problem Identification
| Signal | Greedy | DP |
|---|---|---|
| Selection | Current best | All cases |
| Time | O(n log n) | O(n²) |
| Proof | Required | Not required |
| Example | Meeting rooms | Knapsack |
Recommended Problems
Baekjoon
LeetCode
- LeetCode 455: Assign Cookies
- LeetCode 435: Non-overlapping Intervals
- LeetCode 402: Remove K Digits
- LeetCode 621: Task Scheduler
Programmers
Related Posts
- Two Pointers | O(n²) → O(n) Optimization Complete Guide
- Algorithm Series Full Index
- Arrays and Lists
- Stack and Queue
Keywords
Greedy Algorithm, Greedy, Optimization, Sorting, Meeting Rooms, Coin Change, Coding Interview, Algorithm, Local Optimum, Global Optimum