분류 전체보기

[이코테] 그리디 알고리즘

그리디 알고리즘 (탐욕법) 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시함 [ 예제 3-1 ] 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10배수이다. 문제 접근 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이 아이디어의 핵심 예를 들어 N원을 거슬러 준다고 할 때, 500원으로..