[Python] 알고리즘 : 탐욕법 (Greedy Algorithm)

 

🔹 그리디 알고리즘(탐욕법)

• 선택의 순간마다 가장 좋은 것(최적)이라 생각되는 것을 선택하는 알고리즘.
• 각 순간에 대해서는 최적일 수 있으나, 최종적인 해답이 모든 경우의 수에서 최적이라는 보장이 없다.
• 그러나 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점도 존재.
• 그리디 알고리즘이 적용가능한 문제인지 판단 필요

 

🔹 파이썬에서의 구현

 

예제 - 동전 문제

가치의 합이 K인 동전을 가장 최소한의 개수로 만드려면,
가치가 가장 큰 동전부터 개수를 세어 나가면 된다.
 
590원을 <100,50,10> 세 종류의 동전으로 만들면,
가장 큰 단위인 100원 다섯 개, 50원 한 개, 10원 네 개로 총 10개의 동전이 필요하다.
https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

1. 동전 단위를 정렬한다. (내림차순)

2. 가치 K가 0이될 때까지,

- 각 동전단위로 K를 나눈 몫이 해당 동전의 개수

를 구한다.

 

< 코드 >

import sys
N,K = map(int,sys.stdin.readline().split())
coins = [int(sys.stdin.readline()) for _ in range(N)]
ans = 0
coins.sort(reverse=True)   # --------------------------1)
for i in range(len(coins)): # -------------------------2)
    if coins[i] <= K:
        ans += K//coins[i]
        K = K - coins[i]* (K//coins[i])

    if K == 0 :
        break

print(ans)