탐욕 알고리즘(Greedy Algorithm)

그리디 알고리즘, 욕심쟁이 알고리즘이라고도 부른다.

 

탐욕 알고리즘은 최적해를 구하는 알고리즘으로, 매 순간순간마다 최적의 방식을 선택하여 최종적인 최적해에 도달한다. 물론 순간순간의 최적의 선택을 했다고 해서 이것이 최종적으로 최적이라고 하지 않는다. 대표적인 예시가 마시멜로 실험이다.

 현재 순간에 마시멜로를 먹는다면, 미래에 마시멜로가 없고 / 현재 순간에 마시멜로를 먹지 않는다면 미래에 마시멜로가 두 개이다. 
 이 때 최적의 마시멜로를 먹을 수 있는 최적해를 찾아야 한다.

라는 문제를 보자. 물론 상식적으로는 현재에 마시멜로를 참고, 미래에 마시멜로를 두 개 먹는 것이 최적이다. 그러나 그리디 알고리즘에서는 현재 하나를 먹는다. 왜냐고? 그리디 알고리즘은 '현재 순간' 에서 최적의 방식을 선택하기 때문에 현재에서 가장 많은 마시멜로를 먹을 수 있는 '마시멜로를 먹는다' 라는 선택지를 선택한다.

따라서, 그리디 알고리즘이 언제나 최적의 선택을 한다고 보장할 순 없는 것이다. 그렇다면, 그리디 알고리즘이 선택한 선택지가 최적해가 되는 조건은 무엇일까?

바로 탐욕스런 선택조건(greedy chioce property)와 최적 부분 구조 조건(optimal substructure)이다.

탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며(이래서 마시멜로 실험이 그리디의 반례로 뽑힌다), 최적 부분 구조 조건은 전체의 알고리즘 최적해가 부분의 알고리즘에서도 최적이라는 것이다.

최적 부분 구조 조건의 예시는 다음과 같다.

김포 공항에서 시카고 공항까지 갑니다(문제이므로 실제 경로가 아닙니다 ㅜㅜㅜ).
김포 공항에서 시카고 공항까지 가려면 반드시 도쿄를 경유해야한다고 합니다.
이 때 한국 - 일본까지 가는 비용은 ㄷㅎ항공은 12만원, ㅈ에어 8만원, ㅌㅇㅇ항공은 7만원입니다.
일본 - 시카고까지 가는 비용은 ㄷㅎ항공 80만원, ㅈ에어 86만원, ㅁㄱ항공이 70만원입니다.
이 때 김포 - 시카고까지 가는 가장 저렴한(최적의) 비용은 얼마입니까?  

이 때 최적비용은 7만원 + 70만원 하여 총 77만원이 가장 최적이다. 이 때, 국소적으로 보아도 한국 - 일본의 비용 7만원 / 일본 - 시카고가 70만원으로 국소적으로 봐도 최적임을 알 수 있다. 이게 최적 부분 구조 조건이다.

 

물론 이 두 가지를 성립하지 않더라도 근사치까지는 최적의 해를 구할 수 있어서 근사 알고리즘으로 쓰인다. 이 때 검증을 필요로 한다. 알고리즘들 중에 속도가 빠르기 때문에 실용적으로 사용되는 알고리즘이다.

 

매트로이트 구조(일차 독립적 구조)에서는 언제나 최적해를 찾는다고 한다.

 

마지막으로 탐욕 알고리즘의 예시를 하나만 더 보자.

마트 알바를 하고 있는데 현금 계산을 하는 사람이 나타났다.
총 1780원을 걸러줘야 하는데, 어떻게 해야 가장 적은 갯수로 걸러줄 수 있나?

극단적으로 10원짜리 178개를 줘버리면 된다. 하지만 그러면 알바가 짤리겠지(?)

1780원 -> 1000원짜리로 걸러줘야지!

780원 -> 500원짜리로 걸러줘야지!

280원 -> 100원짜리 2개로 걸러줘야지!

80원 -> 50원짜리로 걸러줘야지!

30원 -> 10원짜리 3개로 걸러줘야지!

가장 이상적인 방식은 1000원짜리 1개, 500원 1개, 100원 2개, 50원 1개, 10원 3개이다.

매 순간 가장 커다란 화폐의 단위를 탐욕스럽게 고른 결과가 된다.