Greedy

개요

---

그리디 알고리즘은 매 선택에서 현재 당장 최적인 답을 선택하여 적합한 결과를 도출하도록 한다. 다시 말해 현재 조건에서 최적의 선택을 했다면 더 이상 다른 가능 케이스는 검증하지 않는 것이다. 그 결과 그리디 알고리즘은 전체에서 최적값을 보장할 수 없다.

그럼에도 불구하고 그리디 알고리즘은 처리 속도가 매우 빠르기 때문에 특정 조건을 만족할 경우 자주 사용될 수 있다.

 

최적의 해를 보장하는 조건

---

탐욕 선택 속성(Greedy Choice Property)

• 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다.

최적 부분 구조(Optimal Substructure)

• 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다.