[이코테] Chapter03 - 그리디

이글은 `이것이 취업을 위한 코딩 테스트다 with 파이썬` 을 읽고 공부하며 적는 글 입니다. 그리디 알고리즘 그리디 알고리즘은 탐욕적 알고리즘 이라고 하며, 단순하지만 강력한 문제 해결 방법입니다. 즉, 그리디 알고리즘은 `현재 상황에서 지금 당장 좋은 것만 고르는 방법`을 의미합니다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 예제 3-1. 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 도전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 문제 해설 1370원을 거슬러 줘야 한다고 생각해봅시다. 우리는 늘 그리디 알고리즘에 따라 살아왔을지도 모르겠습니다. 당연하게도 500원 2개, 100원 3개,...

원문링크 : [이코테] Chapter03 - 그리디