탐욕 알고리즘
-
그리디(Greedy) 알고리즘 :: 마이구미알고리즘 2017. 2. 8. 22:07
이번 글은 그리디(Greedy) 알고리즘에 대해 다뤄본다.그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불린다. 그리디 알고리즘은 간단히 정의하자면 아래와 같이 표현할 수 있다. 경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다. 여기서 최선이라고 생각하는 경우가 무엇인가?그것을 이해하면 그리디 알고리즘을 이해할 수 있다.쉽게 말하면, 전체를 고려하지 않고, 그 순간에서의 최선을 말한다.즉, 그때그때 더 좋아보이는 쪽을 선택하는 것이다.그렇기에 최종적으로는 그 선택이 최적이라고 확신할 수 없다. (문제에 따라 최적이라고 확신할 수도 있다.) 예를 들어, 지금은 초코파이를 먹을 수 있지만, 10분 후면 랍스타를 먹을 수 있다.그리디 알고리즘의 경우에..