그리디 알고리즘

Greedy Algorithm은 욕심쟁이 알고리즘이라고도 하며
매 순간 최선의 선택이 전체 문제의 최선을 선택일 확률이 높다는 가정으로 접근법이다.

한계

그리디 알고리즘의 한계는 '매 순간 최선의 선택이 항상 최선의 결과를 보장하지 않는다는 점이다.'

마시멜로 실험에 비유를 하자면 지금 먹지 않고 참으면 10분 뒤에 마시멜로를 2개를 준다면
그리디 알고리즘 관점에서 매 순간 최선의 선택은 '바로 마시멜로 1개를 먹는 것이다.'
하지만 참으면 결과적으로 2개를 얻게 되므로 매 순간 최선의 선택이 최선의 결과를 불러오지는 못한다.

하지만 그럼에도 그리디 알고리즘은 매 순간 최선의 선택이 어느정도 최적화된 결과를 보장한다는 전제로
문제에 접근하는 풀이법이다.