[Algorithm] Greedy(탐욕법)

그리디 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 당장 좋은 것만 고르는 방법' 을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 상황이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이루어 출제되는 경우가 많다. 

 

다음의 예제는 그리디 알고리즘의 대표적인 문제이다. 한 번 살펴보자!

 

 

# 문제: 당신은 음식은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

이 문제는 간단한 아이디어만 떠올리면 해결할 수 있는 문제이다. 그것은 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그 다음 100원, 50원, 10원짜리 동전을 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다. 이 아디이어를 이용하여 코드를 작성해보면 다음과 같다. 거스름돈이 1260원일 경우다.

 

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin
    n %= coin

print(count)

 

코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 K개라고 할 때 위 소스 코드의 시간 복잡도는 O(K)이다. 이 정도면 준수한 크기의 복잡도이다.