탐욕 알고리즘(Greedy Algorithm)이란?

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 문제를 해결과는 과정에서 결정(decsion) or 선택의 순간이 오면 그 순간만큼은 가장 최적의 답을 선택하여 최선의 결과를 만들어 내자라는 컨셉을 가지고 있는 알고리즘이다. 

예를들어, A를 출발하여 B 경유지를 거처 목적지 C로 갈때 ( A -> B - > C) A->B 로 갈때 선택 할 수 있는경로가 3개가 있고 B->C 는 4개의 경로가 경로가 있다고 하면 A->B 로 갈수 있는 경로 3개중 1나를 선택한다면 가장 짧은 경로를 선택하고 B->C 로 갈때도 가장 빨리 갈수 있는 경로를 선택해서 최종적으로 A->C로 갈때 가장 빨리 갈수 있는 길을 찾아낼수 있다. 

매 선택의 순간마다 항상 최소, 최대 또는 가장 최선의 답만 선택하려 하기 때문에 욕심이 많다 해서 욕심쟁이 알고리즘이라고도 부른다. 그리디 알고리즘의 단점은 항상  100% 최적해를 보장해주지 않는다. 다만, 어느정도 적합한 수준의 해답을 알려준다.
매 순간 최선의 답만 선택해 나가면 최종적으로 최적해가 나올가능성이 큰 것 뿐이지 100%정확하다는 의미가 아니라는 말이다.

 

예를들어, 공항에서 티켓팅을 하거나 짐을 붙이려고 할 때 그림1 처럼 줄을 선다면 보통 우리는 가장 짧은 줄 뒤에가서 서는게 일반적이다. 근데 가장 짧은 줄을 선택하여 기다리는 중인데 다른 줄이 생각했던것보다 빨리 줄어들어 속으로 아 저쪽 줄에 설껄 하면서 후회했던 경험들이 있을거라 생각한다.
즉, 어느 줄에 서야할까 선택의 갈림길에서 그리디 알고리즘을 통해 가장 짧은 줄을 선택하였지만 문제는 내가 선 줄을 담당하는 직원의 업무처리가 늦어 다른줄이 더 빨라진다면 우리가 원하던 결과는 아닐갓이다.

 

그림1. 공항

[출처] https://www.alamy.com/stock-photo-people-waiting-in-line-to-check-in-at-airport-lanzarote-canary-islands-56464438.html 

그래도 매 선택의 순간마다 최적의 해만 찾아 간다면 결과적으로는 좋은 결과가 있을 확률이 높을수 있다. 

그리디 알고리즘 문제들이 어떤것들이 있는지 하나씩 살펴보면서 알고리즘의 특성을 이해해보도록 하자.

 

Standard Greedy Algorithms :

1. 활동선택문제(Activity Selection Problem)
2. 이집트 분수(Egyptian Fraction)
3. 데드라인 스케줄링(Deadline Scheduling) - Job Sequencing Problem
4. 배낭 문제(Knapsack Problem)
5. Coin Change Algorithm(거스름돈 알고리즘)
6. 집합 덮개 문제(Set Cover Problem)
7.