[Algorithm Part 3] 6. Greedy Approach

이번 글에서는, greedy 접근법에 대해 살펴볼 것이다.

---

Geedy algorithm

Definition

Greedy 접근법은 항목(=item)의 연속적인 선택을 기반으로 문제를 푼다.

이때, 선택되는 항목은 "현재 선택 가능한 항목 중에서 가장 좋은 항목"이다.

Approach

Greedy 알고리즘은 빈 집합(=S)에서 시작해 instance의 solution이 될 때까지 항목을 순차적으로 추가한다.

• selection procedure: "현재 선택 가능한 항목 중 가장 좋은 항목(=item)"을 선택한다.
• feasibility check:  S ∪ {item}이 solution이 될 수 있는지 점검한다. 만약 될 수 있다면, S에 item을 추가한다.
• solution check: S가 solution인지 확인한다.

 

Dynamic programming처럼, greedy 접근법을 활용해 최적화 문제를 풀 수 있다.

Greedy 접근법은 dynamic programming보다 더 직관적이고 쉽게 설계할 수 있다.

하지만 greedy 알고리즘은 "문제의 optimal value를 보장함"을 증명해야 한다.

(dynamic programming는 principle of optimality가 문제에 적용되는지 확인하면 된다.)

 

이제부터, greedy 접근법에 대한 이해도를 높이기 위해, 이 접근법을 활용한 유명한 알고리즘에 대해 살펴볼 것이다.

---

1. Minimum Spanning Tree

Problem

MST를 찾는 문제다. 즉, G = (V, E)라고 가정할 때, T = (V, F)를 찾는 문제다.

Assume G is connected, weighted, undirected graph.

A spanning tree for G is a connected subgraph that contains all the vertices inGand is a tree.

Minimum spanning tree(=T) is spanning tree of minimum weight.

Approach

빈 F에서 시작해 T가 MST가 될 때까지 edge를 순차적으로 추가한다.

• selection procedure: "현재 선택 가능한 edge 중 가장 좋은 edge(=$e$)"를 선택한다.
• feasibility check: F ∪ {$e$}가 순환(=cycle)하는지 확인한다. 만약 비순환한다면, F에 $e$를 추가한다.
• solution check: T가 spanning tree인지 확인한다.

Correctness of algorithm

이전 글(Algorithm Part 2. Minimum Spanning Tree)에서 증명함

---

1.1. Prim's algorithm

빈 F, Y에서 시작해 T가 MST가 될 때까지 edge를 순차적으로 추가한다.

• selection procedure: "V-Y의 vertex 중 Y와 가장 가까운 vertex(=v)"를 선택한다. (by PQ)
  
• feasibility check: 바로 v와 Y를 잇는 edge(=$e$)를 T에 추가하고, v를 Y에 추가한다.
  (왜냐하면, $e$를 추가한 T는 무조건 순환하지 않기 때문이다.)
• solution check: T가 spanning tree인지 확인한다.

---

1.2. Kruskal's algorithm

빈 F에서 시작해 T가 MST가 될 때까지 edge를 순차적으로 추가한다.

• selection procedure: "현재 선택되지 않은 edge 중 minimum weight edge(=$e$)"를 선택한다.
• feasibility check: F ∪ {$e$}가 순환(=cycle)하는지 확인한다. (by Union-Find)
  만약 비순환한다면, F에 $e$를 추가한다.
• solution check: 새로운 T가 spanning tree인지 확인한다.

---

Analysis

base operation: 비교(=compare) 연산

input size: n(=# of vertex), m(=# of edge)

	every-case time complexity
prim's algo (by array PQ)	$\Theta (n^2)$
prim's algo (by heap PQ)	$\Theta(m\log n)$
kruskal's algo (by Union-Find)	$\Theta(m\log n)$

 

prim's 알고리즘을 사용할 때, 그래프가 sparse(m$\approx$n)하면, array PQ를 사용하고, dense(m$\approx$$n^2$)하면 heap PQ를 사용하는 것이 적절하다.