그리디 #파이썬 #알고리즘1 당장 좋은 것만 선택하는 그리디 그리디 이론 - '탐욕법' - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - '가장 큰 순서대로', '가장 작은 순서대로' 같은 기준을 알게 모르게 제시해준다. - 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다. - 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을때에는 사용할 수 있다. 예제 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. .. 2021. 1. 29. 이전 1 다음