그리디 알고리즘

그리디(greedy) 알고리즘은 단어 그대로 탐욕법이라고도 한다.

단순하면서도 강력한 알고리즘으로 반드시 알아야 하는 알고리즘 중 하나이다. 

그리디 알고리즘은 뜻 그대로 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 

 

그리디 알고리즘은 최적화 문제를 대상을 하고 그리디 알고리즘은 그 문제를 해결하기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 

즉, 특정한 문제를 직면했을 때, 단순히 현재 상황에서 최적으로 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야 한다. 

 

또한, 그리디 알고리즘 문제는 정렬 알고리즘과 자주 짝을 이룬다. 정렬을 한 상태에서 기준을 만족시키는 경우가 많기 때문이다.

---

 

그리디 알고리즘에 대표적인 예시로 '거스름 돈' 문제를 이용해 그리디 알고리즘을 설명해 보겠다.

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

 

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다.

 

N=int(input())
count = 0

# 큰 단위의 화폐부터 차례로 확인.
coin_types = [500 , 100, 50, 10]

for coin in coin_types:
	count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= coin
    
print(count)

 

화폐의 종류가 K라고 할 때 이 코드의 시간 복잡도는 O(K) 이다. 

 

하지만 대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 정답을 도출할 수 있다.

 

그리디 알고리즘의 핵심은 늘 '최적해'를 구하는 것이다.