Lecture 16 - 강연결 요소 + 그리디 알고리즘(1)

---

강연결 요소

유향 그래프의 모든 정점 쌍에 대해서 양방향으로 경로가 존재하면 강하게 연결되었다고 한다. 그래프 전체 대신 강하게 연결된 부분 그래프에 대해서는 강연결 요소 (Strongly connected component)라고 한다.

아래는 강연결요소를 찾는 psuedo code이다.

수행 시간: Θ(|V|+|E|)

 

예시 그래프를 통해 자세히 살펴보자.

---

그리디 알고리즘

그리디 알고리즘(Greedy algorithm)은 이름처럼 눈앞의 이익만 취하고 보는 알고리즘을 뜻한다. 현재 시점에서 가장 이득인 것으로 보이는 해를 선택하는 행위를 반복한다. 많은 경우에 그리디 방식은 최적해를 보장하지 못하지만, 드물게 최적해가 보장되는 경우가 존재하므로 해당 특별한 case를 잘 알아두는 것이 중요하다.

 

그리디 알고리즘의 전형적인 구조를 살펴보자.

Greedy(C)
▷C: 원소들의 총집합
{
	S ← ∅;
	while (C≠∅ and S는 아직 온전한 해가 아님) {
		x ← C에서 가장 좋아 보이는 원소;
		집합 C에서 x 제거; // C ← C-{x}
		if (S에 x를 더해도 됨) then S ← S ⋃{x};
	}
	if (S가 온전한 해임) then return S;
		else return "no solution!";
}

 

그리디 알고리즘으로 최적해가 보장되지 않는 예시

 

1. 이진 트리의 최적합 경로 찾기

2. 동전 바꾸기 문제

위와 같이 동전의 액면이 모두 바로 아래 액면의 배수가 되면 그리디 알고리즘으로 최적해가 보장되지만 아래와 같은 대부분의 경우에는 보장되지 않는다. 따라서 한국돈과 같은 경우에는 잘 풀리지만 달러 같은 돈은 최적해가 나오지 않아서 DP를 이용해야한다.

---

최소 신장 트리를 찾는 상황은 그리디 알고리즘이 최적해를 보장하는 상황 중 하나이다. 이 외에도 다익스트라 알고리즘 또한 그리디 알고리즘의 일종이며, 압축에 널리 쓰이는 허프만 코딩도 대표적인 그리디 알고리즘의 일종이다. 그리디 알고리즘을 이 최적해를 보장하는 예시들을 살펴보자.

 

1. Prim

Prim (G, r)
{
	S ←Ф ;
	정점 r을 방문되었다고 표시하고, 집합 S에 포함시킨다;
	while (S≠V) {
		S에서 V-S를 연결하는 간선들 중 최소길이의 간선 (x, y)를 찾는다; ▷ (x∈S, y∈V-S)
		정점 y를 방문되었다고 표시하고, 집합 S에 포함시킨다;
	}
}

S에서 V-S를 연결하는 간선들 중 최소길이의 간선 (x, y)를 찾는다; ▷ (x∈S, y∈V-S) 이 부분이 greedy한 부분이라고 볼 수 있다.

 

2. Activity-selection problem

이는 흔히 회의실 배정문제라고 불리는 문제이다. 시작시간 및 종료시간이 표시된 여러 개의 활동들이 있을 때, 주어진 시간 내에서 최대 개수 의 활동을 하는 것을 목표로 한다. 아래와 같이 시작과 종료시간이 명시되어있는 11개의 회의리스트가 있을때 최대한 많은 회의를 진행할 수 있는 조합을 찾는 것이다.

위 예시에서는 {𝑎1 or 𝑎2, 𝑎4, 𝑎8 or 𝑎9, 𝑎11}이 최적해이다.

 

그리디 알고리즘으로 풀기전에 최적 부분구조를 갖는지 살펴봐야한다. 최적 부분구조를 갖는지 알아보는 방법을 살펴보자.

𝑆𝑖𝑗를 𝑎𝑖가 끝나고, 𝑎𝑗가 시작하기 전의 시간동안 수행할 수 있는 활동들의 집합이라고 가정하고 𝑆𝑖𝑗에 대한 activity-selection problem의 해를 𝐴𝑖𝑗라고 하고 𝐴𝑖𝑗에 속하는 𝑎𝑖 … 𝑎𝑗 중 𝑎𝑘가 있다고 가정했을때 𝐴𝑖𝑗 = 𝐴𝑖𝑘 ∪ 𝑎𝑘 ∪ 𝐴𝑘𝑗이 𝐴𝑖𝑗 = 𝐴𝑖𝑘 + 𝐴𝑘𝑗 + 1가 되는 경우이다.

 

해당 정리를 활용하여 재귀 형태의 그리디 알고리즘 구현할 수 있다. 최적 부분구조로부터 재귀 알고리즘 구현이 가장 직관적이므로 재귀 알고리즘부터 살펴보자. k=0에 대해 호출하면 전체 s에 대한 최적해를 도출하고 f[0]=0으로 설정한다. 시간 복잡도는 Θ(𝑛)이다. 작동과정을 아래의 표를 통해 살펴보자.

 

Iteration 형태의 그리디 알고리즘 구현하면 시간 복잡도는 Θ(𝑛)으로 갖고 더 간단하다.

정리하면 다음과 같다.

① 최적 부분구조를 찾는다

② 재귀 알고리즘을 설계한다

③ 그리디 선택을 하면 부분구조가 하나만 남음을 보인다

④ 그리디 선택으로도 최적해를 구할 수 있음을 보인다

⑤ 재귀 알고리즘을 그리디 형태로 변경한다

⑥ 필요하다면 iterative한 그리디 알고리즘으로도 변경한다

---