[Algorithm] 그리디 알고리즘 (Greedy)

그리디 알고리즘이란

탐욕법 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다. 

 

코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그렇기에 많은 연습이 필요하다. 

 

코딩테스트에서는 바로 문제의 유형을 파악하기 어렵다. 우선 그리디알고리즘을 의심하고, 문제를 해결할 수 있는 해결법이 존재하는지 고민한 이후에 해결방법을 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘등으로 문제를 해결해보자.

 

그리디 알고리즘 조건

그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지가 있다.

1. 탐욕스러운 선택 조건 : 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 합니다. 여기서 "안전하다" 라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것입니다.
2. 최적 부분 구조 조건 : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다라는 조건이다. 이말은 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다는 것이다.

 

그리디의 예시

https://www.acmicpc.net/problem/11047

11047번: 동전 0

주어진 동전의 종류가 N개 일때, 주어진 K를 적절한 조합으로 만드는 문제이다.

단, 동전의 갯수는 최솟값이어야한다.

 

예시에서 보는것 같이

K가 4200원일때 주어진 동전의 종류가 N개이고

1원, 5원, 10원, 50원, 100원, 500원, 1000원, 5000원, 10000원, 50000원 이라면

 

4200원을 만드는 동전 갯수의 최솟값은 

4200원 보다 작지만 그 중 가장 큰 동전으로 조합을 짜는 것이다.

 

N,K = map(int, input().split())
coins = sorted([int(input()) for _ in range(N)], reverse=True)
count = 0

for i in range(N) :
    count += K // coins[i]
    K %= coins[i]

print(count)