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