Greedy1 Greedy Algorithm (그리디 알고리즘) 현재 사황에서 지금 당장 좋은 것만 고르는 방법 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다. 1. Example. 거스름돈 (1) 문제 거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소의 개수를 구하여라. (2) 문제 해설 그리디 알고리즘을 이용해 풀어 보자. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다. 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다. (3) 소스 코드 publi.. 2021. 11. 5. 이전 1 다음 반응형
