파이썬의 자료구조 - 그리디

그리디

탐욕법이라고도 하는 그리디(Greedy) 알고리즘은 “현재 상황에서 최적이라고 생각하는 해를 선택“하는 방법이다.
현재 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식이며 이러한 선택 방법이 가장 좋을 것이라고 기대하고 사용하는 것이다.
그러나 말그대로 앞으로 남은 선택들을 고려하지 않고 현재 상황만 고려하기 때문에 항상 최적해(Global optimum)를 보장하지는 않는다.

그리디 특징

아래와 같은 트리가 있을 때, 시작점에서 시작하여 가장 큰 값을 구해야 한다고 가정하자.

가장 Best 방법은 6 -> 27 로 가장 큰 값인 27을 구하는거지만 그리디 알고리즘 같은 경우는 현재 상황에서 지금 당장 좋은 것만 고르기 때문에 15 -> 20 로 가게 된다.

즉 당장 좋은 것을 고르는 건 전체를 보지 않고, 지금 당장 닥친 상황만 보고 고르는거라고 보면 된다.

탐욕 알고리즘은 각각의 단계에서 최적의 수를 찾아내는 방법으로, 간단하다는 것이 장점이다.
탐욕 알고리즘이 항상 성공하는 것은 아니지만, 구현이 간단하면서도 보통은 정답에 상당히 가까운 정답을 도출해낸다.
정확한 답을 계산하는 데 시간이 너무 많이 걸린다면 근사 알고리즘을 사용할 수 있는데,
탐욕 알고리즘은 근사 알고리즘 디자인 테크닉의 한 방법이 될 수 있다. 탐욕 알고리즘은 작성하기도 쉽고 빠르기 때문이다.
근사 알고리즘의 성능은 다음의 두 가지로 판단한다.

• 얼마나 빠른가
• 최적해에 얼마나 가까운가