[Algorithm] 12 강 : 그리디 알고리즘 개요(탐욕법)

그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것 만 고르는 방법 그리디 해법은 그 정당성 분석이 중요 - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요 여기서 최적의 해는 가장 큰값인 21 이다. 하지만 그리디 해는 현재노드(현재 상황) 에서 가장 큰 값을 거치는 것을 의미한다. 그래서 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 예시) 거스름돈 문제 이 상황에서 예를들어 거스름돈이 1260이라고 가정한다. 여기서 카운터에서 손님에게 거스러줄 동전의 최소의 개수는 동전이 가장 큰 값부터 주면된다. 500 원 * 2 / 100원*2 / 50원 * 1 / 10원 * 1 이렇게가 된다. 현재 상황에서 큰 금액에..