그리디 알고리즘(Greedy Algorithm)?

참조

https://ko.wikipedia.org/wiki/탐욕_알고리즘
https://namu.wiki/w/그리디%20알고리즘
https://janghw.tistory.com/entry/알고리즘-Greedy-Algorithm-탐욕-알고리즘

그리디 알고리즘

그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 그것이 최적해라는 보장은 없다.

최적해가 보장되는 경우

탐욕 선택 속성(greedy choice property)과 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다.
한번의 선택이 다음 선택에는 전혀 무관한 값이며 매 순간의 최적해가 문제에 대한 최적해라면 이 알고리즘을 사용하여 도출한 답은 최적해가 보장된다.