‘greedy(탐욕스러운)’ + ‘알고리즘’은 한마디로 욕심쟁이 알고리즘이다.
어떻게 알고리즘 이름이 욕심쟁이 알고리즘인지 의문이 들 수 있다. 그 까닭은 알고리즘의 특성과 관련이 있다. 그리디 알고리즘은 최적해를 구하는 근사적 방법의 일종으로 여러 선택지가 주어졌을 때, 선택지마다 최적의 경우를 선택함으로써 최종적인 결과에 도달한다.
<한 줄 요약> 전체를 고려하지 않고 선택의 순간마다 가장 좋은 선택을 한다!
위의 설명에서 알 수 있듯이 모든 경우에 대해 항상 최적의 결과만이 나오는 것이 아니며, 최적의 값에 근사한 값을 목표로 작동한다. 다음 주에 다룰 동적프로그래밍처럼 최적해를 구하기 위해 모든 경우에 수를 고려해 작동 시간이 늘어나는 단점을 보완하기 위해 그리디 알고리즘을 사용한다.
탐욕적인 선택이라는 것은 거시적으로 보지 않고 근시안적으로 가장 최적인 값을 선택한다는 것을 의미한다. 이때, 현재의 선택이 전체 문제의 최적해 도출에 영향을 주어서는 안 된다. 즉, 매순간의 최적의 선택이 전체 문체의 최적의 결과로 도출되는 문제에만 그리디 알고리즘을 적용할 수 있다!!
부분마다 정해진 최적값의 합이 전체의 최적값과 같다. 즉, 문제를 여러 문제 분할하여 고려할 때, 각각의 문제들이 모여 큰 문제의 답이 되어야한다.
그리디 알고리즘의 대표 예시인 동전 문제
def solution(money):
answer = 0
change = [500, 100, 50, 10]
remain = money
for i in change:
answer += remain // i
remain = remain % i
return answer