[이코테] 그리디 알고리즘(Greedy Algorithm)
📌 그리디 알고리즘 (탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 최적의 해를 구할 수 있는지 검토하는 과정 필요 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한 해서 출제되는 경우有 ✅ 문제 - 거스름 돈 - 그리디 알고리즘 설명을 위한 문제 예시로 많이 쓰임 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수는? (단, 거슬러 줘야 할 돈 N은 항상 10의 배수) 💡 해결 아이디어 가장 큰 화페 단위부터! 🔎 정당성 분석 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 만약에 800원을 거슬러 주어야 하는데 화폐 ..
코딩테스트/이코테
2021. 3. 22. 02:07
