그리디 알고리즘
그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘"
최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제
- 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림
- 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택<가장 좋은 데이터를 선택>
- 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함
전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함
그리디 알고리즘 방법
= 근시안적인 선택으로 부분적인 최적해<국소적인 해>를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다.
[특징]
(1) 한 번 선택하면 번복하지 않는다.
한 번 최선의 방법을 선택에서 나중에 봤을 때 별로라고 뒤로 다시 가는 것이 아니다.
그리디 알고리즘은 “정답을 찾는다”가 아니라 “정답에 가까운 답”을 찾는 것이다.
*물론, 문제 중에 그리디 알고리즘을 사용하면 항상 정답을 찾는다는 것을 증명된 문제가 있지만 그렇지 않은 문제들도 있다.
⇒ 이러한 특성 때문에 대부분의 그리디 알고리즘들은 매우 단순(각 시점에서 가장 좋은 답을 선택하면 되니)하며, 또한 제한적인 문제만이 그리디 알고리즘으로 해결된다.
많은 근사 알고리즘들이 그리디 알고리즘을 이용하여 해결된다.
'CS > 알고리즘' 카테고리의 다른 글
Chap4-2. 최소 신장 트리 (0) | 2022.04.11 |
---|---|
Chap4-1. 동전 찾기 문제 (0) | 2022.04.11 |
Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) (0) | 2022.04.08 |
Chap3-2 퀵정렬(QuickSort) (0) | 2022.04.05 |
Chap3-1. 합병 정렬(MergeSort) (0) | 2022.04.04 |