03. 그리디 알고리즘(Greedy Algorithm)

 

 
Q. 주어진 거스름돈을 가장 적은 수의 동전으로 거슬러주는 알고리즘을 고안하라. (이후로 후보군 집합을 C, 해결책 집합을 S라고 명명함.)
A.

그리디 알고리즘에서 필요한 세 가지 함수
1. Select() - 조건에 맞는 원소를 선택
2. Feasible() - S 집합에 들어갈 수 있는지 판단
3. Solution() - 문제가 해결되었는지 확인
 

* 최적화 문제

대상 함수 $f$를 제약 조건(Condition or Constraint) C에 맞게 최적화(대체로 최대화 또는 최소화) 하는 것.
가능(feasible)한 해결책 : C를 만족하는 아무 결과
최적의 결과 : 대상 함수를 최적화하는 해결책
 

* 그리디 알고리즘(Greedy Algorithm)

현재 갖고 있는 정보만을 가지고 결정을 내리는 것. 이에 따른 미래에 영향을 고려하지 않음.
대체로 최적화 문제를 해결하기 위해 쓰임.

- 일반적인 성질
최적화된 방법으로 풀기 위한 몇몇 문제들이 주어짐.
문제에 대한 해결책을 만들기 위한 후보군 집합 C가 있음.
 
- 알고리즘이 진행됨에 따라, 두 집합이 축적됨.
집합 1 (S) : 이미 고려되고 선택된 후보가 포함되어 있음.
집합 2 : 이미 고려되고 선택되지 않은 후보가 포함되어 있음.
 
- 함수 Solutiuon()
후보군들의 특정 집합이 문제에 대한 해결책을 제시하는지 체크하며, 당분간은 최적성에 대한 의문을 무시함.
 
- 함수 Feasible()
후보를 집합에 추가함으로써 집합을 완성시킬 수 있는지, 더불어 문제에 대한 해결이 되는지 체크함.
 
- 함수 Selection()
선택되거나 거부되지 않고 남은 나머지 후보들 중에서 어떤 것이 가장 적합한지를 나타냄.
 

* 그래프 : 최소 비용 트리(Minimum Spanning Tree, MST)

대표적인 최소비용트리 알고리즘에는 1) 크루스칼 알고리즘과, 2) 프림 알고리즘이 있음.

- 가중치가 있는 연결된 무방향 그래프 $G=(N,A;w)$ 가 주어졌음.
여기서 $N$은 노드들의 집합(크기는 n)이고, $A$는 간선의 집합, 그리고 $w$는 비용 함수($A\to R^{+}(양의실수)$)임.
 
- 연결된 서브그래프 $G^{\prime }(N,T)$를 만들어야 함.
$T\le A$이며, 간선들의 가중치 합은 최소임. 즉, $\sum _{e\in T}w(e)$가 최소임.
 
- $G^{\prime }$의 특성
i) 연결된 서브그래프 $G^{\prime }$은 최소 n-1개의 간선을 가짐.
ii) n-1개를 넘는 개수의 간선을 가지는 서브그래프 $G^{\prime }$은 최소 하나의 사이클을 가짐. 그렇다면, 사이클을 이루는 간선을 선택해서, $G^{\prime }$을 분리시키지 않고도 최소 한 개의 간선을 제거할 수 있음. 따라서, n개 이상의 간선을 가지는 $G^{\prime }$은 최적이라고 할 수 없음.
i와 ii에 의해, $G^{\prime }$은 정확히 n-1개의 간선을 가져야 하며, $G^{\prime }$은 트리임을 알 수 있음. 그래프 $G^{\prime }$은 그래프 $G$에 대한 최소 비용 트리라고 부름.
 

- 용어 정의

• 가능한 간선들의 집합이 확장되어 최적의 해결책이 될 수 있다면 "적합(Promising)"이라고 부름.
• 집합 $B$를 MST가 만들어지는 과정에서 정점의 집합이라고 가정, 만일 한 간선의 두 끝부분 중 하나만이 이 집합에 속한다면 "간선이 노드 집합$B$를 떠난다"라고 함.

- Lemma (보조 정리, 정리를 위한 정리)

• $G(N,A;w)$는 가중치가 있는 무방향성 그래프임.
• $B\subset N$임.
• $T(\le A)$는 어느 간선도 $B$를 떠나지 않는 간선들의 집합임.
• $v$는 $B$를 떠나는 제일 짧은 간선임. 그렇다면, $T\cup \{v\}$는 적합함.

- 증명

$T$가 적합하므로, $T\le U$인 MST $U$가 존재함.
이제 $T\cup \{v\}$가 적합하지 않다고 가정해 봄. 즉, $v$가 $U$에 속하지 않음.
$U$는 비용 트리이고, $U\cup \{v\}$는 사이클이 있으며, 사이클에 간선 $u$가 존재해야 함. $v$가 B를 떠나는 가장 짧은 간선이므로, $w(v)\le w(u)$이고, 그렇다면 $U^{\prime }(=U-\{u\}\cup \{v\})$은 $w(U^{\prime })\le w(U)$인 비용 트리임. 따라서, $U^{\prime }$ 또한 G의 최소 비용 트리가 됨. -> 모순되므로 $T\cup \{v\}$가 MST를 구성하기에 적합한 게 맞음.
 

- 크루스칼 알고리즘(Kruskal's Algorithm)

처음에, $G$의 각 노드는 각각의 다른 컴포넌트를 구성하고 있음. 
간선을 오름차순으로 검사함.
만일 간선이 두 다른 컴포넌트를 잇고 있다면 T에 포함시킴.
두 연결된 컴포넌트는 새로운 하나의 컴포넌트를 이룸. (합쳐짐.)
알고리즘은 하나의 컴포넌트만 남겨질 때까지 계속됨.

반복문이 진행될 때마다 $T$, $(u,v)$, 컴포넌트 상황은 다음과 같음.

※ Kruskal의 시간 복잡도
노드 n개의 최대 간선수 = $n(n-1)/2\approx n^2$
처음 정렬할 때 $O(n^{2}log{n}^2)$
for문에서 $O(n^2)$
 

- 프림 알고리즘 (Prim's Algorithm)

집합 A의 간선들은 하나의 트리를 이룸.
각각의 단계에서, 현재 있는 트리에 새로운 가지(branch)를 한 개 추가함. 
각각의 단계에서, 알고리즘은 가능한 최소의 간선$(u,v)$을 찾아냄. 여기서 $u\in B$이고, $v\in N-B$임.
 

반복문이 진행될 때마다 $T,B,N-B,(u,v)$의 상황은 다음과 같음. 

 

* 그래프 : 단일 출발점(Single Source) 최단 경로 문제

※ 기존의 값을 $\mathrm{\infty }\to 1000\to \dots \to 100$처럼 감소시키는 것을 Relaxation(완화) 기법이라고 함.
 
- 가중치가 있는 방향성 그래프 $G=(N,A;w)$가 주어짐.
각 간선은 음이 아닌 길이를 가짐.
정점들 중 하나, $s$가 시작점(Source)으로 지정됨.
 
- 문제는 시작점부터 각각의 다른 정점들까지의 최소 거리를 구하는 것임.
 

- 다익스트라 알고리즘(Dijkstra's Algorithm)

집합 $S$:  최단 경로가 찾아진 정점들의 집합
알고리즘은 반복적으로 정점 $u(\in N-S)$를 선택해 최단 경로를 추정하고, $S$안에 집어넣고, $u$를 떠나는 모든 간선을 완화(relax)함.

반복문이 진행될 때마다 $C,S,d,\mathrm{\Pi },u,v$의 상황은 다음과 같음.

 

* 스케줄링(Scheduling)

시스템의 시간을 최소화하는 것.
작업이 시스템에서 사용하는 시간을 최소화하는 것이 목표임.
서비스 시간은 미리 주어짐. (작업 $i$는 $t_i$만큼의 시간을 사용하며, $1\le i\le n$임.)
작업의 수가 고정되어 있기 때문에, 시스템의 전체 시간을 줄이는 것과 동일함. ($=\sum _{i=1}^n{t}_i$ 최소화)
최적의 스케줄은 작업들이 걸리는 시간이 짧은 순서대로 정렬되어 있을 때 해결 가능함. (Shortest Job First 기법)
 

- 마감 기한(Deadline)이 있는 단위 시간(Unit time) 작업 스케줄링

수행되어야 할 n개의 작업의 집합이 있고, 각각은 단위 시간만큼 소요됨.
작업 $i$는 시간 $d_i$보다 빨리 실행되었을 경우에만 0보다 큰 이득 $g_i$를 얻게 됨.
작업 집합은 그 안의 작업 전부가 각각의 마감기한을 넘기지 않고 실행되도록 하는 순서(sequence)가 하나 이상 존재하는 경우에만 가능(feasible)함.
 

- 그리디 알고리즘

각 단계에서 아직 고려되지 않은 작업들 중 가장 높은 $g_i$ 값을 가진 것을 추가함. 단, 선택된 작업들의 집합은 가능함(feasible)을 유지해야 함.
WLOG. 작업들은 $g_i$ 값이 작아지는 순서로 넘버링되어 있다고 가정함. (즉, $g_1\ge g_2\ge \dots \ge g_n$ 임)
배열 d는 마감 기한을 담고 있고, 해결책은 배열 j에 담기로 함.
스케줄은 배열 j에 순서대로 담김.
변수 $k$는 몇 개의 작업이 스케줄 되었는지를 나타냄.
배열 j안의 $k$개의 작업은 마감기한이 증가하는 순서로 정렬되어 있음.
작업 $i$가 고려될 때, 알고리즘은 배열 j의 적절한 위치에 다른 작업의 마감기한 넘김 없이 넣을 수 있는지 판단함. 가능하다 판단이 되면, 작업 $i$는 받아들여지고, 아니면 거부됨.

알고리즘이 진행될 때 배열 j의 상황은 다음과 같음.