[자료구조] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘이란?

그리디(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 그리디 알고리즘은 우리말로 욕심쟁이 알고리즘이라고 하는데 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 

 

그리디 알고리즘의 대표적인 예로 거스름돈 문제로 설명하겠다.

 

거스름돈

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

문제 해설

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 그것은 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. N원을 거슬러 줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

n = 1260 # 손님에게 거슬러줘야 할 거스름돈
count = 0

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

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

print(count)

 

 

그리디 알고리즘이 정당성을 만족하기 위한 조건

• 탐욕적 선택 속성(Greedy Choice Property): 이전의 선택이 현재 선택에 영향을 끼치지 않는다.
• 최적 부분 구조(Optimal Substructure): 최종 해는 각 부분 문제에 대한 최적의 해로 구성된다.

 

예를 들어 아래와 같은 그래프가 있을 때, 그리디 알고리즘으로 root node에서 leaf node까지 노드번호의 합의 최솟값을 구한다고 하자. 그리디 알고리즘은 매 선택지에서 최선의 선택을 하기 때문에 1->4->13으로 총 18이 된다.

하지만 전체로 보면 1->10->3 총 15가 최솟값이 된다. 최종해가 최적 해가 아닐 수 있다.

따라서 그리디 알고리즘을 적용해도 (매 선택시 최선의 선택지만 고를 때)  최종 해가 최적의 해가 될 수 있는지 확인하는 정당성 분석이 필요하다.