Algorithm : Greedy Algorithm 2

1. Dijkstra algorithm

• single source shortest path problem
• 가중치가 있는 방향성 그래프에서 시작 정점에서 다른 모든 정점으로 가는 최단경로 구하기
• 순서
  • 시작 노드를 정한다.
  • 시작 노드에서 가중치가 작은 정점을 Y에 추가한다.
  • Y에 노드가 추가되면 연결된 노드의 가중치를 update 해준다.
  • 모든 노드가 Y에 추가될 때 까지 반복
• pseudo code

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 = None
    
    for(i = 2; i <= n; ++i)
    {
    	touch[i] = 1;
        length[i] = W[1][i];
    }
    repeat(n-1 times)
    {
    	min = inf;
        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;
    }
}

• 중요 부분
  • 새로운 노드가 추가된 경우, 기존에 연결되어있던 거리보다 더 작은 거리인지를 확인하고 노드의 가중치를 업데이트 해야한다
  • length[vnear] + w[vnear][i] < length[i]
• 분석
  • $T(n) = 2(n-1)^2 \in \Theta(n^2)$
  • 힙으로 구현한 경우 $\Theta(mlg\ n)$
  • 피보나치 힙으로 구현한 경우 $\Theta(m+nlg\ n)$

2. Huffman code

• 최적의 이진 코드를 만들기 위한 방법
• 각 빈도수의 합이 최소가 되는 것을 찾아서 트리 구성하기

3. 0-1 knapsack problem

• 무게가 제한된 가방에 최대한의 이익으로 물건을 담기

greedy

1) 비싼 물건부터 넣기
2) 가벼운 것 부터 넣기
3) 무게당 가치가 가장 높은 것 부터 넣기

• 세 경우 모두 최적의 경우가 아니다.
• 물건의 일부를 잘라서 넣는 방법 선택!

동적 계획법

$P[i][w] = max(P[i-1][w], p_i+P[i-1][w-w_i])$

4. 상호 배타적 집합의 처리

• 상호 배타적 집합이란 각 집합간의 교집합이 없다는 의미이다.

linked list

• make_set -> O(1)
• find -> O(1)
• union -> $O(m^2)$
  • union의 단점 극복하기 위해 weighted union heuristic 존재
  • $O(nlgn)$

array

• list와 동일

tree

• 가중치 x

• 가중치 o

• find

• path compression