Python x 알고리즘 : 탐욕법(Greedy) 알고리즘

Greedy(탐욕법) 알고리즘

Greedy는 탐욕이라는 뜻으로, 현재 상황에서 가장 좋은 것만 고르는 방법을 의미한다.

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 정당성이 중요하다.

- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다.

 

위 사진에서는 그리디 알고리즘을 사용해서 최적의 해를 구할 수 없다.

그리디 알고리즘은 5 다음 7, 10, 8 중 가장 최적의 해인 10을 선택하고 그 다음 트리인 4, 3에서 최적의 해인 4를 선택하기 때문에

최적의 해인 5 -7 -9를 구할 수 없고 5 - 10 - 4로 19의 값을 얻기 때문이다.

 

-> 이를 통해 일반적인 상황에서는 그리디 알고리즘을 통해 최적의 해를 보장받을 수 없는 경우가 많다.

하지만 코딩 테스트에서는 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있도록 출제된다.

 

1. 만약 점원이 1260원을 거슬러줘야한다면?

2. 이 문제에서 거슬러 주어야 할 동전의 최소 개수를 구해야한다. 즉 동전의 개수가 최대한 적게 나와야한다.

3. 500원 -> 100원 -> 50원 -> 10원 순으로 거슬러주면 500원 2개 100원 2개 50원 1개 10원 1개 총 6개의 동전으로 문제를 해결할 수 있다.

 

하지만 만약 800원의 거스름돈에서 화폐 단위가 500, 400, 100이라면?

그리디 알고리즘을 사용했을 경우 500원 1개 100원 3개 총 4개의 동전이 나온다.

하지만 최소 갯수는 400원짜리 2개를 거슬러 줬을때다.

 

이는 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다는 조건이 붙기 때문에 그리디 알고리즘이 적용되는 것이다.

- 그리디 알고리즘에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

 

//거스름 돈
n = 1260
//동전 갯수
count = 0

//화폐 단위
array = [500, 100, 50, 10]

//화폐 단위만큼 반복문을 돌린다.
for coin in array:
    count += n
    n %= coin
    
print(count)

- 화폐의 종류가 K라고 했을 때, 시간 복잡도는 O(K)이다.

- 이 알고리즘의 시간 복잡도는 거슬러줘야하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.