[알고리즘] 그리디(Greedy) 알고리즘 (탐욕 알고리즘)

개념 그리디 알고리즘은 욕심쟁이 방법이라고도 불리는데, 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 원리를 가진 알고리즘 설계 기법이다. 이는 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하며, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 그러나 가장 좋은 결과를 얻는 것이 보장된 것은 아님 이러한 알고리즘을 사용한 것에는 프림 알고리즘, 다익스트라 알고리즘 등이 있음. 과정 가장 최적의 해는 초록색 라인을 따라가서 얻는 107이지만, 그리디 알고리즘을 통..........