[이코테] 그리디 알고리즘
매 순간마다 가장 최적의 답을 선택하여 최종의 답을 도출하는 방법 매 순간의 최적해가 문제에 대한 최적해이다. 한번의 선택이 다음 선택에는 무관하다. 문제를 해결하기 위한 아이디어를 직관적으로 찾고 그 아이디어의 정당성을 검토할 수 있어야 한다. 1. 거스름 돈 문제 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하기 (단, 거슬러 줘야 할 돈 N은 항상 10의 배수) 해결 방안 가장 큰 단위부터 돈을 거슬러 준다. why? 큰 단위가 항상 작은 단위의 배수이다! 500원을 각각 100원 5개, 50원 10개, 10원 50개 400원 동전이 있다면 800원을 거슬러 주는데 문제가..
알고리즘/그리디
2020. 10. 8. 00:12