[그리디] 알고리즘 - 그리디 (Greedy) :탐욕법

그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 

탐욕법이라고도 불리는데 이름에서 알 수 있듯이 단순 무식하게, 탐욕적(현재 상황에서 지금 당장 좋은 것만 고르는 것)으로 문제를 해결하는 알고리즘이다. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

대체로 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘 적용 조건

1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택이 영향을 주지 않는다.
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

그리디(탐욕) 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점이 있다. 이 장점으로 인해 근사 알고리즘으로 사용할 수 있다.

 

EX) 거스름돈

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

 

해설. 이 문제는 그리디 알고리즘을 이용해 해결할 수 있는 가장 대표적인 문제로 간단한 아이디어로 문제를 해결할 수 있다. 그 아이디어는 바로 가장 큰 화폐 단위부터 돈을 거슬러 주는 것 이다. 가장 먼저 500원 동전으로 최대로 거슬러 준후 100원, 50원 10원 순으로 차례로 거슬러 주는 것이 동전의 개수가 최소가 된다.

 

코드

N = 1260 # 거슬러 줘야할 돈
count = 0 # 거슬러 줘야 할 동전의 개수

coin_types = [500, 100, 50, 10]

for coin in coind_types:
	count += N // coin  # 해당 동전으로 거슬러 줄 수있는 최대 개수 
    N %= coin 			# 거슬러 준 후 나머지 저장

print(count)

 

시간 복잡도. 

화폐의 종류만큼 반복을 수행해야 하므로 화폐의 종류가 K개라고 할때 시간 복잡도는 O(K)가 된다.

---

 

주의할점

그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없는 가능성이 있다. 위의 예시와 같이 거스름돈은 항상 큰 화폐부터 거슬러 주는 것이 최적의 해가 보장이 될때 그리디 알고리즘이 효과적이다.

그리디 알고리즘을 사용했을 때에는 그 해법이 정당한지 검토해야한다. 만약 동전의 단위가 배수 형태가 아니라 무작위로 주어진다면 그리디 알고리즘으로 해결할 수 없다. 이때는 다이나믹 프로그래밍으로 해결할 수 있다.

 

 

코딩 테스트 문제에서 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보아야한다. 만약 그리디 알고리즘으로 해결할 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘을 이용하여 해결할 수 있는지도 확인해 보아야 한다.