거스름돈

Chapter 3. 그리디

그리디개념 정리그리디 알고리즘현재 상황에서 지금 당장 좋은 것만 고르는 방법매 순간 가장 좋은 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 문제 유형다른 알고리즘에 비해 "사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형"다익스트라 알고리즘 (최단 경로)과 같은 특이 케이스를 제외하고는 암기로 대처하기가 어려움보통 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구예제 : 거스름돈문제당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할..