Greedy

개념:

매 순간 최적의 해라고 생각되는 것을 선택해 나아가며, 최종적인 해답에 도달한다!

쉽게 말해 나무만 보고 숲을 보지 못하는 것

조건이 있습니다

• 앞의 선택이 이후의 선택에 영향을 주지 말 것!
• 문제에 대한 최적해가 부분문제에 대해서도 최적해일 것!

★삽화 예시

마리오가 leaf 노드까지 가는데 가장 큰 값을 구하려면?

마리오가 모험을 시작했습니다

가장 첫번째 길목에서 슈퍼 나뭇잎이 4점이라 저걸 바로 택했습니다

슈퍼 나뭇잎을 택한 상황에서 그다음 제일 좋은 것을 비교해보니 불꽃이 최적의 해 입니다

탐욕 알고리즘의 한계

• 반드시 최적을 해를 구할 수는 없다.
• 최적의 해에 가까운 것을 구하는 방법 중 하나라 근사치 추정에 활용은 된다.

이 경우에는 마리오가 버섯(2점) → 별(5점)으로 가는게 전체 최적해가 됩니다!

참고

https://babbab2.tistory.com/108

https://ko.wikipedia.org/wiki/탐욕_알고리즘