그리디 알고리즘

그리디 알고리즘이란 최적의 값을 구해야 하는 상황에서 가장 좋은 것부터 고르는 알고리즘입니다.

문제 해결

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

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

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

예를 들어 1,260원을 거슬러줘야 할 때, 총 6(2+2+1+1)개의 동전으로 거슬러 줄 수 있습니다.

코드

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

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

정당성 분석

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

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

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