그리디 알고리즘이란 ? 주어진 상황에서 가장 좋은것(큰 값)을 구하는 알고리즘이다. 단순히 가장 좋은것을 선택하는 행위를 반복하여도 최적의 값이 추출되는지 검증이 필요하다. 1. 해결 아이디어 제시 거스름돈으로 사용할 화폐단위를 정의한다. 가장 적은 개수를 구하는 문제이기에 화폐단위중 가장 큰 값으로 거슬러 줄수 있는 개수를 구한다. 그다음으로 적은 금액으로 거슬러 줄 수 있는 개수를 구한다. 해당 작업을 반복한다. 2. 정당성 분석 해당 문제는 거슬러 주어야할 최소 동전 개수를 구하는 문제 이기에, 화폐의 가장큰 단위로 거슬러 준다면 , 거스름돈의 개수를 최소화할 수 있다. 예 : 거스름돈 1,000 일 경우 500 * 2 100 * 10 50 * 20 10 * 100 이기에 가장큰 화폐단위인 500원..