출처: 이것이 취업을 위한 코딩테스트다 with 파이썬
그리디 알고리즘은 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
그리디 알고리즘의 정당성
대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있음
바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민 후에도 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민
ex) 거스름돈
1.
화폐단위: 500, 100, 50, 10
→ 가장 큰 단위가 가장 작은 단위의 배수 형태이므로
그리디 알고리즘이 가능
2.
화폐단위가 무작위면 불가능
