[알고리즘] 그리디 알고리즘

그리디 알고리즘은 선택의 순간마다 당장의 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 답변에 도달하는 알고리즘이다.

하지만, 해당 알고리즘을 사용하는 것이 항상 최적의 방법이라고는 보장할 수 없다.

 

- 그리디 알고리즘 문제 해결 방법

1. 선택절차 : 현재 상태에서의 최적의 해답을 선택.

2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사.

3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복.

 

- 그리디 알고리즘 문제(큰 수의 법칙)

ex ) 260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러 주는 경우는? [500원, 100원, 50원, 10원]

# 위의 문제의 경우, 가장 큰 동전인 500원은 제외되므로 100원짜리 2개, 50원짜리 1개, 10원짜리 1개 순서대로
# 거슬러 주면 된다.
# 해당 답을 코드로 설명하면 다음과 같다.

def greedy(n):
    count = 0
    array = [500,100,50,10]
    for coin in array:
        count +=n // coin
        n %=coin
    # print(coin)
    # print(count)