그리디 알고리즘

그리디 알고리즘이란

최적의 값을 구해야 하는 상황에서 가장 좋은 것부터 고르는 알고리즘입니다.
알고리즘은 간단하지만, 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 답이 나오는 문제인지 파악하는 정당성 분석을 잘하는 것이 중요합니다.

---

문제 해결

그리디 알고리즘의 대표적인 문제인 거스름돈을 풀어봅시다.

💰 거스름돈

카운터에는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재합니다.
손님에게 거슬러 주어야 할 돈이 N원일 때,
거슬러 주어야 할 동전의 최소 개수를 구하세요.
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.)

최소 개수(최적의 답)를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됩니다.

예를 들어 1,260원을 거슬러줘야 할 때,

동전	개수	남은 돈
-	-	1260원
500원	2	260원
100원	2	60원
50원	1	10원
10원	1	0원

총 6(2+2+1+1)개의 동전으로 거슬러 줄 수 있습니다.

코드

# python
N = int(input())
ans = 0
for coin in [500, 100, 50, 10]:
  ans += N // coin
  N %= coin
print(ans) # 6

---

// javascript
function solution(N) {
  let ans = 0;
  for (let coin of [500, 100, 50, 10]) {
    ans += Math.floor(N / coin);
    N %= coin;
  }
  return ans;
}

정당성 분석

이 문제에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 가지고 있는 각 동전들(500, 100, 50, 10) 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.

만약 가지고 있는 동전이 500원, 400원, 100원일 경우, 그리디는 최적의 해를 보장할 수 없습니다. 반례로 800원을 거슬러 주어야 한다면, 그리디를 사용하는 경우 4개(500원 x 1 + 100원 x 3)이지만 최솟값은 2개(400원 x 2)입니다.