[알고리즘] 그리디 알고리즘 - 최소비용신장트리, 스케줄 짜기

탐욕 알고리즘이란?

 

작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다.

 

선택과정(selection procedure) : 집합에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택한다.

 

적절성검사(feasibility check) : 새로운 집합이 해답이 되기 적절한지 검사한다.

 

해답점검(solution check) : 새로운 집합이 문제의 해답인지 결정한다.

 

이 과정이 동시다발적으로 진행된다.

 

거스름돈을 고르는 탐욕 알고리즘

 

예를 들어 돈이 50원, 25원, 10원, 5원, 1원이 있고 31원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.)

 

거스름돈 알고리즘 예시 1

 

1. 50원을 집었다가 내려놓는다.

 

2. 25원을 집는다.

 

3. 25원을 집었다가 내려놓는다.

 

4. 10원을 집었다가 내려놓는다.

 

5. 5원을 집는다.

 

6. 5원을 집었다가 내려놓는다.

 

7. 1원을 집는다.

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

위의 문제가 거스름돈 문제와 같다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int a, b; cin >> a >> b;
	int cnt = 0;
	vector<int> v(a);
	for (int i = 0; i < a; i++) {
		int num; cin >> num;
		v[i] = num;
	}
	for (int i = a - 1; i >= 0; i--) {
		while (v[i] <= b) {
			b -= v[i];
			cnt++;
		}
	}
	cout << cnt;
}

위 문제의 소스 코드인데 위에서 설명한 거스름돈 알고리즘과 같은 알고리즘인 걸 알 수 있다. 다른 점은 각각의 거스름을 할 수 있는 돈의 가치를 정할 수 있다는 것인데, 이 거스름돈의 가치를 정하는 것을 잘못한다면 탐욕 알고리즘이 최적의 해답을 찾지 못할 수 있다.

 

예를 들어 돈이 12원, 10원, 5원, 1원이 있고 16원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.) 탐욕 알고리즘을 쓴다면,

 

 

탐욕 알고리즘 예시 2

 

1. 12원을 집는다.

 

2. 12원을 집었다가 내려놓는다.

 

3. 10원을 집었다가 내려놓는다.

 

4. 5원을 집었다가 내려놓는다.

 

5. 1원을 4개 집는다.

 

위의 사례에서는 거스름돈 동전의 개수가 5개가 되는 반면, 최적의 답은 10 + 5 + 1인 3개의 동전이 답이다.

 

거스름돈 문제에서 보듯이 탐욕 알고리즘은 최적의 해를 보장하지 않는다. 따라서 탐욕 알고리즘을 설계했다면 최적의 해를 주는지 항상 점검하자.

 

coinset을 어떻게 가지고 있느냐에 따라 최적의 해를 구할 수도 있고 아닐 수도 있다.

 

optimality proof(최적 증명)

 

만약 coinset이 $c = \{1,\;5,\;10\}$이고 거슬러줘야할 돈이 $A$라 할 때의 증명이다.

 

$\mathrm{case} \; 1 \; : \; A  < 5 $   1원들로만 거슬러 주면 최적의 답이 나온다.

 

$\mathrm{case} \; 2 \; : \; A  = 5 $   5원으로 거슬러 주면 최적의 답이 나온다.

 

$\mathrm{case} \; 3 \; : \; 5 < A < 10 $   5원을 거슬러주면 $\mathrm{case} \; 1$과 같으므로 최적의 답이 나온다.

 

$\mathrm{case} \; 4 \; : \; 10 \leq A $   $A-10k\; < 10 \;\; \exists\; k $

$ A-10k$는  $\mathrm{case}\; 1, 2, 3$과 같으므로 최적의 답이 나온다.

 

최적 증명은 그리디 알고리즘에 필수적이다.

 

최소 비용 신장 트리 (Minimum Spanning Tree)

 

 도시 사이를 연결할 도로를 짓는데 도로의 총길이를 최소한으로 하는 알고리즘 그래프에서 acyclic하고 connected한 트리를 만든다. 

 

MST 적용 사례 : 고속도로, 지하철, 통신망 연결 등

 

프림 알고리즘 (prim's algorithm)

 

프림 알고리즘은 이음선의 $F$의 부분집합인 공집합과 $Y$는 ${v_1}$로 초기화한다. $Y$에서 가장 가까운 마디는 최소가중치를 가진 이음선으로 $Y$에 속한 마디를 연결하는 $V-Y$의 마디이다. $Y$에서 가장 가까운 가장 가까운 vertex를 $Y$에 추가하고, 그 이음선은 $F$에 추가한다. 같은 가중치가 두 개 이상 있으면, 임의로 선택한다. 가장 가까운 마디를 추가하는 이 과정은 $Y=V$가 될 때까지 계속한다.

 

$F := \emptyset; $    edge 집합

$Y := {v_1}; $    vertex 집합

 

while(사례 미해결) {

    Y에서 가장 가까운 V-Y에 속한 이음선을 선택;     //선택 절차와 적절성 점검
    그 마디를 Y에 추가;
    
    그 이음선을 F에 추가; 
    
    if(Y == V) 사례해결;     //해답점검
}

 

프림 알고리즘의 일정 시간 복잡도 분석 (prim's algorithm analysis)

 

$$T(n) = 2(n-1)(n-1) \in \Theta(n^2) $$

 

프림 알고리즘의 최적 증명 (prim's algorithm optimality proof)

 

비방향그래프 $G(V,E)$가 있을 때, $E$의 부분집합 $F'$이면  $F'$는 유망하다(promising)

 

만약 $Y$에 속한 마디를 $V-Y$에 속한 마디로 연결하는 이음선 중에 가중치가 최소인 이음선을 $\{e\}$라 하면, $F \cup \{e\}$는 유망(promising)하다.

 

$F$는 유망하므로, 다음 관계가 성립하는 이음선의 집합 $F'$가 반드시 존재하고,

 

$$F \subseteq F'$$

 

$(V, F')$는 최소비용 신장트리가 된다. 

 

 

$ e = (v,w)$

 

case 1)  $ e = (v, w) \in F'$

 

$F \subseteq F'$

 

$F \cup \{e\} \subseteq F'$

 

$\therefore$  $F \cup \{e\}$은 유망하다

 

 

 

 

case 2)  $e = (v,w) \notin F'$

 

$F \cup \{e\} \nsubseteq F'$

 

$F' \cup \{e\}$를 추가하면 사이클이 생기게 된다.

그렇다는 것은 ${e} = (v, w)$과 같은 가중치를 같은 ${e'} = (v', w')$이 있다는 것이다.

$F' \cup \{e\} -\{e'\}$

$F \cup \{e\} \subseteq F' \cup \{e\} -\{e'\}$ 

$\therefore$  $F \cup \{e\}$은 유망하다

 

 

위의 두 케이스에서 전부 $F \cup \{e\}$ 는 유망하다. 고로 증명이 완료되었다.

 

이제 본격적으로 프림 알고리즘이 항상 최소비용 신장트리를 만드는지 알아보자.

 

귀납법을 활용해 repeat-루프가 매번 수행 후에 집합 $F$가 유망하다는 것을 증명하면 된다.

 

귀납기초 : 공집합은 당연히 유망하다.

 

귀납가정 : repeat-루프에서 어떤 주어진 반복이 이루어진 후 그때까지 선택한 이음선의 집합인 $F$는 유망하다고 가정한다. 

 

귀납절차 : 집합 $F \cup \{e\}$가 유망하다는 것을 보이면 된다. 여기서 $e$는 다음 반복을 실행할 때 선택한 이음선이다. 그런데 이음선 $e$는 $Y$에 속한 어떤 마디를 $V-Y$에 속한 어떤 마디로 연결하는 이음선 중에서 최소의 가중치를 가지고 있기 때문에 위에서 설명한 내용에 의해서 $F \cup \{e\}$는 유망하다. 귀납 증명이 완료되었다.

 

귀납증명에 의해 이음선의 최종 집합은 유망하다. 이 집합은 신장트리의 이음선으로 구성되므로, 그 트리는 최소비용 신장트리임에 틀림없다.

 

 

반응형

 

크루스칼 알고리즘 (kruskal's algorithm)

 

각 마디마다 자신만 포함하는 $V$의 서로소 부분집합들을 만드는 걸로 시작한다. 그리고 가중치가 작은 것부터 차례로 이음선을 검사한다.(가중치가 같으면 임의로 선택한다.) 만약 어떤 이음선이 서로소 부분집합들에 있는 두 마디를 연결하면 그 이음선을 추가하고, 부분집합을 하나로 합친다.

 

$F:= \emptyset$

$V$의 서로소 부분집합 구축(각 마디마다 하나씩, 그 마디만 포함하도록 한다.)

 

$E$에 속한 이음선을 가중치가 작은 것부터 차례로 정렬

 

while(답을 구하지 못했음){

    다음 이음선을 선택;             // 선택절차
    
    if(이음선이 서로소 부분집합의 두 마디를 연결한다) {       //  적절성 검사
        부분집합을 합침;
        그 이음선을 F에 추가;
    }
    if(모든 부분집합이 하나로 합쳐졌음) {          //해답 점검
        답을 구했음;
    }
}

 

크루스칼 알고리즘의 최악 시간복잡도 분석 (kruskal's algorithm analysis)

 

단위 연산 : 비교 명령문

입력 크기 : $n$(마디의 개수), $m$(이음선의 개수)

 

1. 이음선 정렬하는데 걸리는 시간

 

최악 시간복잡도가 $\Theta (m \lg m)$인 합병정렬이 있다. 여기서 더 이상의 성능 향상은 불가능하다. 따라서 이음선을 정렬하는 시간복잡도는 다음과 같다.

 

$$ W(n) \in (m \lg m) $$

 

2. while 루프에서 걸리는 시간

 

최악의 경우 모든 이음선을 고려해야하는데 이는 루프를 $m$번 반복한다는 뜻이다. 루프를 $m$번 반복하는 시간복잡도는 다음과 같다.

 

$$W(n) \in \Theta(m \lg m) $$

 

3. $n$개의 서로소 집합을 초기화하는데 걸리는 시간 

 

초기화하는 시간복잡도는 다음과 같다.

 

$$ T(n) \in \Theta (n) $$

 

$m \geq n-1 $이므로, 서로소 집합을 정렬하고 조작하는 시간이 초기화 시간을 지배한다. 따라서 다음과 같다.

 

$$W(m,n) \in \Theta (m \lg m)$$

 

최악의 경우, 모든 마디는 다른 모든 마디와 연결되기 때문에 다음과 같다.

 

$$m = \frac{n(n-1)}{2} \in \Theta(n^2) $$

 

그러므로 최악의 경우에 다음과 같이 쓸 수 있다.

 

$$w(m,n) \in \Theta(n^2 \lg n^2) = \Theta (n^2 2 \lg n) = \Theta(n^2 \lg n) $$

 

프림(prim)과 크루스칼(kruskal) 알고리즘의 비교

 

	W(m,n)	sparse graph	dense graph
prim	$\Theta (n^2) $	$\Theta (n^2) $	$\Theta (n^2) $
kruskal	$\Theta (m \lg m) \;\;\&\;\; \Theta (n^2 \lg n) $	$\Theta (n \lg n) $	$\Theta (n^2 \lg n) $

 

마디(vertex)가 많으면 prim's algorithm을 쓰고(고밀도 그래프), 아니면 kruskal's algorithm을 쓰는 게 효율적이다.(저밀도 그래프)

 

https://kimmessi.tistory.com/97

[그래프 이론] BOJ 1197 최소 스패닝 트리

최소 스패닝 트리 문제를 구현한 코드이다. 

 

 

스케줄 짜기(Job scheduling)

 

디스크드라이브 사용자들이 기다리고 서비스를 받는데 소요되는 총 시간이 최소가 되도록 디스크 사용 스케줄을 짜는 문제나 미용사가 각각 기다리는 시간을 최소화하려고 머리 자르는 순서를 정하는 것과 같은 문제들에서 주로 쓰인다.

 

작업이 3개가 있고, 작업을 하는데 걸리는 시간은 각각 다음과 같다.

 

$$ t_1 = 5, \;\;\; t_2 = 7, \;\;\; t_3 = 4 $$

 

1, 2, 3 순서대로 스케줄을 짠다면 이 3개의 작업을 완료하는데 걸리는 시스템 내부 시간은 다음과 같다.

 

작업	시스템 내부 시간
$t_1$	5 (작업시간)
$t_2$	5 (작업 1 대기시간) + 7 (작업시간)
$t_3$	5 (작업 1 대기시간) + 7 (작업 2 대기시간) + 4 (작업시간)

 

이 스케줄에서 시스템 내부에서 걸리는 총 시간은 위에서 작업 1, 작업 2, 작업 3을 끝내는데 걸리는 시간을 모두 더해주면 된다.

 

이때, 가장 최소가 되게 하려면 작업 시간이 가장 작은 순서대로 탐욕적으로 스케줄을 짜면 된다.

 

위의 문제의 답도 [3,1,2] 순서대로 작은 순서대로 탐욕적으로 스케줄을 짜는 것이 정답이다.

 

위의 알고리즘을 의사코드로 나타내보면 다음과 같다.

 

작업시간 별로 작업을 비내림차순으로 정렬한다;

while(답을 구하지 못했음) {
    다음 작업을 스케줄에 넣는다;    //선택절차와 적절성 점검
    
    if(작업이 더 이상 없다) 답을 구했음;    //해답점검
}

 

https://kimmessi.tistory.com/103

[그리디] BOJ 11399 ATM

 

백준에서 스케줄 짜기 문제를 직접 구현한 코드이다.

 

스케줄 짜기 증명

 

작업 시간이 작은 순서대로 탐욕적으로 스케줄을 짜면 최소한의 시스템 내부의 총 시간을 쓸 수 있는지 증명해보자.

 

 여기 작업 순서 $S_1$과 $S_2$가 있다. 이때, $t_i > t_j$이면 $i > j$이다.

 

$S_1 = t_1 \; t_2 \; \cdots t_i \; t_{i+1} \cdots t_n$

$S_2 = t_1 \; t_2 \; \cdots t_{i+1} \; t_i \cdots t_n$

 

총 시스템 내부 시간은 $T_1$과 $T_2$는 다음과 같다. 이때 $m$은 그 전까지의 시스템 내부 시간이고, $n$은 그 이후의 시스템 내부 시간이다.

$T_1 = m+(m+t_i)+(m+t_i+t_{i+1})+n$

$T_2 = m+(m+t_{i+1})+(m+t_i+t_{i+1})+n$

 

여기서 $t_i < t_{i+1}$이므로 $S_1 < S_2$이다.

 

그러므로 작업 시간이 작은 순서대로 탐욕적으로 스케줄을 짜면 시스템 내부의 총 시간의 최솟값을 구할 수 있다.

 

스케줄 짜기의 일정 시간 복잡도 분석

 

여기서 알고리즘이 하는 일은 작업 시간별로 작업을 정렬하는 일 뿐이다. 따라서 시간복잡도는 다음과 같다.

 

$$ W(n) = \Theta (n \lg n)$$

 

마감시간이 있는 스케줄 짜기(Seheduling with Deadlines)

 

마감시간이 있는 스케줄 짜기 문제에서 각 작업을 끝내는데 1의 단위시간이 걸리고, 마감시간과 보상이 할당되어있다. 마감시간 전이나 마감시간에 마친다면 보상을 받고 아니면 받지 못한다. 목표는 총 보상액이 최대가 되게 작업 스케줄을 짜는 것이다.

 

예를 들어 작업, 마감시간, 보상이 다음과 같다고 하자.

 

작업	마감시간	보상
$J_1$	2	30
$J_2$	1	35
$J_3$	2	25
$J_4$	1	40

 

답을 구하는 과정

 

가장 보상이 큰 $J_4$를 선택한다. 마감시간이 지나지 않았으므로 적절하다.

그 다음 보상이 큰 $J_2$를 선택한다. 마감시간이 자났으므로 적절하지 않다.

그 다음 보상이 큰 $J_3$을 선택한다. 마감시간이 지나지 않았으므로 적절하다.

 

답은 40 + 30 = 70이 된다. 

 

위의 알고리즘을 의사코드로 나타내보면 다음과 같다.

 

작업을 보상이 큰 것부터 차례로 정렬한다;
S = {};	
while(답을 구하지 못했음) {
    다음 작업을 선택;    //선택 절차
    if(이 작업을 추가하면 S가 적절하다)    //적절성 검사
        이 작업을 S에 추가;
    if(더 이상 작업이 없다)    //해답점검
        답을 구했음;
}

 

마감시간이 있는 스케줄 짜기의 최악 시간 복잡도 분석

 

단위연산 : 작업들을 정렬할 때, $K$와 작업 $i$가 추가된 $J$를 같게 놓을 때, $K$가 적절한지 검사할 때 비교연산이 필요하므로 비교연산이 단위연산이다.

입력크기 : 작업의 수 $n$

 

작업들을 프로시저에 전달하기 전에 작업들을 정렬하는데 $\Theta (n^2) $시간이 걸린다.

for-$i$루프마다 $K$에 $i$째 작업을 추가하는데 최대한 $i-1$번의 비교연산이 필요하고, $K$가 적절한지 검사하는데 최대한 $i-1$번의 비교연산이 필요하다.

따라서 최악의 경우 시간은 다음과 같다.

 

$$\sum^{n}_{i=2} [(i-1)+i] = n^2-1 \in \Theta (n^2) $$

 

$$W(n) \in \Theta (n^2) $$

 

0-1 배낭 채우기 (0-1 Knapsack problem)

 

아이템들의 총 무게가 $W$를 넘지 않으면서 아이템의 총 값어치가 최대가 되도록 배낭에 담는 문제이다.

 

먼저 이 문제를 완전 탐색으로 풀어보자

 

완전 탐색을 이용한 풀이

 

아이템이 $n$개가 있다고 하면 각각 $n$개를 배낭에 넣을지 말지를 선택해야 하므로 시간 복잡도는 아래와 같다.

 

$$ T(n) = \Theta (2^n) $$

 

시간 복잡도가 너무 크므로 완전 탐색으로는 풀 수 없다.

그럼 탐욕적 알고리즘으로는 풀 수 있을까?

 

탐욕적 알고리즘을 이용한 풀이 

가장 쉬운 탐욕적인 전략은 가장 값어치가 높은 아이템을 먼저 채우는 것이다. 즉, 값어치가 높은 순서로 채우는 것이다.

그러나 값어치에 비해 무게가 많이 나가는 경우 좋지 않을 수 있다. 두 번째 탐욕적인 전략은 가장 가벼운 아이템부터 훔치는 것이지만, 이 전략은 가벼운 아이템이 무게에 비해서 값어치가 별로 나가지 않는 경우 좋지 않다. 이 문제들을 극복한 탐욕적 알고리즘은 무게 당 값어치가 큰 것부터 차례로 아이템을 총 용량 $W$를 초과하지 않으면 배낭에 채우는 알고리즘이다.

 

	무게	값어치	무게 당 값어치
$I_1$	5	50	10
$I_2$	10	60	6
$I_3$	20	140	7

 

무게 당 값어치로 정렬해보면 $I_1, \; I_3, \; I_2 $로 나열할 수 있다.

배낭이 감당할 수 있는 최대 무게가 30이라고 할 때, 탐욕적 방법으로 풀어본다면 $I_1, \; I_3$을 배낭에 넣는 방법으로  풀어낼 수 있다. 하지만 이것은 최적의 해답이 아니다. 최적의 해답은 $I_2, \; I_3$를 배낭에 넣는 방법이므로 무게 당 값어치로 탐욕적 탐색을 하는 방식으로도 풀 수 없다.

 

그렇다면, 아이템을 조각내어 배낭의 남은 부분만큼 채울 수 있다고 가정한다면 어떨까?

 

위의 $I_1,\; I_3$를 넣은 배낭에서 5정도의 무게가 남으므로 $I_2$를 절반으로 나눠서 배낭에 넣는 방법이다. 

그러면 총 값어치는 50+140+60(5/10) = 220이다. $I_2, \; I_3$를 넣었을 때의 총 무게가 200이므로 최적의 해답을 얻어낼 수 있다. 하지만 아이템을 나눌 수 없는 상황에서는 풀 수 없다.

 

앞에서 완전 탐색과, 탐욕적 알고리즘으로는 원하는 답을 구할 수 없었다. 

새로운 방식으로 풀어보자.

 

동적계획법을 이용한 풀이

 

https://kimmessi.tistory.com/76

[DP] BOJ 12865 평범한 배낭

위의 문제를 푼 방식대로 동적계획법을 구현하면 된다.

 

배낭 채우기 문제의 동적계획법 최악 시간 복잡도를 구해보자

 

계산해야되는 엔트리가 행이 낮아질수록 갯수만큼 선택하는 가지수가 커지므로 2의 지수 크기만큼 커진다. 

그러므로,

 

$$T(n) = 2^{n-1} + 2^{n-2} + \cdots + 2^0 = 2^n -1 \in \Theta (2^n) $$

 

완전 탐색의 시간 복잡도와 똑같다.

그러므로 우린 새로운 알고리즘으로 다시 시도해볼 필요가 있을 것 같다.