#20. 그리디 알고리즘(Greedy Algorithm), 탐욕 알고리즘

그리디 알고리즘(Greedy Algorithm)

• 최적해를 구하는 데에 사용되는 근사적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달

 

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
• 탐욕스런 선택 조건(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것
• 최적 부분 구조 조건(optimal substructure) : 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것

---

주요 단계

 

• 선택 과정(Selection Procedure) : 현재 상황에서 가장 최선의 후보를 선택 (지금 당시에 가장 최적인 해를 구한 뒤, 이를 부분해 집합에 추가한다.)
• 적절성 검사(Feasibility Check) : 선택한 후보가 답이 될 수 있는지 제약 사항 검사 (새로운 부분해 집합이 적절한지 검사한다.)
• 해답 점검(Solution Check) : 현재까지 선택된 해가 문제의 정답이 되었는지 검사하고 정답이 아니라면 다시 시작

---

References

 

ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] Greedy Algorithm (탐욕 알고리즘)

m.blog.naver.com/qpghnv/221597913108

[알고리즘 설명] 그리디 알고리즘 (탐욕법, Greedy method)