1. 개요
그리디 알고리즘(greedy algorithm) 이라고도 하며, 지금 이 순간 당장 선택할 수 있는 최적의 답을 찾기 위한 알고리즘이다. 즉, 주어진 문제에 대한 근본적인 최적의 해를 찾는 게 아닌, 그 근사치를 찾기 위한 알고리즘이라고 할 수 있다.
2. 특징
그리디 알고리즘은, 아래와 같은 특성을 가진 문제를 해결할 때 강점이 있다.
2.1. 탐욕스러운 선택 조건 (Greedy Choice Property)
앞에서 선택한 것이 이후의 선택에 영향을 주지 말아야 한다.
알고리즘 특성상, 앞에서 선택한 것이 이후의 선택에 영향을 줘야하는 경우가 있는데, 그런 경우에는 적합하지 않다는 뜻이다. (대표적인 예: 외판원 순회 문제)
2.2. 최적 부분 구조 조건 (Optimal Substructure)
주어진 문제에 대한 최적해는 부분 문제에 대한 최적해로 구성된다.
부분 문제에 대한 최적해로 구성된다. 라는 어휘 때문에 조금 어렵게 느껴졌는데, 여러 문서를 찾아 보니 별거 없더라.
- 주어진 문제를 적절한 범위로 쪼갠다. (주어진 문제를 적절하게 쪼갠 것 = 부분 문제)
- 부분 문제별로, 최적의 해를 구한다. (개별 부분 문제에 대한 최적해를 구한다.)
- 쪼갠 범위별 최적 답안을 모아, 하나의 답안으로 조합한다. (여러개로 나누어진 부분 문제에 대한 최적해를 모아, 하나로
구성한다.) - 짜잔! 주어진 문제에 대한 최적 해 완성!
- 주어진 문제 : 부분 문제 여러개로
구성된 문제. - 주어진 문제의 최적 해: 부분 문제의 최적해 여러개 개를 하나로 모은(=구성한) 것.
- 주어진 문제 : 부분 문제 여러개로
결론적으로, 내가 구성하다 라는 단어와 친하지 않아 발생한 참사였다. 본의아니게 장황한 글이 되었지만, 나의 부족한 어휘력을 반성하는 계기로 삼기 위해 기록코자 한다.
3. 예시
3.1. 탐욕 알고리즘으로 최적 해를 도출하는 데 성공한 경우
서울에서 대전과 동대구를 거쳐 부산까지 가는, 최대한 빨리 갈 수 있는 경로를 찾는다고 가정하자. 단, 각 지역에서 정차 혹은 환승하는 시간은 고려치 아니한다.
- GREEDY : KTX(59분) → KTX(49분) → KTX(46분) [합계: 2시간 34분]
- BEST : KTX(59분) → KTX(49분) → KTX(46분) [합계: 2시간 34분]
- WORST : 무궁화(2시간 5분) → 무궁화(1시간 58분) → 무궁화(1시간 29분) [합계: 5시간 32분]
너무 뻔한 걸 예시랍치고 가져와서 민망하지만, 탐욕 알고리즘이 효과를 발휘할 수 있는 예시 중 하나라고 볼 수 있다.
3.2. 탐욕 알고리즘으로 이상적인 최적 해를 도출해내지 못한 경우
주어진 트리를 위에서 아래로 순회하며 선택해나간 값의 합계를 내야한다고 가정하자. 단, 조건은 다음과 같다.
- 합계를 낸 값이 크면 클 수록 좋다.
- 탐욕 알고리즘은, 이미 지나친 노드와 앞으로 선택해야 할 노드의 값은 생각치 않으며, 당장 눈 앞에 선택해야 할 노드 중 가장 큰 값을 선택하며 앞으로 나아가야 한다.
알고리즘의 공정한 평가를 위해, 트리를 다섯개정도 만들어서 검증해보도록 하자.
3.2.1. 첫번째
- GREEDY : 11 → 24 → 84 [합계: 119]
- BEST : 10 → 34 → 100 [합계: 134]
- WORST : 10 → 23 → 53 [합계: 88]
3.2.2. 두번째
- GREEDY : 15 → 34 → 70 [합계: 134]
- BEST : 15 → 32 → 95 [합계: 142]
- WORST : 2 → 26 → 50 [합계: 78]
3.2.3. 세번째
- GREEDY : 18 → 24 → 85 [합계: 127]
- BEST : 18 → 19 → 96 [합계: 133]
- WORST : 10 → 21 → 26 [합계: 57]
3.2.4. 네번째
- GREEDY : 16 → 52 → 62 [합계: 130]
- BEST : 8 → 51 → 77 [합계: 136]
- WORST : 16 → 31 → 64 [합계: 111]
3.2.5. 다섯번째
- GREEDY : 20 → 31 → 85 [합계: 130]
- BEST : 20 → 27 → 97 [합계: 144]
- WORST : 11 → 23 → 60 [합계: 94]
3.2.6. 평가
총 다섯개의 트리를 통해 검증해본 결과를 종합해보면 다음과 같다.
| 차수 | greedy | Best | Best값 기준 상대오차 |
|---|---|---|---|
| 첫번째 | 119 | 134 | 11.19% |
| 두번째 | 134 | 142 | 4.93% |
| 세번째 | 127 | 133 | 4.51% |
| 네번째 | 130 | 136 | 4.41% |
| 다섯번째 | 130 | 144 | 9.72% |
평균 상대오차율 : 6.95%
이번 예시는, 외판원 순회 문제 처럼 모든 케이스를 다 순회해보아야 정확한 값을 알 수 있는 상황이었으므로, 탐욕 알고리즘을 사용할 시 정확한 답을 얻어낼 가능성이 낮은 편이었다.
예상대로, 탐욕 알고리즘으로 도출해낸 결과값은 모든 케이스를 순회하며 구해낸 정확한 값 대비, 평균 6.95% 정도의 오차가 발생하였음을 알 수 있다.
다만, 탐욕 알고리즘은 모든 케이스를 순회하며 값을 도출한 게 아닌, 단순 양자택일을 진행하며 도출해낸 값임을 알아둘 필요가 있다. 즉, 노력을 아낀 것 치고는 꽤 선방한 결과라 볼 수 있으며, 이런 특성 덕분에 근사치를 알아내기 위한 알고리즘으로서는 여전히 가치가 있다고 볼 수 있다.
덧: 예시로 주어진 트리를 정렬 한 후에 탐욕 알고리즘을 실행시켰다면, 결과는 달라졌을 수도 있겠다는 생각이 들었다.
4. 관련 알고리즘
- 프림(Prim) 알고리즘
- 크루스칼 (Kruskal) 알고리즘
- 다익스트라(Dijkstra) 알고리즘
- 허프만 코드 (huffman code) 알고리즘