Algorithm : Greedy Algorithm 2

LeemHyungJun·2023년 5월 26일
0

Algorithm

목록 보기
6/9

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(n1)2Θ(n2)T(n) = 2(n-1)^2 \in \Theta(n^2)
    • 힙으로 구현한 경우 Θ(mlg n)\Theta(mlg\ n)
    • 피보나치 힙으로 구현한 경우 Θ(m+nlg n)\Theta(m+nlg\ n)

2. Huffman code

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

3. 0-1 knapsack problem

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

greedy

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

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

동적 계획법

P[i][w]=max(P[i1][w],pi+P[i1][wwi])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(m2)O(m^2)
    • union의 단점 극복하기 위해 weighted union heuristic 존재
    • O(nlgn)O(nlgn)

array

  • list와 동일

tree

  • 가중치 x

  • 가중치 o

  • find

  • path compression

0개의 댓글