Greedy Algorithm 방식에서는, 단계적으로 최선의 것을 선택하더라도, 최종적으로 최적의 해를 얻는 것은 아니다. 최적화 문제란, 소모비용을 최소로 하거나, 최대의 이익을 가져오는 문제를 말한다. 이런 최적화 문제는, 언제나 완전한 최적의 해를 얻을 수 있는 것은 아니다. 최적의 해를 얻는다고 하더라도 필요 이상의 시간이 소모된다면, 이런 경우 최적에 가까운 근사해를 얻는 것이 더 유용할 수 있다. Greedy Algorithm은 많은 경우 좋은 근사해를 얻을 수 있다.
Prims' Algorithm이 그런 방식이라고 할 수 있는데, 이 방식은 최소 신장 트리를 만들기 위해서 트리를 키워나가는 방법을 사용하고 있다. Prims' Algorithm 해결 단계는 다음과 같다.
step1. 정점 하나를 선택한다. 정점은 선택되면 방문되었다는 표시를 한다.
step2. 선택된 정점에서 경로가 존재하는 정점들 중 경로의 가중치가 가장 작은 경로는 선택하며, 이렇게 선택된 정점에서 같은 방법으로 최소의 경로 가중치를 가지는 다른 정점을 선택해나간다. 이때 가장 가까운 정점들의 집합을 Fringe Vertex라고 하자.
step3. 경로의 전체 집합은 가중치가 Priority Queue로 구성된다면, 최소의 값을 최소의 시간에 얻을 수 있다. 이 과정을 반복하여 남아있는 경로의 집합이 없을 때까지 반복한다.
이와 반대로, Kruskal's Algorithm은 전체 트리에서 필요없는 경로를 제거하여 트리를 줄여나가는 방식이다. 즉, 경로 전체를 보면서, 최소의 경로만 선택하여 사이클이 형성되는지, 그렇지 않은지를 확인하여 사이클이 존재한다면 새 원소로 집합에 추가하지 않는다.
또, 이런 Greedy Algorithm 방식을 사용하는 것으로 유명한 것은 Dijkstra Algorithm이 있다. 이것은 최단 경로를 찾는데 사용하는 알고리즘인데, 출발점에서 다른 정점까지 모든 최단거리를 찾거나, 특정 목적지까지의 최단 경로를 찾는 문제를 해결한다.
Library/Algorithm