[Python] 그리디 알고리즘이란 무엇일까? /백준 11047 동전 0 파이썬 풀이

 

Greedy 알고리즘

말 그대로 탐욕적인, 현재 상황에서 지금 당장! 좋은 것만 고르는 방법

가장 좋은 게 내꺼얌

그리디 알고리즘은,

문제를 풀기 위한 최소한의 아이디어를 적절히 떠올려야 풀 수 있다!

 

 

 

 

 

그리디 알고리즘의 단점

출처-동빈나 유튜브 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현

최적의 해는 5 = > 7=> 9 총 21이 나오는 경로일 것이다

 

 

 

 

 

 

Q. 그리디 알고리즘을 사용하여
단순히 매 상황에서 가장 큰 값만 고른다면?

 

출처-(이코테 2021 강의 몰아보기) 2. 그리디 & 구현

5 => 10 => 4 총 19가 나오는, 최적의 해를 구할 수 없는 상황이 나온다.

 

예시처럼 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다....

하지만, 코테에서 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가

최적의 해가 되는 상황에서 이를 추론할 수 있도록 출제된다고 한다!

 

가장 대표적인 문제는 거스름돈 문제이다

 

백준-11047번 

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 A[i]가 오름차순으로 주어진다.

(1 ≤ A[i] ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 A[i]는 A[i]-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 

6

 

예제 입력 2 

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 2 

12

 

 

 

 

 

아이디어 생각하기

최적의 해를 구하기 위해선 가장 큰 화폐단위부터 거슬러주면 된다.

n원을 거슬러줘야할 때, 가장 큰 금액으로 거슬러 줄 수 있을만큼 거슬러 주고,

그 다음으로 큰 숫자만큼 거슬러주면 된다. 

 

가장 큰 화폐단위부터 돈을 거슬러 주는 게 최적의 해인 이유?

 

 

 

 

A[i]는 A[i]-1의 배수라는 조건이 있기 때문에

가지고 있는 동전 중, 가장 큰 단위가 항상 작은 단위의 배수이므로

작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

 

만약, 800원을 거슬러줘야하는 상황에서 화폐단위가 [500,400,100] 이라면

그리디 알고리즘을 통해 푼다면 가장 큰 금액부터 나눠져

500원 1개 100원 4개가 해일 것이다. 

하지만 실질적으론 400원 2개가 최적의 해이다.

 

그리디 알고리즘은 이런 문제가 발생하기 쉽다!

따라서 그리디 알고리즘에선 정당성 검토가 중요하다

 

 

 

 

 

 

코드 정답

n, k = map(int, input().split()) ## 총 동전의 갯수(n), 금액(k)를 입력 받기
coins = [] #동전의 단위를 받을 리스트 coins
for j in range(n):#n번 입력을 받아 입력받은 동전을 coins에 추가
  coins.append(int(input()))
#큰 수부터 오름차순
coins.sort(reverse=True)
result = 0 

  # 가장 큰 동전단위인 coins[0]부터 나눈다. 
  # k = 나눠진 후의 거스름돈이 저장되고, 다시 for문을 돌아 coins[1]로 넘어가 나눈다
  # k = 4200, coins = [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1] 이면
  # 4200는 1000원으로 4번, 100원으로 2번 나눠진다. result는 따라서 총 6번이 나온다 
  #result는 총 필요한 동전의 갯수 = for문에서 나눠진 몫들의 합이 저장된다.
for i in coins:
  result += k // i
  k = k % i
 
print(result)