그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 알고리즘이라고 할 수 있다.

 

어떤 문제가 주어졌을 때 현재 상황에서 가장 좋은 방식을 선택하는 알고리즘으로 단순 무식하다고 볼 수 있다.

 

그리디 알고리즘에 해당하는 문제 풀이시 현재 상황에서 최선의 선택을 하는 것의 정당성을 파악하는 것이 중요하다!

 

대표적인 예시로는 거스름돈 문제를 생각 해 볼 수 있다.

x만큼의 거스름돈을 돌려줘야하는 상황에 500원,100원,50원,10원 짜리의 동전 사용이 가능한 경우 그리디 알고리즘에서는 가장 큰 화폐 단위부터 돈을 거슬러 준다면 동전 개수를 최소화 하여 거슬러 줄 수 있게 되는 것이다.

 

[백준 그리디 알고리즘 예시 문제]

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

11047번: 동전 0

 

문제의 표현이 조금 달라 졌을 뿐 본질적인 문제는 위의 거스름돈 문제와 동일하다.

n,k= map(int,input().split())

coin = []   #화폐 단위를 입력받을 리스트
for i in range(n):
    n = int(input())
    coin.append(n)

coin.reverse()  #큰 단위 부터 체크하기 위해 내림차순으로 변경
cnt = 0     #필요한 동전 개수

for i in range(len(coin)):
    if k >=coin[i]:
        cnt += k //coin[i]
        k = k%coin[i]

print(cnt)