Algorithm] 그리디 알고리즘(Greedy Algorithm)

Greedy Algorithm(그리디 알고리즘;탐욕 알고리즘)

데이터 간 관계를 고려 않고 수행 과정에서 모든 것들을 욕심 내어

최솟값 혹은 최댓값을 가진 데이터를 선택한다.

이러한 선택을 근시안적인 선택이라고도 하며

이러한 선택으로 그리디 알고리즘은 문제의 최적해를 찾는다.

그리디 알고리즘에서 선택이 이뤄지면 번복하지 않고 다른 것을 취하지 않기 때문에

알고리즘 자체는 매우 단순하지만, 제한적인 경우에만 이 알고리즘이 유효하게 사용할 수 있다.

대표적인 예가 동전 거슬러주기(Coin Change)문제이니 이를 토대로 알고리즘에 대해서 알아보자.

현실처럼 500원, 100원, 50원, 10원이 있다고 하자.

거스름돈 동전의 수가 가장 적은 최적해를 구하고 싶을 때, 그리디 알고리즘으로 해결할 수 있다.

그리디 알고리즘을 통해 가장 큰 액면의 동전을 취하면서, 최소 동전 수를 찾아낼 수 있다.

만약 860원이라는 액수의 돈을 거슬러 줘야 하는 상황이라면 아래의 규칙에 따라 진행한다.

change=860

c500=c100=c50=c10=0

while (change>=500)

change -= 500, c500++

while (change>=100)

change -= 100, c100++

while (change>=50)

change -= 50, c50++

while (change>=10)

change -= 10, c10++

return c500+c100+c50+c10

result : 6

아래의 규칙을 잘 살펴보면

특정 구간에서는 그 이후의 상황에 대해서는 전혀 고려하지 않고 명령을 수행한다.

이것이 아까 위에서 말했던 그리디 알고리즘의 근시안적인 특성이다.

최고 액면가부터 순차적으로 거스름돈을 해결하는 알고리즘에는 맹점이 있다.

만약에 애매하게 260원이라는 액면가를 가진 동전이 추가 발행되어 존재한다고 하자.

300원이라는 돈을 거슬러 주려 한다면,

그리디 알고리즘에 따르면 260원 1개, 10원 4개를 취하는 것이 최적해가 되겠지만 정답이 아니다.

100원 3개라는 답이 따로 존재하며 맹점을 보여준다.