Greedy Algoritm 개념

Greedy Algoritm

‘Greedy Algoritm’은 탐욕알고리즘이라고 하는데 단순무식하게 현재 상황에서 지금 당장(=탐욕스럽게) 좋은 것만 고르는 방법이다. 그렇기 때문에 미래 혹은 다음 선택은 고려하지 않고 현재의 선택에 집중하게 된다. Greedy Algoritm은 기준에 따라 좋은 것을 선택하므로 ‘가장 큰 순서대로’ 혹은 ‘가장 작은 순서대로’같은 기준을 직접 찾아야 하며 정렬 알고리즘과 함께 사용하면 효율이 좋은 경우가 많다.

거스름돈

문제

카운터에서 거스름돈을 거슬러 줘야하고, 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하자. 손님에게 거슬러 줘야 할 돈이 1260원일때 거슬러 줘야 할 동전의 최소 개수를 구하라.

접근 방법

이 문제는 가장 큰 화폐 단위부터 거슬러 주면 된다. 그렇기 때문에 큰 단위의 거스름돈으로 나눠주기 시작하면된다.

내가 푼 코드

N = 1260
Coin = 0

Coin += N//500
N = N%500

Coin += N//100
N = N%100

Coin += N//50
N = N%50

Coin += N//10
N = N%10

print(Coin)

정리한 코드

N = 1260
Coin = 0

Coin_types = [500,100,50,10]

for i in Coin_types:
    Coin += N//i
    N %= i

print(Coin)

Greedy Algorithm 정당성

그리디 알고리즘은 모든 문제에 적용할 수 없다. 정확히 말하면 그리디 알고리즘으로 최적의 해를 항상 구할 수는 없다. 예를 들어 거스름돈 단위가 500,400,100 이고 거스름돈이 800원이면 400원짜리 두개로 거슬러 주는 것이 효과적이나 그리디 알고리즘을 사용하면 500,100,100,100 네개로 거슬러 주게된다. 이 사오항에서는 큰 단위가 작은 단위의 배수 형태이므로 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업을 수행해야 아이디어가 정당해진다. 이렇듯 Greedy문제는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토 가능해야한다.

만약 Greedy알고리즘으로 해결할 수 없다면 DynamicProgramming 혹은 Graph Algorithm을 사용할 것을 고려해본다.