[알고리즘] 4장. Greedy Algorthm

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 4-1

* 탐욕적 알고리즘

- 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택한다.
- 그 순간의 선택은 그 당시(local)에는 최적이지만 그 결과들을 모아서 최종적인(global)해답을 만들었다고 해서 그 해답이 궁극적으로 최적이라는 보장이 없다. 따라서 탐욕적인 알고리즘은 항상 최적의 해답을 주는지 반드시 검증해야 한다.

* 설계 절차
- 1. 선정 과정 (selection procedure) : 현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다.
- 2. 적정성 점검 (feasibility check) : 새로 얻은 해답모음이 적절한지를 결정한다.
- 3. 해답 점검 (soluction check) : 새로 얻은 해답모음이 최적의 해인지를 결정한다.

---

📌 4-2

* 그래프 용어
- 비방향성 그래프(undirected graph) G=(V,E)
- V는 정점(vertex)의 집합
- E는 이음선(edge)의 집합
- 경로(path)
- 연결된 그래프(connected graph) : 어떤 두 정점 사이에도 경로가 존재
- 부분그래프(subgraph)
- 가중치 포함 그래프(weight graph)
- 순환경로(cycle)
-  순환적 그래프(cycle graph), 비순환적 그래프(acyclic graph)
- 트리(tree) : 비순환적이며, 비방향성 그래프
- 뿌리 있는 트리(rooted tree) : 한 정점이 뿌리로 지정된 트리

* 신장트리(spanning tree)
- 연결된, 비방향성 그래프 G에서 순환경로를 제거하면서 연결된 부분그래프가 되도록 이음선을 제거하면 신장트리가 된다.
- 모든 정점을 다 포함하면서 트리가 되는 열결된 부분그래프다.

* 신장트리의 개수
- 노드가 n개인 complete graph Kn의 엣지 개수 : nC2
- 트리는 엣지수가 n-1
- Kn으로부터 생성할 수 있는 엣지 수가 n-1인 그래프의 개수 : (nC2)C(n-1)

* 최소비용신장트리(minimum spanning tree)
- 신장트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프
- 적용 예시 : 도로건설, 통신, 배관

* 최소비용신장트리 찾기

- 문제 : 비방향성 그래프 G = (V,E)가 주어졌을 때, F => E를 만족하면서 (V,F)가 G의 최소비용신장트리(MST)가 되는 F를 찾는 문제
- 알고리즘:
1. F:=0;
2. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복
(a) 선정 절차: 적절한 최적해 선정절차에 따라서 하나의 이음선을 선정
(b) 적정성 점검: 선정한 이음선을 F에 추가시켜도 사이클이 생기지 않으면 F에 추가
(c) 해답 점검 : T = (V,F)가 신장트리면, 사례해결. T는 최소비용신장트리.

* <A> Prim의 알고리즘

1. F:=0;
2. Y:={v1};
3. while(사례 미해결)
(a) 선정 절차/적정성 점검: V - Y에 속한 정점 중에서 Y에 가장 가까운 정점 하나를 선정
(b) 선정한 정점을 Y에 추가
(c) Y로 이어지는 이음선을 F에 추가
if (Y==V) (d) 해답 점검 : Y = V가 되면, T = (V, F)가 최소비용신장트리

void prim(int n, const number W[][], set_of_edges& P) {
	index i, vnear;
	number min;
	edge e;
	index nearest[2..n];
	number distance[2..n];
	F = 0;
	for (i = 2; i < n; i++) {
		nearest[i] = 1;
		distance[i] = W[1][i];
	}
	repeat(n-1 times) {
		min = infinite;
		for (i = 2; i <= n; i++)
			if (0 <= distance[i] < min) {
				min = distance[i];
				vnear = i;
			}
		e = vnear와 nearest[vnear]를 잇는 이음선;
		e를 F에 추가;
		distance[vnear] = -1;
		for (i = 2; i <= n; i++)
			if (W[i][vnear] < distance[i]) {
				distance[i] = W[i][vnear];
				nearest[i] = vnear;
			}
	}
}

---

📌 4-3

* 서로소 집합 추상 데이터타입 (disjoint set abstract data type)
- index i;
- set_pointer p, q;
- initial(n): n개의 서로소 부분집합을 초기화 (하나의 집합에 1에서 n사이의 인덱스가 정확히 하나 포함됨)
- p = find(i): 인덱스 i가 포함된 집합의 포인터 p를 넘겨줌
- union(p, q): 두 개의 집합을 가리키는 p와 q를 합병
- equal(p, q): p와 q가 같은 집합을 가리키면 true를 넘겨줌

 

* <A> Kruskal의 알고리즘

1. F:=0;
2. 서로소가 되는 V의 부분집합들을 만드는데, 각 부분집합 마다 하나의 정점만 가짐
3. E안에 있는 이음선을 가중치의 비내림차순으로 정렬
4. while(답을 구하지 못했음)
(a) 선정 절차 : 최소가중치를 갖고 있는 다음 이음선을 선정
(b) 적정성 점검 : 만약 선정된 이음선이 두 개의 서로소인 정점을 잇는다면, 먼저 그 부분집합을 하나의 집합으로 합하고, 그 다음에 그 이음선을 F에 추가한다.
(c) 해답 점검 : 만약 모든 부분집합이 하나의 집합으로 합해지면, 그 때 T=(V,F)가 최소비용신장트리

void kruskal(int n, int m, set_of_edges E, set_of_edges& F) {
	index i, j;
	set_pointer p, q;
	edge e;
	E에 속한 m개의 이음선을 가중치의 비내림차순으로 정렬;
	F = 0;
	initial(n);
	while (F에 속한 이음선의 개수가 n-1보다 작다) {
		e = 아직 점검하지 않은 최소의 가중치를 가진 이음선;
		(i, j) = e를 이루는 양쪽 정점의 인덱스;
		p = find(i);
		q = find(j);
		if (!equal(p,q)) {
			merge(p,q);
			e를 F에 추가;
		}
	}
}

---

📌 4-4

* <A> Dijkstra 알고리즘 (탐욕적인 방법)
- 단일출발점 최단 경로 문제 (single source shortest path problem)

- 문제 : 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로 구하기.
- 알고리즘
1. F := 0;
2. Y := {v1};
3. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복
(a) 선정 절차/적정성 점검 : V - Y에 속한 정점 중에서, v1에서 Y에 속한 정점 만을 거쳐서 최단경로가 되는 정점 v를 선정
(b) 그 정점 v를 Y에 추가.
(c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가.
(d) 해답 점검 : Y = V가 되면, T = (V,F)가 최단경로를 나타내는 그래프

- 시간 복잡도 분석
T(n) = 2(n-1)^2 => Θ(n^2)
힙으로 구현하면 Θ(mlgn), 피보나치 힙으로 구현하면 Θ(m + nlgn)

void Dijkstra(int n, const number w[][], set_of_edges& F) {
	index i, vnear;
	edge e;
	index touch[2..n];
	number length[2..n];
	F = 0;
	for (i = 2; i <= n; i++) {
		touch[i] = 1;
		length[i] = W[1][i];
	}
	repeat(n-1 times) {
		min = infinite;
		for (i = 2; i <= n; i++)
			if (0 <= length[i] < min) {
				min = length[i];
				vnear = i;
			}
		e = (touch[vnear], vnear): 이음선;
		e를 F에 추가;
		for (i = 2; i <= n; i++)
			if (length[vnear] + W[vnear][i] < length[i]) {
				length[i] = length[vnear] + W[vnear][i];
				touch[i] = vnear;
			}
		length[vnear] = -1;
	}
}

---

📌 4-5

* Huffman Code

- 최적 이진 코드를 만든다.
1. Fixed-length binary code : 코드의 길이가 고정
2. Variable-length binary code : 코드의 길이가 변함
3. Optimal binary code : 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드
4. 전치코드 : prefix code - 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없다.

* Huffman Code 구축 방법
(1) 빈도수를 데이터로 갖는 n개의 노드를 생성
(2) 빈도수의 합이 최소가 되는 노드를 merge 시켜 이진트리로 구축
(3) 모든 노드가 하나의 이진트리가 될 때까지 단계(2)를 반복

* <A> Huffman code 생성 알고리즘
- 우선순위 큐(Priority Queue) 사용 - Heap
- 자료구조
struct nodetype {
char symbol;
int frequency;
nodetype* left;
nodetype* right;
};
- 초기
1. 우선순위 큐 PQ에서 nodetype 레코드를 가리키는 포인터 n개를 생성.
2. PQ의 각 포인터 p에 대해 p->symbol = 문자, p->frequency = 문자의 빈도수, p->left = p->right = NULL

- 시간 복잡도: Θ(nlgn)

for (i = 1; i <= n-1; i++) {
	remove(PQ, p);
	remove(PQ, q);
	r = new nodetype;
	r->left = p;
	r->right = q;
	r->frequency = p->frequency + q->frequency;
	insert(PQ, r);
}
remove(PQ, r);
return r;

---

📌 4-6

* 0-1 Knapsack Problem (동적계획법)
S = {item1, item2, ..., itemn}
wi = itemi의 무게
pi = itemi의 가치
W = 배낭에 넣을 수 있는 총 무게
라고 할 때,
Sigma(wi)<=W를 만족하면서 Sigma(pi)가 최대가 되도록 A => S가 되는 A를 결정하는 문제다.

* Fractional Knapsack Problem (탐욕적인 방법)

* <A> 0-1 Knapsack Problem (동적계획법)

- 시간 복잡도 분석
Θ(2^n)
P행렬의 엔트리 수 => O(nW)
최악의 경우 수행시간 = O(min(2^n,nW))

Knapsack(p, w, n, W) {
	for (w = 0 to W) P[0, w] = 0
	for (i = 0 to n) P[i, 0] = 0
	for (i = 1 to n)
		for (w = 0 to W)
			if (wi <= w)
				P[i, w] = max { P[i-1, w], pi + P[i-1, w-wi]}
			else
				P[i, w] = P[i-1, w];
	return P[n, W]
}

* NP문제

- 더 나은 알고리즘을 발견하지 못한 문제

* 탐욕적인 방법 vs 동적계획법
최적화 문제를 푸는데 적합 / 최적화 문제를 푸는데 적합
알고리즘이 존재할 경우 보통 더 효율적 / 때로는 불필요하게 복잡
알고리즘이 최적인지를 증명해야 함 / 최적화 원칙이 적용되는지를 점검해 보기만 하면 됨
단일 출발점 최단경로 문제: Θ(n^2) / 모든 노드간의 최단경로 문제: Θ(n^3)
배낭 빈틈없이 채우기 문제는 풀지만, 0-1 배낭 채우기 문제는 풀지 못함 / 0-1 배낭 채우기 문제를 풀 수 있음

---

📌 4-7

* 상호배타적 집합의 처리 (Disjoint Sets Algorithm)
- 상호배타적(disjoint): 집합간에 교집합은 0
- 응용 : 인터넷 상의 웹페이지 관계, alias 처리, 컴퓨터 네트워크

- 방법
1. linked list 사용 방법
2. array 사용 방법
3. tree(forest) 사용 방법
3-a. 단순 방법
3-b. 무게(weight)고려 방법
3-c. path compression 방법

- operation
- make_set(v): make a set with an element v
- find(v): returns a name of the set containing v
- union(u,v): 원소 u와 원소 v를 갖고 있는 집합을 하나로 합친다. 이미 같은 집합에 속해 있을 수 있다.

- 문제 : find, union의 명령어가 다수 있을 때 효율적인 처리가 가능한 자료구조와 알고리즘을 개발한다.
- weighting-union heuristic
- Kruskal 알고리즘 분석

---