정수로 구성된 수열 S=(a1, a2, ... , an)가 주어졌을 때, S의 부분 수열이란 S에서 임의로 k개의 원소를 순서적으로 선택한 수열로서 인덱스가 1 ≤ i1 < i2 < ... < ik ≤ n 의 조건을 만족하는 수열(ai1, ai2, ... , aik) 을 말한다.
증가 부분 수열(increasing subsequence)이란, 이러한 부분 수열 중에 ai1 < ai2 < ... < aik 의 조건을 만족하는 수열이다.
최장 증가 부분 수열 (longest increasing subsequence - LIS) 문제는 이러한 증가 부분 수열 중 길이가 가장 긴 수열과 그 길이를 구하는 것이다.
예를 들어서, S={25,12,18,6,13,16,29,17} 에서 최장 증가 부분 수열 중 하나는 {12,13,16,17}이며 길이는 4이다. 물론, 길이가 4인 다른 부분 수열들이 존재할 수도 있다. {12,13,16,29} 도 길이 4를 가진 최장 증가 부분 수열이다.
이 문제에서는, 최장 증가 부분 수열이 여러 개가 있더라도 임의의 답을 하나만 구한다고 가정한다.
Q. 만약 우리가 주어진 수열의 모든 부분 집합으로 구성된 수열을 다 고려하고, 각 수열이 증가 부분 수열인지를 체크하여 증가 부분 수열들 중에서 가장 긴 부분 수열을 고른다면? (exhaustive search)
A. 원소의 개수가 n인 수열의 부분 집합 개수는 적어도 2^n개이므로, 일일이 다 구한다면 O(2^n)의 이상의 시간이 걸림.
동적 계획법
그렇다면 이 문제를 동적 계획법으로 해결하고자 한다. 그러기 위해서 우선 재귀적인 공식을 수립해야 한다.
hi 를 원소 ai로 끝나는 최장 증가 부분 수열의 길이라고 정의하자.
그렇다면, 우리가 원하는 최장 수열 증가 부분 수열의 길이 h는 a1로 끝나는 최장 증가 부분 수열의 길이 h1, a2로 끝나는 최장 증가부분 수열의 길이 h2, ... , an으로 끝나는 최장 증가 부분 수열의 길이 hn 중 가장 큰 값이 될 것이다.
가상적인 아주 작은 값 a0이 있다고 가정하면, 다음과 같이 되기 때문에
최장 증가 부분 수열의 길이는 아래와 같다.
간단한 예시를 보며 더 자세히 알아보도록 하겠다. S= {9,5,2,8,7,3,1,6,4}
i
0
1
2
3
4
5
6
7
8
9
수열 ai
- ∞
9
5
2
8
7
3
1
6
4
길이 hi
0
1
1
1
2
2
2
1
3
3
전 값 pi의 인덱스
2
2
3
6
6
우리가 구하는 최장 증가 부분 수열의 길이는 3이고, 그 수열은 (2,3,6), (2,3,4)가 될 것이다. (전 값의 인덱스를 따라감)
각 hi를 구하기 위해서는, ai와 그 앞에 있는 (i-1)개의 원소들 ai-1,...,a1과 비교해야 하므로전체 시간 복잡도는 O(n^2)
임을 알 수 있다.
int longest (int s[]) {
int i,j;
int h[MAX]={0,} ,p[MAX]; //h는 부분 수열의 길이, p는 전 값의 index
int max=0,index;
for(i=1;i<MAX;i++){
for(j=0;j<i;j++){
if(s[i]>s[j] && h[i]<h[j]+1){
h[i]=h[j]+1;
p[i]=j;
}
for(i=1;i<MAX;i++){ //최대 부분 수열의 길이 찾기
if(max<h[i]){
max=h[i];
index=i;
}
int lis[MAX]; // 최대 부분 수열을 저장하는 배열
i = max;
while(index!=0) {
lis[--i]=s[index];
index=p[index];
}
printf("longest increasing subseq");
for (i=0;i<max;i++) printf("%d ", list[i]);
printf("\n");
return max;
}
공통점 : 두 전략 모두 주어진 문제를 크기가 작은 여러 개의 부분 문제로 분할하여 부분문제들의 해를 구한 후, 그 해들을 결합하여 원래 문제에 대한 해를 구한다.
차이점 : 분할 정복 방식은 문제를 크기가 작은 부분 문제로 분할 후, 그 부분 문제를 독립적으로 해결한다. 그 후 그 해들을 결합하여 원래 문제의 해를 구한다. 또한, 답을 얻을 수 있는 최소 단위까지 내려가는 Top-down(하향식) 방법이다.
하지만 동적 계획법은, 부분 문제를 해결하여 그 해를 테이블에 저장한다. 그 후 다시 그 부분 문제를 풀어야 할 때 다시 풀지 않고 테이블을 저장된 결과를 사용한다. 접근법은 Down-top(상향식) 방법이다.
따라서, 분할 정복 방식에서는 서로 공유되는 같은 부분 문제가 있다고 하더라도 독립적으로 반복적인 계산을 하지만, 동적 계획법에서는 이러한 반복적 계산을 피할 수있으므로 아주 효율적으로 문제를 풀 수 있다.
Greedy algorithm과 동적계획법
동적 계획법은 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이다. 이러한 단점을 극복하기 위해 greedy algorithm이 등장했다. 차량 정체 구간에서 A->B로 가는 가장 빠른 경로를 찾는다고 하자. 동적계획법을 사용한다면 우리가 갈 수 있는 모든 상황과 교통 정체를 감안하여 최적의 경로를 찾아낸다. 반면 Greedy algorithm을 사용한다면 순간 순간 locally optimal한 경로를 찾아줄 것이다.
Greedy algorithm은 항상 최적의 해를 구해주지는 않지만, 최소 스패닝 트리, fractional knapsack problem 등 여러 문제에서 최적해를 구할 수 있음이 이미 입증되었다. 하지만 동적계획법을 사용하면 최적의 해가 보장된다는 장점이 있다.
동적계획법 설계
문제의 해를 구할 수 있는 재귀적인 성질을 설정한다.
상향식 접근 방법에 의해 크기가 작은 문제를 먼저 해결한 후 크기가 큰 문제를 해결한다.
크기가 큰 문제의 해결을 효율적으로 하기 위해 크기가 작은 문제의 해는 table에 저장한다. (같은 크기의 문제의 해를 다시 계산하는 과정을 피하기 위해서)
이항 계수
n개의 물건에서 중복을 허락하지 않고 k개를 꺼내는 조합의 수가 바로 (n k) 이다. 이를이항 계수라고 부른다.
이항 계수를 원래의 방법대로 구하면, n! 값과 k! 값을 계산해야 하기 때문에 n, k 값이 조금만 커지더라도 값을 구하기가 매우 어렵다. 따라서, 아래와 같이 재귀의 성질을 이용하여 값을 구한다고 하자.
int bin(int n,k){
if (k==0 || k==n)
return 1;
else
bin (n-1, k-1) + bin (n-1, k);
}
하지만, 위에서 언급한 것과 같이 위 알고리즘은 각 재귀 호출마다 같은 부분 문제들을 풀어야 한다. = 매우 비효율적!
예를 들자면, bin(n-1,k) 값을 구하려면 bin(n-2,k-1)값과 bin(n-2, k) 값이 필요하고
bin(n-1,k-1)값을 구하려면 bin(n-2,k-2)값과 bin(n-2,k-1)값이 필요하다.
이와 같이, 각 재귀 호출은 서로 독립적으로 계산을 해야 하기 때문에 수행시간이 늘어난다! (중복 계산때문에)
이런 식으로 한다면, B[i][j]의 값을 구하기 위해 필요한 모든 값들이 이미 배열 B에 저장되어 있기 때문에
한 번의 덧셈 연산에 의해 쉽게 계산할 수 있다. 결론적으로, B[n,k]의 값이 우리가 원하는 값인 (n k)가 된다!
이 과정은 파스칼의 삼각형을 만들어가는 과정과 유사하다.
int bin(int n, int k){
int i,j;
int B[MAX][MAX]; // 배열 B 생성한다.
for (i=0;i<=n,i++){
for (j=0;j<=min(i,k);j++){
if (j==0 || j==i) B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];
return B[n][k];
}
data compression : 데이터 파일을 encoding하는 효율적인 방법을 찾는 것. (데이터 압축)
data transmission : 데이터 파일을 전송하는 효율적인 방법을 찾는 것. (데이터 전송)
허프만 코드 : 파일을 저장하기 위한 방법으로, 이진 코드(binary code)가 가장 많이 쓰인다.
이진 코드 : 파일의 각 문자를 소위 codeword라고 부르는 유일한 비트 스트링으로 대응시켜 표현한 것.
- fixed-length binary code (고정 길이 이진 코드)
각 문자를 같은 길이의 비트 스트링으로 표현한다. 예를 들자면, 2-bit 짜리 문자의 결합이 {a,b,c}일 때 이를 나타내면
a : 00 b : 01 c : 11
파일 ababcbbbc 를 코드화하여 나타낸다면
000100011101010111 (18 bits) 이 된다.
- variable-length binary code (가변 길이 이진 코드)
각 문자를 나타내는 비트 스트링의 길이가 다를 수 있다. (어떤 문자는 1비트, 다른 문자는 2비트 등)
a : 10 b : 0 c : 11
파일 ababcbbbc를 코드화하여 나타내면
1001001100011 (13bits)이 된다. 고정 길이를 사용했을 때보다 전체 필요한 비트 수가 줄어든다!
이와 같이, 파일이 주어졌을 때 기본 구성 요소인 각 문자를 어떤 이진 코드로 나타내는 것이
파일을 저장할 때 공간이 가장 적게 필요한지 찾아내는 문제를 최적 이진 코드 문제라고 한다.
이러한 최적 이진 코드 문제를 greedy algorithm으로 풀 수 있는 한 가지 방법이 허프만의 알고리즘이다.
허프만의 알고리즘에 대해 알아보기 전에, 먼저 prefix code에 대해 설명한다.
prefix code는 앞자리 부호, 즉 앞에 붙이는 한 자리 이상의 문자를 말한다.
만약, variable-length binary code가 다음과 같이 구성되어 있다고 하자.
a : 010 b : 1 c : 01 d : 11
이 때, 파일 bbabcbbbcd를 코드화해서 나타내면 110101011110111 이 된다.
하지만, 이 경우 이진 코드를 보고 파일을 복원한다고 했을 때,
다른 추가적인 정보 없이는 두 비트 11이 d인지, bb인지 혹은 중간에 나오는 0101이 cc인지 ab인지 구별할 수가 없다.
따라서, 이를 구별하기 위해서 어떤 문자의 이진 코드가 다른 문자의 이진 코드의 앞부분, 즉 prefix가 되어서는 안된다!
아래의 예시를 보면서 이를 이해해보자.
a : 010 b : 1 c : 00 d : 011
이진 코드를 살펴보면 b의 코드인 1은 a, c, d를 나타내는 prefix가 아니고, c의 코드인 00도 a, d의 prefix가 아니다.
따라서, 이러한 binary 코드는 prefix 코드의 성질을 만족한다.
이제 모호성이 없기 때문에 쉽게 복호화(decode)할 수 있을 것이다.
위와 같이, 각 문자를 복호화하는 과정을 나타내기 위해서 이진 트리를 이용하면 쉽게 표현될 수 있다.
각 단말 노드 : 그에 대응하는 문자
단말 노드의 숫자 : 대응되는 문자의 빈도수
내부 노드의 숫자 : 그 노드를 root로 하는 부분 트리에 있는 단말 노드들의 빈도수의 합
생성된 이진 트리는 다음과 같은 표를 제공한다.
a
b
c
d
e
f
fixed length codeword
000
001
010
011
100
101
variable length codeword
0
101
100
111
1101
1100
frequency (*1000)
45
13
12
16
9
5
고정 길이 코드를 이용하면 6자를 표현하기 위해 3비트가 필요하다. 전체 frequency의 합은 100이기 때문에 3*100*1000=300000. 따라서, 전체 파일을 코딩하려면 300,000비트가 필요!
하지만, 가변 길이 코드를 사용한다면, 빈번한 문자에는 짧은 codeword를 부여하고, 빈번하지 않은 문자에는 긴 codeword를 부여하여 더 효율적으로 수행할 수 있을 것이다. 계산해보면, 45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224,000 비트이고, 이는 무려 메모리의 25%를 절약할 수 있다!
주의 ! 이때, prefix code를 고려해서 구현한다. abc를 구현한다면 0.101.100 = 0101100 이런 식으로 연결을 하여 구현.
0101100을 디코딩할 때, a.b.c 이런 식으로 고유한 문자를 매칭할 수 있기 때문에 혼동이 없다.
각 문자에 대한 이진 코드는 root로부터 각 단말 노드까지 가는 경로에 의해 표현된다.
왼쪽 자식 노드로 가면 0, 오른쪽 자식 노드로 가면 1이고, 내부 노드는 항상 자식 노드가 2개이다.
이처럼 이진 트리 T를 생성하여 전체 비트 수를 최소화하는 욕심쟁이 알고리즘이 허프만 알고리즘이다.
0. 우선 빈도수가 적은 순서대로 정렬한 후 시작한다.
각 기호에 대해 리프 노드를 작성하여 우선 순위 큐에 추가한다.
대기열에 둘 이상의 노드가 있는 동안 :
대기열에서 가장 높은 우선 순위의 두 노드를 제거한다.
이 두 노드를 자식 노드로하고 두 노드의 빈도의 합과 같은 빈도로 새 내부 노드를 만든다.
새 노드를 큐에 추가함.
나머지 노드는 루트 노드이며 허프만 트리가 완성된다.
typedef struct node{
struct node *left; // left child
struct node *right; // right child
}node
*node huffman (int n,node PQ){
node *a, *b, *r;
int i;
for (i=1;i<n;i++){
remove(PQ,a);
remove(PQ,b);
r->left=a;
r->right=b;
r->freq=a->freq+b->freq;
insert(PQ,r);
}
remove(PQ,r);
return r;
}
코드 설명 : 우선순위 큐에서 노드를 두 개 제거하고, 다시 우선 순위 큐에 제거한 노드 두 개를 합친 노드 r을 삽입한다.
이 과정을 반복하여 나온 허프만 트리의 루트를 반환한다.
시간 복잡도
우선순위 큐로 heap이 사용된다면, 초기에 힙을 구성하는 데 O(n) 시간이 걸리고, 최솟값 제거 및 새로운 원소의 삽입 등 heap 연산은 O(logn) 시간이 걸린다. for 루프는 n-1번 수행되기 때문에 알고리즘의 전체 수행 시간은 O(nlogn)이 된다.
물건 n개의 집합 S={1,2,...,n} 와 W={w1,w2,...,wn}, P={p1,p2,...,pn}가 주어져 있다.
배낭에 이러한 물건들을 넣어 시장에 판다고 할 때, 얻을 수 있는 최대 이윤을 구한다.
wi(>0) : 각 물건 i의 무게
pi(>0) : 물건 i를 시장에서 팔았을 때 얻는 이윤
M : 배낭의 크기(사람이 짊어질 수 있는 최대 무게)
이 문제에서 만약 물건을 쪼갤 수 있는 경우면 분수 배낭 문제(Fractional Knapsack)라 하고,
물건을 쪼갤 수 없는 경우0-1 배낭문제라고 한다.
결론부터 말하자면 이 문제는 최적화, 즉 Optimization 문제인데,(1) 분수 배낭문제는 greedy algorithm으로 다항 시간에 풀 수 있고(2) 0-1 배낭문제는 dynamic programming으로 의사 다항 시간(밑에서 자세히 설명함. NP-완전문제)에 풀 수 있다. 두 전략을 사용하여 푸는 방법을 모두 소개하고자 한다.
(1) Greedy algorithm - fractional knapsack problem
우선, greedy algorithm은 눈 앞에 있는 최대 이익을 locally optimal하게 고르는 알고리즘이다. 따라서, 항상 optimal하다고 보장할 수 없다는 것을 알아두자. ( 0-1 knapsack 문제의 경우 greedy algorithm을 사용하면 항상 최적화 문제를 구할 수 없다. 반례 有 )
int fractional_knapsack (int num, int weight[], int profit[], float x[], int capacity){
int cu=capacity; // 남아 있는 배낭 크기
int max_profit=0; // 최대 이익
int i; // index
for (i=1;i<=num;i++){
if(weight[i]>cu) break;
x[i]=1.0;
cu=cu-weight[i];
max_profit=max_profit+profit[i];
}
if (i<=num){
x[i]=(float)cu/weight[i];
max_profit=max_profit+profit[i]*x[i];
}
return max_profit;
}
위의 알고리즘을 보면서 이해해보도록 한다. X는 solution 배열, cu는 배낭의 남은 용량을 나타내는 변수이다.
해당 알고리즘에서 i는 단위 무게당 이윤의 내림차순으로 정렬되어 있다고 가정한다. (pi/wi>=pi+1/wi+1)
a) 만약 물건의 무게가 남아 있는 배낭 크기보다 크면 loop는 종료된다.
b) 배낭에 더 넣을 수 있는 경우
x[i]=1.0; // 현재 물건을 배낭에 전부 채운다.
cu=cu-weight[i] 값으로 남은 배낭의 크기를 갱신한다.
max_profit값 또한 새로 갱신한다.
c) 배낭에 넣을 수 있는 물건이 없을 때
x[i]=(float)cu/weight[i]; 현재 물건을 남은 배낭의 비율만큼 채운다.
알고리즘 fractional_knapsack에 의해 항상 분수 배낭 문제에 대한 최적의 해를 구할 수 있다.
각 단계에서 그래프의 모든 edge 중에서 최소의 가중치를 갖는 edge를 선택하는 greedy algorithm 이다.
시작 정점을 정하고 가까운 정점을 선택하면서 트리를 구성하는 프림 알고리즘과 달리,
크루스칼 알고리즘은 시작점을 정하지 않고 최소 cost의 간선을 차례대로 대입하면서 트리를 구성하기 때문에
cycle check 를 꼭 해주어야 한다! (프림 알고리즘은 cycle이 생기지 않는다. )
알고리즘을 개괄적으로 이해하기 위해, 예제를 풀어보자.
출처 : 위키피디아
0. 다음은 우리가 풀어야 할 그래프이다.
변 옆의 숫자는 가중치를 가리키고, 현재 edge에 아무것도 포함되지 않음.
1. 가장 가중치가 작은 변(AD or CE 중 아무거나)을 선택하여 edge에 포함시킨다.
2. 이제 CE 변이 가장 짧은 변이므로, edge에 포함시킨다.
3. 같은 방식을 반복하여 고르면 다음 변은 DF이므로 edge에 포함시키고,
그 다음으로 가장 짧은 변은 AB와 BE인데 임의로 AB를 고른다. (cycle만 없으면 상관없다!)
BD는 cycle을 구성하기 때문에 빨간색으로 표시하였다.
4. 다음으로 가장 짧은 변은 BE이다. edge에 포함시킨다. BC와 DE, EF가 cycle을
구성하므로 빨간색으로 표시하였다.
5. 끝내, 빨간색이 아닌 edge 중 더 작은 cost를 가진 edge EG를 연결하며 알고리즘이 종료된다.
edge의 개수가 정점 V -1 이 되었으므로 MST 가 완성되었다!
step 0) 모든 edge를 끊어서 가중치 작은 순서대로(오름차순) 정렬한다. step 1) 정렬된 간선을 순서대로 선택한다. step 2) 만약 edge가 서로소 부분집합인 두 개의 정점을 잇는다면, 두 개의 부분집합을 merge하고 해당 edge를 solution에 추가한다. step 3) 모든 정점들의 부분집합이 merge될 때까지 step 1 ~ step 2 과정을 반복한다
이처럼 high-level 알고리즘을 보면 어렵지 않으나, 코드로 구현하기 위해서는
cycle을 확인할 때 Union-Find(Disjoint-Set) 자료구조를 이용해야 한다.
위의 알고리즘에서 서로소 집합에 있는 2개의 정점을 잇는다는 것은 cycle이 없다는 것을 의미한다.
이에 대한 자세한 설명을 이어서 해보도록 하자.
Union-Find Operations for disjoint sets. (서로소 집합 자료 구조)
서로소 부분 집합(disjoint - set)으로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다.
이 자료구조에서 사용하는 연산은 다음과 같은 세가지로 나누어진다.
* U={0,1,2,...,n-1} 이라는 집합이 있다고 가정하고, U에 속하며 서로 전부 서로소인(disjoint) 부분집합 S0,S1,...,Sk-1 이 있다고 가정한다.
-init(n): 원소 한개를 가진 n개의 집합들로 초기화한다.
-find(x): 어떤 원소가 주어졌을 때, 이 원소가 속한 집합을 반환한다. 주로 "대표"하는 원소를 반환하므로, find값을 비교하면 이 원소들이 서로 같은 집합에 속하는지를 판단할 수 있다.
-union(x,y): 두 개의 집합을 하나의 집합으로 합친다. x와 y집합에 대해 이 연산을 하면, find(x)=find(y)가 된다.
- find(7) = 1, find(3) = 0 (바로 위의 union을 한 후 find를 했을 경우)
Example 2) Connected Components (점진적으로 연결된 요소)
왼쪽의 GIF를 보자.
10개의 원소에 대해 5번의 union을 한 후, object[0]과 object[7]은 연결되지 않았고 object[8]과 object[9]는 연결이 되어있다.
그런데 4번의 union을 더 한 후, object[0]과 object[7]은 연결이 되어있다.
이처럼, 서로 disjoint했던 object의 각 집합은 union을 한 후 연결 상태로 바뀌게 된다.
다음과 같이, 점 p에서 q까지 grid point(교차점)를 통해 갈 수 있는 경로를 알아보고 싶다고 하자. 이 때, 위에서 배운 함수 세 가지를 응용하여 값을 구한다. 이러한 과정을 컴퓨터가 연산을 통해 계산한다.
- union(u,v) : 두 개의 grid point를 잇는다.
- find(u) : grid point u를 가진 set을 찾는다.
- path(u,v) : u와 v point를 잇는 경로가 있는가?
Kruskal Algorithm에 활용한 union - find
이제, 실제 알고리즘을 구현해보면서 이해해보도록 한다.
void kruskal (int n, int m, set_of_edges E, set_of_edges &F){
index i,j;
set_pointer p,q;
edge e;
Sort the m edges in E by weight in non-decreasing order; // 오름차순으로 간선 정렬
F={0};
init(n); /* Initialize n disjoint subsets. */
while (number of edges in F is less than n-1){ //간선의 개수=정점의 개수-1까지가 최대
e=edge with least weight not yet considered;
i,j=indices of vertices connected by e;
p=find(i);
q=find(j);
if (!equal(p,q)){
union(p,q);
add e to F;
}
}
}
출처 : 위키피디아
← 왼쪽의 GIF를 보면 더 잘 이해할 수 있다.
오름차순으로 정렬된 edge를 순서대로 선택해나가고, 이 edge와 연결된 정점의 index를 각각 i와 j라고 한다. 각각의 정점을 init(n)함수를 통해 원소 1개짜리 서로소 집합인 부분집합으로 나누고, 이를 계속해서 union(p,q) 함수를 통해 병합해나간다. 정점이 전부 병합될 경우 while문은 종료된다.
우선, find(i)와 find(j) 값이 같다는 건, (i,j) edge를 추가할 경우 cycle이 생긴다는 뜻이다. 더 자세하게 말하자면, find 함수의 값은 해당 부분집합의 대표 값을 말한다. 따라서, 이 두 개의 값이 같다는 건 서로 같은 집합에 속한다는 것을 말한다. (두 부분집합을 병합한다면 cycle이 생기게 될 것이다!)
왼쪽의 GIF에서 보여지는 자료구조는 "up-tree" 구조인데, tree의 root가 대표값으로 간주된다. (find(x)연산과 일맥상통) / root 노드가 서로 다른 집합끼리 union할 경우, 하나를 다른 한 쪽의 자식으로 넣어서 두 트리를 합치게 된다.
index
0
1
2
3
4
parent
-1
0
0
1
3
find함수는 대표 root가 나올 때까지 따라가는 함수인데, 위의 표와 같이 index를 계속 따라가서
parent가 -1 값을 가질 때까지 따라가게 된다. (root는 parent 값 -1)
root를 추적하는 과정에서, 해당 tree의 높이만큼 따라가게 될 것이라는 것을 알 수 있다.
int find(int i){ //parent[i] 만날 때까지 계속 거슬러 올라간다.
for (;parent[i]>=0;i=parent[i]);
return(i);
}
void union(int i,int j){ // 병합
parent[f(i)]=f(j);
}
Time complexity
- Kruskal Algorithm 최악의 경우는 edge의 개수 m이 n(n-1)/2개일 경우이다.
W(n) = O(mlogm) = O(n^2logn)
- Find & Union
최악의 경우는 트리가 한 줄로 이루어졌을 때, (비대칭 트리, 연결리스트의 형태처럼 됐을 때) 즉, 모든 트리의 노드가 바로 뒤 노드를 가리키고 있을 때이다.
union(0,1)만 한 뒤 find(0) 연산 시 : for문 한 번만 돌면 된다.
union(0,1), union(1,2)를 한 뒤 find(0) 연산 시 : for문 두 번 돌면 된다.
union(0,1), union(1,2), union(2,3)를 한 뒤 find(0)연산 시 : for문 세 번 돌면 된다.
...
이런 식으로 n번 연산을 할 경우, find 연산 시 맨 끝의 root 노드를 찾기 위해 모든 부모 링크를 따라가야 하는 비효율성이 발생한다.
-> union() : W(n) = O(n^2)
-> find() : W(n) = O(n^2)
Weighted union tree (가중치 유니온 법칙)
위의 find & union 변질 트리 생성 문제를 더 효율적으로 해결하기 위해, 가중치를 고려한다.
Rule : wUnion(i,j)에서 트리 i 보다 트리 j가 노드 수가 더 적다면, i가 j의 부모가 되게 한다. 반대의 경우 j가 i의 부모가 되게 한다. 노드의 수가 많은 트리가 더 적은 트리의 parent(root)가 되게 한다. (노드 수에 가중치를 둠)
위 과정처럼, tree는 더 많은 쪽의 노드를 가진 tree에 속하게 된다.
h(T)는 tree T의 높이를 말한다. 다음과 같이, h(T)는 log_2 (n)만큼의 최대값을 가진다.
간단한 예시를 들어보자.
n=8인 tree T의 높이가 최대가 되게끔 가중치 union 법칙을 사용하여 구성해보도록 한다.
