Optimization Problem
알고리즘 문제는 크게 Decision Problem, Optimization Problem으로 나뉜다.
Decision Problem은 문제에 대한 답을 yes / no로 대답할 수 있는 문제이다. 예를 들면, "그래프에서 a->b까지의 weight 합이 3 이하인 path가 존재하는가?" 와 같은 문제가 있을 수 있다.
Optimization Problem은 문제에 대한 답 중, 최적해를 도출하는 문제이다. 예를 들면, "그래프에서 a->b까지의 weight 합이 최소인 path를 구하시오" 와 같은 문제이다.
Greedy Algorithm
Optimization Problem에는 여러가지 해가 존재할 수 있지만, 그 중에서 최적해를 구해야 한다. 이 최적해를 구하는 방법에는 Greedy Algorithm이 있다.
Greedy Algorithm은 각 단계에서 할 수 있는 최선의 선택을 반복하는 것이다. 그런데 이렇게 선택해서 항상 최적해를 구할 수 있을까? 답은 No이다. Greedy Algorithm가 항상 최적해를 구한다고는 할 수 없다.
하지만, Greedy Algorithm을 이용해서 무조건 최적해를 찾을 수 있는 문제가 존재한다. 먼저 언급하자면 Minimum Spanning Tree를 찾는 문제와, Single Source Shortest Path를 찾는 문제이다.
Minimun Spanning Tree
Spanning Tree
G=(V,E)에 대한 Spanning Tree는 G의 모든 vertex를 가지면서 connected된 subgraph이다. 이 때 간선의 수가 최소가 되어야 하므로, m = n-1이 된다.(n: vertex의 수, m: edge의 수)
Minimum Spanning Tree(MST)
Spanning Tree중 가중치의 합이 가장 작은 Spanning Tree를 말하고, 한 그래프에 대한 MST는 여러개가 존재할 수 있다.
MST를 구하는 알고리즘은 Prim, Kruskal이 있다.
Prim's Algorithm
프림 알고리즘에서는 vertex를 다음의 3종류로 구분한다.
Tree vertices: MST에 포함된 vertex
Fringe vertices: Tree vertex에 인접한 vertex
Unseen vertices: Tree, Fringe 모두 아닌 vertex
프림 알고리즘은 Tree vertex를 늘려가는 알고리즘이라고 생각하면 된다. 수도코드는 다음과 같다.
- 시작 정점 s를 선택하고, 이를 tree set에 넣어준다.
- s에 인접한 vertex들을 s와의 weight와 함께 fringe set에 넣어준다.
- fringe set 중 weight가 가장 작은 vertex v를 선택하여, tree set에 추가한다.
- v에 인접한 vertex들을 v와의 weight와 함께 fringe set에 넣어준다.
- 이 때, v에 인접한 vertex가 unseen인 경우는 fringe set에 추가한다.
- 인접한 vertex가 fringe인 경우에는, 해당 vertex가 원래 갖고 있던 weight와 v와의 weight를 비교하여 작은 것을 선택한다.(v와의 weight가 작다면, weight를 업데이트해야 한다.)
- 인접한 vertex가 tree인 경우에는 그냥 넘어간다.
위의 과정을 fringe set의 크기가 0이 될 때까지 반복해주면 된다.
주요 연산은 fringe 중 최소의 weight를 갖는 vertex를 구하는 연산, 해당 vertex에 인접한 vertex들을 처리해주는 연산이 있다.
fringe set에서 최솟값을 구하는 연산이 반복되기 때문에, fringe set은 Priority Queue를 이용하여 관리한다. Priority Queue를 어떻게 구현하는 지에 따라 시간 복잡도가 결정된다.
v의 인접 vertex를 처리하는 과정은 O(deg(v)) time이 소요된다.
만약 Priority Queue를 Unsorted Array로 구현한 경우, 프림 알고리즘의 시간 복잡도는 O(n2)이다.
Kruskal's Algorithm
크루스칼 알고리즘은 forest를 합쳐나가는 알고리즘이라고 생각하면 된다.
Union Find를 이용하여, tree set끼리 union하며 MST를 구한다. 수도코드는 다음과 같다.
- edge들 중에서 weight가 최소인 edge를 선택한다.
- edge가 cycle을 만들지 않으면, 즉 다른 set에 속해있으면 union 하고, 같은 set에 속해있으면 pass한다.
크루스칼 알고리즘의 경우에도 가중치가 최소인 edge를 계속 찾아야 하기 때문에 Priority Queue를 이용하고, 같은 set인지 확인하고 합치는 연산을 하기 위해 Union Find를 이용한다. 이 둘을 구현하는 방법에 따라 시간 복잡도가 달라진다.
Single-Source Shortest Paths
어떤 vertex에 대해, 다른 vertex까지의 shortest path들을 구하는 문제이다.
Dijkstra Algorithm
다익스트라 알고리즘은 Greedy, DP를 이용한다. 수도코드는 다음과 같다.
프림 알고리즘과 상당히 비슷한 부분이 많은데, 프림 알고리즘과 다른 점은 fringe vertex에 출발점으로부터의 weight를 저장한다는 것이다.
위의 수도코드에서 d(v, m)은 v에서 m까지의 최단거리를 저장한다.
그래프를 adjacency list로 구현하고, fringe set을 unsorted array에 저장하는 경우, 시간복잡도는 O(n2)가 된다.
