알고리즘 이론/탐욕 알고리즘1 탐욕 알고리즘(greedy algorithm) 1. 탐욕 알고리즘이란? - 여러 경우 중 하나를 결정해야 하는 순간마다, 최적의 선택을 진행하여 결과를 구하는 기법 - 특정 순간에 전체 조합(예, 전체 동전의 조합)을 고려하지 않고 그 순간의 최적의 선택을 시행한다 2. 탐욕 알고리즘의 문제 1. 최소 동전 개수 구하기 - 주어진 금액을 지불해야 할 때, 동전을 가장 적게 사용해 지불할 수 있는 경우 찾기 - 가장 큰 금액의 동전을 사용해 최대한 많이 지불하는 것이 매순간(지금 이 순간) 가장 좋은 선택! coin_list = [1,50,500,100] def count(value, coin_list): total_count = 0 details = list() coin_list.sort(reverse = True) for coin in coin_l.. 2020. 10. 3. 이전 1 다음