알고리즘 (1) 썸네일형 리스트형 그리디 & 구현 그리디 단순히 매 상황에서 가장 큰 값만 고르는 방법 => 최적의 해를 보장할 수 없을 때가 많음 단, 코딩테스트에서 그리디(탐욕법)으로 분류되는 경우에는 최적의 해를 보장하는 경우로 추정함 문제 1 당신이 점원이고 카운터에 500, 100, 50, 10 원 짜리 동전이 무한할 때, 손님에게 거슬러 주어야 할 돈 N원을 거슬러 주어야 할 동전의 최소개수를 구하시오. 단, 거슬러 줘야 할 N원은 항상 10의 배수. 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위 부터 거슬러 줄 수 있을 만큼 거슬러 준다. 가장먼저 500원을 거슬러 줄 수 있을만큼, 그다음 100, 50, 10 원 순서대로 거슬러 준다. 정당성 분석 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 .. 이전 1 다음