각 단계에서 국소 최적해를 찾음으로써 전체 문제를 풀 수 있다는 개념이다.
국소 최적해가 문제의 최적해가 아닐 수 있다.
따라서 문제 자체가 국소 최적해와 문제의 최적해가 일치하는 문제로 나오기 때문에
판단 잘해서 사용해야한다.
그리디 알고리즘이 그저 허울 좋은 망상이라고 생각 할 수 있겠지만, 그리디 알고리즘은 다른 복잡하지만 최적해를 뽑아내는 다른 알고리즘들에 비해 비교적 비용이 저렴한 경우가 많습니다.
가장 유명한 개념 동전 바꾸기 개념
최소한의 동전 개수로 주어진 가격을 만들어라!
10원, 100원, 500원 ⇒ 그리디 가능
10원, 30원, 40원, 50원 ⇒ 그리디 불가능 ⇒ DP로 풀자!
70원 국소 최적해 50 - 1개 10 - 2개 ⇒ 3개 / 문제 최적해 40 - 1개, 30 - 1개 ⇒ 2개
LeetCode