무기력한 제이미

• 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로 하는 부분 트리에 있는 단말 노드들의 빈도수의 합 

생성된 이진 트리는 다음과 같은 표를 제공한다.

고정 길이 코드를 이용하면 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. 우선 빈도수가 적은 순서대로 정렬한 후 시작한다. 

1. 각 기호에 대해 리프 노드를 작성하여 우선 순위 큐에 추가한다.

2. 대기열에 둘 이상의 노드가 있는 동안 :

   1. 대기열에서 가장 높은 우선 순위의 두 노드를 제거한다.

   2. 이 두 노드를 자식 노드로하고 두 노드의 빈도의 합과 같은 빈도로 새 내부 노드를 만든다.

   3. 새 노드를 큐에 추가함.

    

3. 나머지 노드는 루트 노드이며 허프만 트리가 완성된다.

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에 의해 항상 분수 배낭 문제에 대한 최적의 해를 구할 수 있다.

(나중에 증명해볼 것!)

최소 스패닝 트리(Minumum Spanning Tree - MST)란,

1. 그래프의 모든 정점이 간선으로 연결되어 있고

2. 그래프 안에 사이클이 포함되지 않은

스패닝 트리 중 최소 cost의 합으로 만들어진 신장 tree를 말한다. 

Kruskal Algorithm 은, 최소 스패닝 트리를 구하는 방법 중 하나로, 

각 단계에서 그래프의 모든 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)가 된다.

Example 1) U={0,1,2,...,9}이라고 할 때, 다음 연산을 하시오. 

- init(10) : S0={0}, S1={1}, S2={2}, ... , S9={9}

- find(1) = 1, find(7) = 7

- union(1,7), union(2,5), union(0,3) : S0={0,3}, S1={1,7}, S2={2,5}, S3={4}, S4={6}, S5={8}, S6={9}

- 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할 경우, 하나를 다른 한 쪽의 자식으로 넣어서 두 트리를 합치게 된다.

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 법칙을 사용하여 구성해보도록 한다.

(node가 8개이고, h는 최대 log_2 (8)=3이 될 것이다. )

wUnion(0,1), wUnion(2,3), wUnion(4,5), wUnion(6,7) 

wUnion(0,2), wUnion(4,6)

wUnion(0,4)

그림으로만 봐도 직관적으로 이해가 될 것이다. 처음에, 노드의 개수가 같으므로 첫번째 트리가 부모가 되게끔 하였다.

그 후, 계속해서 tree의 개수가 더 작은 쪽(같을 때는 왼쪽 노드들)에 트리를 포함시킨다.

이 때, find(7)=3을 했을 때 worst case이고, height와 같다. 

(1) 이제 node의 개수 대신 tree의 height를 이용할 수 있다.

(2) find(x) 연산은 root를 찾기 위해 부모를 타고 올라간다. 

만약 이 때, root node까지 순회하다가 방문한 각 node들이 직접 root를 가리키도록(포인터) 갱신하도록 한다면,

모든 노드들은 같은 대표 노드를 공유하게 될 것이다. = path compression (amortized) 

• 정의 및 설명

다익스트라 알고리즘은 주로 도로 교통망 같은 곳에 나타날 수 있는

"그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘"이다. 

다익스트라 알고리즘은 매번 주어진 상황에서 가장 좋은 경로를 선택함으로써 만들어가는 탐색 방법인 greedy algorithm(욕심쟁이 알고리즘)의 하나이기도 하다.

위의 그림을 통해 대략적으로 알고리즘을 이해할 수 있다.  

노드 1과 노드 2 사이의 최단 경로를 찾는 알고리즘이라 할 때, 가장 낮은 값을 가진 노드 중 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산 후, 더 작을 경우 인접 거리를 업데이트한다.

위 그림을 보면 다음 방문할 예정의 노드는 회색으로, 이미 방문하여 계산을 완료한 노드는

빨간색으로 표현한 것을 확인할 수 있다.

그림에 대해 더 자세히 풀어쓰자면, 시작하는 출발 노드 1 로부터 가장 가까운 정점은 2이므로 2를 방문한다.

2에서 이미 방문한 노드인 1을 제외하고 가장 가까운 정점은 3이므로 3을 방문한다.

이 때, 1->2->3으로 간다면 가중치가 10+7=17 이지만, 1->3으로 간다면 9이므로, 노드 3의 거리를

둘 중에 더 작은 9로 계산한다. (이 비교 과정을 매번 노드에 방문할 때마다 거쳐야 한다.)

이 과정을 반복하여 다음 방문할 노드를 정하고, 모든 노드의 방문이 끝나면

해당 방문 순서가 최단경로가 되고 마지막 노드의 가중치가 총 최단경로의 거리가 되는 것!

다익스트라 알고리즘에 대한 전체적인 메커니즘을 이해했으니

이제 본격적으로 어떻게 동작되는지 코딩을 통해 알아보기로 하자. 

• 동작과정

위에서 사용한 예시를 그대로 이용하여 설명해보자. 

위와 동일하게 처음 시작 노드는 1, 마지막 목적지는 5로 가정한다.

처음에 노드 1에서 이동할 수 있는 비용은 아직 모두 무한대(inifinity)로 설정한다. 

아직 다음 노드를 방문하지 못했으므로, 모두 무한대로 설정된 상태이다.

출발 노드 1번은 0으로 초기화한다. 노드 1과 인접해있는 노드 2, 노드 3, 노드 6의 비용을 각각 갱신한다.

현재 배열에 저장된 값 중 가장 작은 비용을 가진 노드는 2번이므로, 2를 선택한다. 

다음에 방문한 노드 2와 인접한 노드 3, 4의 거리를 갱신할 수 있다. 

이 때, 노드 3의 기존 cost는 9이고, 2까지의 최단경로와 2->3의 cost를 더한 값은 7+10=17이다.

더 작은 것을 선택해야 하므로 해당 배열 값은 그대로 내버려둔다.

노드 4의 거리는 1->2->4로 22가 새롭게 갱신된다. 

이미 방문한 노드를 제외한 노드들 중 cost가 가장 적은 노드 3을 방문한다.

노드 3과 인접한 4와 6 노드를 갱신할 수 있다.

노드 4는 기존의 cost 22보다 1->3->4, 즉 9+11=20 이 작기 때문에 더 작은 20으로 갱신한다.

노드 6 또한, 기존의 cost 14보다 1->3->2를 통한 cost 9+2=11이 더 적기 때문에 11로 갱신한다.

방문하지 않은 노드 4,5,6 중 가장 적은 cost를 가진 노드 6을 방문한다. 

방문하지 않은 노드 5에 대한 가중치를 갱신할 수 있다. 

이로써, 출발 노드 1번에서 도착 노드 5번까지 도달하였으므로 최단경로를 구한 것이 된다. 

또한, 위의 배열은 출발 노드로부터 모든 노드까지 도달하는 데 걸리는 최소 비용 배열이 된다. 

모든 노드를 방문하면 다익스트라 알고리즘이 종료된다. (= infinity에 해당하는 노드가 없음)

Time Complexity

T(n) = 2(n-1)(n-1) = O(n^2)