왜 Greedy일까?
// Greedy = 욕심부리는, 탐욕스러운 //
필자는 Greedy 가
전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에
현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다
(현재만 생각하는 욕심을 부린다는 의미이다.)
그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다.
Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다.
하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다.
예제)
위 그래프에서 goal까지의 최저비용 거리를 구해보자.
1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 이므로 start->b
2) b 에서 출발. b에서 가장낮은 비용은 e 로 가는 2 이므로 b->e
3) e 에서 출발. e에서 갈 수 있는 경로는 마지막 goal로 가는 6 이다. e->goal
최종 비용 : 3+2+6 = 11
최적일까??
아주 운좋게도 이는 최적의 경우이다.
하지만 다른 노드를 통해 가는 길이 5 + 1 + 1 = 7 이런식으로 비용이 더 적을 가능성이 농후하다.
Greedy Algorithm 은 항상 최적의 답을 도출하지는 않는다.
그렇다면 왜? 부정확한 답이 나올 수 있는 Greedy 를 쓸까?
1.
특정 문제들은 현재 최고의 정답만을 구하가다 보면 Optimal Solution 이 나오는 문제들이 있다!!
(물론 이 그리디 알고리즘이 정확하고 증명된 알고리즘이어야 한다.)
2.
혹은, 최적의 답이 아니더라도 근사치를 구하는 것이 목표인 경우이다!
정확한 정답이 아니더라도 속도면에서 만족할만한 결과를 얻어낼 수 있기에 사용된다.
그리디 알고리즘의 대표적인 예로는 Prim Algorithm, Kruskal Algorithm, Dijkstra Algorithm 등등 이 있다.
출처 : 고려대학교 정순영 교수님 알고리즘 수업,
introduction to algorithms 3rd edition - 토머스 H. 코르먼(Thomas H. Cormen) 찰스 E. 레이서슨(Charles E. Leiserson)
댓글