그리디 알고리즘

그리디 알고리즘이란?

그리디 알고리즘은 어떠한 문제가 있을 때 탐욕적으로 문제를 푸는 알고리즘이다. 이때 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 즉, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

따라서 그리디 문제를 해결하기 위해서는 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악해야 한다.

힌트

그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 가장 큰 순서대로, 가장 작은 순서대로 와 같은 기준을 제시해준다. 그에 대한 예시는 거스름돈이 있다.

카운터에서 거스름돈으로 500원, 100원, 50원, 10원 있을 때, 거슬러 줘야할 동전의 최소 개수를 구하시오

• 위의 문제에서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 정답이 나온다.

정당성 검토

위의 거스름돈 문제에서는 500원 부터 거슬러주면 된다. 그런데 만약 거슬러 줘야 하는 돈이 800원이고, 화폐단위가 500원, 400원, 100원인 경우의 최적해는 2개의 동전(400원 + 400원)을 거슬러 줘야 한다.

• 위의 경우에는 가지고 있는 가장 큰 돈인 500원이 다른 화폐 단위(400)의 배수가 아니기 때문에 그리디 알고리즘을 적용할 수 없다. => 정당성 X
• 따라서 그리디 알고리즘을 적용하기 위해서는 정당성을 검토한 후에 적용할 수 있다.