Greedy Algorithm

Greedy Algorithm은 말그대로 닉값(?)을 하는 친구다. 기본적으로 현재의 상황에서 가장 최선의 선택을 한다고 생각하면 된다.

위에서도 말했듯이 오직 현재만 고려하기 때문에, 문제에서 구하려고 하는 바에서 경우의수 전체 에서의 최선의 답이 아닐 수 있다.

전체에서 최선의 경우를 global optimum이라고 하고, Greedy algorithm을 통해서 도출해낸 최선의경우를 local optimum이라고 한다.

그러면 global optimum이라는 제일 좋은 경우를 두고 왜 굳이 Greedy algorithm을 통해서 local optimum을 구하는 것일까?

1. 시간을 단축할 수 있다.
2. 항상은 아니지만 local optimum이 곧 global optimum이 되는 경우가 많다.

이러한 점을 고려하면 효율성이 높은 접근 방법이라고 볼 수 있다.

대표적인 예로 코인 문제가 있다.

제시된 금액을 최소의 동전 갯수로 만드는 것이다.

만약 74cent를 최소의 동전 갯수로 만들고 싶다고 가정하자.

그렇다면 큰 동전부터 작은 동전까지 순서대로 나열했을때,

1. 74cent에서는 최대 1개의 half dollar ->24
2. 24cent에서는 최대 2개의 dime ->4

3. 4cent에서는 최대 4개의 penny

   를 각각의 상황에서 선택할 수 있고, 이렇게 선택한 경우의 수가 사실상 최소의 코인 갯수가 된다.

마치며

Greedy Algorithm은 원리가 단순하고, 구현이 쉽기 때문에 매우 매력적으로 다가온다. 그래서 우리에겐 사실상 Greedy Algorithm으로 해결할 수 없는 문제에 대해서도 혹시나 하는 마음에 Greedy Algorithm으로 시도를 하는 유혹이 있다.

특히 Greedy Algorithm을 써야하지만 DP를 사용해서 풀어야하는 함정같은 문제들이 있다. (ex. kanpsack problem)

이런 유형들은 평소에 문제를 많이 풀어보고 감을 익히는게 좋을 것 같다.