[알고리즘] 탐욕 알고리즘, Greedy Algorithm

탐욕 알고리즘이란?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
탐욕 알고리즘은 선택의 순간에, 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라고 보장할 수 없다.
탐욕 알고리즘을 적용할 수 있는 문제는,
순간의 최선이 전체의 최선으로 이어지는 구조를 가진 문제이다.

대표 문제

문제

미국 동전을 사용하여 n센트의 거스름돈을 주는 알고리즘을 설계하라.
사용할 수 있는 동전은 다음과 같다:
쿼터 (quarter, 25센트) / 다임 (dime, 10센트)
니켈 (nickel, 5센트) / 페니 (penny, 1센트)
이때 동전의 총 개수를 최소화하는 방식으로 거스름돈을 만들어야 한다.

해결

예를 들어, 67센트를 만드는 경우를 생각해보자.
먼저 25센트짜리 동전을 하나 선택하면 42센트가 남는다.
또 하나의 25센트를 선택하면 17센트가 남고,
10센트를 선택하면 7센트가 남는다.
5센트를 선택하면 2센트가 남는다.
1센트를 선택하면 1센트가 남고,
마지막으로 1센트를 한 번 더 선택하면 끝난다.
👉 이처럼 총 6개의 동전으로 67센트를 거슬러 줄 수 있다.

이 문제는 왜 탐욕 알고리즘일까?

탐욕 알고리즘(Greedy Algorithm)은
"각 단계에서 가장 최적처럼 보이는 선택"을 반복하여 전체 해답에 도달하는 방식이다.
이 문제에서도 우리는 매 순간 남은 금액에서 가장 큰 동전부터 차례대로 선택하고 있다.
즉, "지금 당장 가장 좋은 선택"을 반복하는 방식이기 때문에
탐욕 알고리즘의 대표적인 구조를 따르고 있다.

이 문제에서 탐욕이 잘 작동하는 이유

미국 동전 체계(25, 10, 5, 1)는 다음 두 가지 조건을 만족한다:
탐욕적 선택 속성 (Greedy-Choice Property)
→ 매 순간의 최선의 선택이 결국 전체적으로도 최선이 됨
최적 부분 구조 (Optimal Substructure)
→ 전체 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있음
즉, 큰 동전부터 고르는 방식이 전체적으로도 항상 동전 개수를 최소화하는 방법이 되는 구조라서,
이 문제에서는 탐욕 알고리즘이 정확히 작동한다.

⚠️ 하지만 항상 통하는 건 아니다!

탐욕 알고리즘은 모든 문제에서 반드시 최적해를 보장하지는 않는다.
예를 들어, 동전 단위가 {1, 3, 4}이고 6센트를 만들고 싶을 때:
탐욕 알고리즘: 4 + 1 + 1 → 총 3개
최적 해답: 3 + 3 → 총 2개 ❗
→ 이처럼 그 순간의 최선의 선택이 전체적으로는 최악의 선택이 되는 경우도 존재한다.

수도코드

Python

cents = 67
q_count = 0 # q : quater = 25
d_count = 0 # d : dime = 10
n_count = 0 # n : nickel = 5
p_count = 0 # p : penny = 1
tmp = 0

q_count = cents // 25
tmp = cents- 25*q_count

d_count = tmp // 10
tmp = tmp - 10*d_count

n_count = tmp // 5
tmp = tmp - 5*n_count

p_count = tmp // 1
tmp = tmp - 1*p_count

print(q_count, d_count, n_count, p_count)

출력

2 1 1 2

---

What is a Greedy Algorithm?

"Greedy" means taking what seems best or most desirable in the moment.
A greedy algorithm is one that makes the best-looking choice at each step, aiming to reach a final solution by choosing what's locally optimal at every decision point.
It is an approximation method used to find optimal solutions in some cases.
It proceeds by always choosing what seems optimal at the moment, hoping that these local decisions will lead to the global optimum.
However, the choice made at each step—though locally optimal—does not guarantee that the final result will be globally optimal.
A greedy algorithm works only for problems where
making the best local choice always leads to the best global solution.

Representative Problem

Problem

Design an algorithm that makes change for n cents using U.S. coins.
Available coin types are:
Quarter (25¢), Dime (10¢),
Nickel (5¢), Penny (1¢).
The goal is to minimize the total number of coins used.

Solution

Let’s take 67 cents as an example.
Start with one 25¢ coin → 42 cents left.
Take another 25¢ coin → 17 cents left.
Take a 10¢ coin → 7 cents left.
Take a 5¢ coin → 2 cents left.
Take a 1¢ coin → 1 cent left.
Take one more 1¢ coin → Done!
In total, 6 coins are used to make change for 67 cents.

Why is this a Greedy Algorithm?

A greedy algorithm works by
making the best-looking choice at each step without reconsidering previous decisions.
In this case, we are always choosing the largest coin possible at each step,
based on the remaining amount.
This behavior follows the classic greedy strategy

Why does Greedy work well here?

The U.S. coin system (25, 10, 5, 1) satisfies two key properties:

• Greedy-Choice Property
  → The best local choice leads to the best global outcome.
• Optimal Substructure
  → An optimal solution to the problem contains optimal solutions to subproblems.
  Thus, the strategy of picking the largest coin first always results in the minimal number of coins,
  and greedy gives the correct answer here.

⚠️ But it doesn’t always work!

Greedy algorithms don’t guarantee optimal solutions in all cases.
For example, with coin denominations {1, 3, 4} and a goal of 6 cents:

• Greedy: 4 + 1 + 1 → 3 coins
• Optimal: 3 + 3 → only 2 coins ❗
  → This shows that the locally best choice can sometimes lead to a worse overall result.

Pseudocode

Python

cents = 67
q_count = 0 # q : quater = 25
d_count = 0 # d : dime = 10
n_count = 0 # n : nickel = 5
p_count = 0 # p : penny = 1
tmp = 0

q_count = cents // 25
tmp = cents- 25*q_count

d_count = tmp // 10
tmp = tmp - 10*d_count

n_count = tmp // 5
tmp = tmp - 5*n_count

p_count = tmp // 1
tmp = tmp - 1*p_count

print(q_count, d_count, n_count, p_count)