[2026] Greedy Algorithm | Best Choice Every Step Complete Guide

· 18분 읽기 · 수정 Intermediate Tutorial
[2026] Greedy Algorithm | Best Choice Every Step Complete Guide

이 글의 핵심

Greedy algorithms make the locally optimal choice at each step. When conditions are met, they efficiently find the optimal solution. Learn application conditions, representative problems, risks of using without proof, and coding interview…

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. 아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

FeatureGreedyDP
SelectionCurrent bestAll cases
Time ComplexityO(n log n)O(n²) ~ O(2ⁿ)
Optimal GuaranteeX (proof needed)O
ImplementationSimpleComplex

2. Representative Problems

Problem 1: Meeting Rooms

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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? 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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 meetings

Problem 2: Coin Change

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

"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 optimal

When Greedy Fails

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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 ones

4. Practical Problems

Problem 1: Gym Clothes (Programmers)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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]))  # 5

Problem 2: Joystick (Programmers)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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"))  # 56

5. Common Greedy Patterns

Pattern 1: Sorting + Selection

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))  # 1

Practical Tips

Identifying Greedy Problems

아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# ✅ 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

아래 코드는 python를 사용한 구현 예제입니다. 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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 greedy

Summary

Key Points

  1. Greedy: Best choice every step, O(n log n)
  2. Proof Required: Check for counterexamples
  3. Sorting: Most problems require sorting first
  4. Compare with DP: Greedy is faster but not always optimal

Problem Identification

SignalGreedyDP
SelectionCurrent bestAll cases
TimeO(n log n)O(n²)
ProofRequiredNot required
ExampleMeeting roomsKnapsack

Baekjoon

LeetCode

  • LeetCode 455: Assign Cookies
  • LeetCode 435: Non-overlapping Intervals
  • LeetCode 402: Remove K Digits
  • LeetCode 621: Task Scheduler

Programmers

Keywords

Greedy Algorithm, Greedy, Optimization, Sorting, Meeting Rooms, Coin Change, Coding Interview, Algorithm, Local Optimum, Global Optimum

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3