[Algorithm] Greedy 알고리즘

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

-> 그렇게 했을때 최적의 해를 구할 수 있는지 검토해야함

* 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

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

 

ex) 거스름돈 문제

[정답] 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

 

그리디 알고리즘의 정당성

: 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

 

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