24. 그리디 알고리즘
Greedy algorithm, 탐욕기법이라고도 하며 한가지 조건만을 기준으로 최적의 결과를 도출하는 과정을 의미한다.
한가지 조건만을 기준으로 알고리즘을 진행하기 때문에 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적의 해에 근접한 형태를 찾을 수 있는 알고리즘이다.
특정 상황에서는 최적의 해를 보장할 수 있지만, 대부분의 상황에서는 그리디 알고리즘은 최적의 해를 도출하지는 못한다.
24-1. 그리디 알고리즘의 확장
그리디 알고리즘의 중요한 점은 다른 알고리즘으로 확장이 된다는 점이다.
그리디 알고리즘 자체는 최적의 해를 보장받지 못한다는 점에서 적용하기 힘든 경우가 많지만, 최소신장트리(크루스칼 알고리즘) 등 최적의 경로를 찾는데 그리디 알고리즘으로부터 확장하는 경우가 있고 동적계획법을 같이 적용하는 등 확장 측면에서 의미가 있는 알고리즘이다.
24-2. 적용예시
그리디 알고리즘의 대표적인 적용 예시는 거스름돈이다.
거스름돈의 핵심은 가장 적은 개수의 화폐를 제공한다는 것이고, 이때 알고리즘의 기준은 가장 적은 개수로만 적용하게 된다.
#거스름돈을 가장 적은 화폐로 거슬러준다고 할 때
def greedy(value):
result = 0
result = result + value//500
value = value % 500
result = result + value//100
value = value % 100
result = result + value//50
value = value % 50
result = result + value//10
return result
print(greedy(1260))