| 이 항목은 욕심쟁이 알고리즘, 탐욕 알고리즘으로도 들어오실 수 있습니다. |
1 그리디 알고리즘이란?
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.
예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.[1] 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.
단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.
그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.
2 어떤 경우에 잘 동작하는가
그리디 알고리즘은
- greedy choice property
- optimal substructure
특성을 가지는 문제들을 해결하는데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다. [2]
3 근사 알고리즘
상기했다시피 그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기때문에 실용적으로 사용이 가능하다. 허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다. 또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.[3]
4 사용되는 예시
- AI에 있어서 결정 트리 학습법(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제[4]
- 최소 신장 트리 (Minimum spanning tree)
- 제약조건이 많은 대부분의 문제 [5]
- 다익스트라 알고리즘
- 허프만 코딩
- 크루스칼 알고리즘
5 최적값을 구하는데 실패하는 문제들
- 외판원 순회 문제 (traveling salesperson problem)
- ↑ 이는 일반적으로 외판원 순회 문제 (Traveling Salseman Problem, TSP)로 알려져 있다.
- ↑ 예를 들어서 상기 교차로 문제는 도로가 어떻게 생겼는지에 따라서 다음 선택에 영향이 가며, 만일 두 수가 매 턴에 주어지고 종료시에 모든 선택된 수의 합이 최대로 하고자 하면 그냥 매 단계에서 두 숫자중 큰 숫자를 고르면 매 순간의 최적해의 set이 최종적으로 문제의 최적해라고 볼 수 있다는 의미이다
- ↑ 가지치기
- ↑ 단, 동전들에 배수관계가 성립할때만 한정. 대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.
- ↑ 항상 그런것은 아니지만, 프로그래밍 문제를 풀 때 제약조건이 많다면 대부분 그리디로 풀리는 경우가 많다. 다만 그리디인줄 알고 풀었다가 피보는 경우도 있다.