Chap 4. 그리디 알고리즘

그리디 알고리즘 

그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘"

    최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제

• 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림
• 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택<가장 좋은 데이터를 선택>
• 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함

       전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함

 

그리디 알고리즘 방법 

= 근시안적인 선택으로 부분적인 최적해<국소적인 해>를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다.

 

[특징]

(1) 한 번 선택하면 번복하지 않는다.

 

한 번 최선의 방법을 선택에서 나중에 봤을 때 별로라고 뒤로 다시 가는 것이 아니다.

그리디 알고리즘은 “정답을 찾는다”가 아니라 “정답에 가까운 답”을 찾는 것이다.

*물론, 문제 중에 그리디 알고리즘을 사용하면 항상 정답을 찾는다는 것을 증명된 문제가 있지만 그렇지 않은 문제들도 있다.

 

⇒ 이러한 특성 때문에 대부분의 그리디 알고리즘들은 매우 단순(각 시점에서 가장 좋은 답을 선택하면 되니)하며, 또한 제한적인 문제만이 그리디 알고리즘으로 해결된다.

많은 근사 알고리즘들이 그리디 알고리즘을 이용하여 해결된다.