8강 제 4장 욕심쟁이 알고리즘

4.5 최단 경로

 

4.5.1 개념과 원리

 

두 정점 간의 최단 경로 ( shortest path ) 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치 합이 가장 작은 경로를 의미한다.

 

플로이드 Floyd 알고리즘	데이크스트라 Dijkstra 알고리즘
모든 정점 간의 최단 경로	특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로(“단일 출발점 최단 경로”)
동적 프로그래밍 방법 적용	욕심쟁이 방법 적용
O(|V|3)	O(|V|2)
가중치의 합이 음수인 사이클이 없다고 가정	음의 가중치를 갖는 간선이 없다고 가정

 

데이크스트라(다익스트라) 알고리즘

: 거리 d[v] 

: 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 

 

-출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법

  - 초기화 → 출발점 d[s]=0,나머지 모든 정점 v의 d[v]=∞,선택 정점 집합 S={}

  - 미선택 정점 집합 V-S에서 d[]가 가장 작은 정점 u를 선택 

    → u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정

 

 

4.5.2 알고리즘 

Dijkstra (G,s) 

 

입력 : G = ( V, E ), s : 시작 정점

출력 :  d [] : s로 부터 각 정점으로의 최단 경로의 길이

        phi[] : 최단 경로를 만드는 선행 정점

 

{
     S=Ø;d[s]=0;

     for(모든 정점 v≠s)d[v]=∞;

     for(모든 정점 v에 대해서)phi[v]=Null;

     while(S!=V) {

         d[u]가 최소인 정점 u∈V-S를 선택

         S=S∪ u};

         for(u에 인접한 모든 정점 v에 대해서 )

            if(d[v]>d[u]+(u,v)의 가중치 ){

                     d[v]=d[u]+(u,v)의 가중치;

                     phi[v]=u;

                          }

     }

     returnd[],phi[];
}

 

 

 

 

4.5.3 성능 분석

 

Dijkstra (G,s) 

 

{
     S=Ø;d[s]=0;

     for(모든 정점 v≠s)d[v]=∞;

     for(모든 정점 v에 대해서) phi[v]=Null;

     while(S!=V)

       {

          d[u]가 최소인 정점 u∈V-S를 선택

          S=S∪ u};

          for(u에 인접한 모든 정점 v에 대해서 )

              if(d[v]>d[u]+(u,v)의 가중치 )

                  {

                      d[v]=d[u]+(u,v)의 가중치;

                      phi [v] = u;

                   }

       }

     returnd[] , phi[];
}

 

인접 행렬 → O( |V|^2 )

인접 리스트 + 힙 →  O ( ( |V| + |E| ) log |V| ) 

 

 

 

4.5.4 특징 

 음의 가중치를 갖는 간선이 없어야 한다

 

 

 

4.6 작업 스케줄링 문제

 

4.6.1 개념과 원리

작업 스케줄링 ( task scheduling ) 

가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제

  - 작업의 집합 T = { t1, t2,…,tn } , ti = ( si, fi ) ( 1 ≤ i ≤ n )

      - si :작업 시작 시간,fi :작업 완료 시간
  - 작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함

      - 작업 간 충돌 → 한 기계에서 두 개 이상의 작업이 동시에 수행되는 것

      - 충돌을 피하기 위해 만족해야 할 조건 →  Fi ≤ Sj 또는 Fj ≤ Si  

 

기본 아이디어

 - 각 단계에서 ‘시작 시간이 빠른 작업’을 우선적으로 선택

    → 충돌이 발생하지 않으면 해당 기계에 배정

    → 충돌이 발생하면 새로운 기계에 할당   

 

4.6.2 알고리즘

 

TaskScheduling (T[][],n) 

 

입력 : T [0..n-1][0..1] : 

            T [i][0] : 작업 i의 시작 시간

            T [i][1] : 작업 i의 완료 시간

          n:작업의 개수

출력 : m : 모든 작업을 완료하는데 필요한 기계의 개수

 

 {

     작업을 시작 시간의 오름차순으로 정렬;

     m=1;

     for ( i = 0 ; i < n ; i++)

          {

                 if ( 작업 ti를 수행할 기계 p(1≤p≤m)가 있으면 )

                     작업 ti를 기계 p에 할당;

              else{

                     m=m+1; 작업 ti를 새 기계 m에 할당;

                   }

          }

     returnm;

}

 

 

4.6.3 성능 분석

 

TaskScheduling (T[][],n) 

{ 

     작업을 시작 시간의 오름차순으로 정렬;

     m=1;

     for ( i = 0 ; i < n ; i++)

       {

              if ( 작업 ti를 수행할 기계 p(1≤p≤m)가 있으면 )

                 작업 ti를 기계 p에 할당;

              else

                  {

                        m=m+1; 작업 ti를 새 기계 m에 할당;

                   }

        }

     returnm;

}

 

시간 복잡도 O(nlogn)

 

 

 

 

4. 7. 작업 선택 문제

 

4.7.1 개념과 원리 

  작업 선택 (activity selection ) 문제는 앞서 살펴본 작업 스케줄링 문제에서와 같이 n 개의 작업, 각 작업의 시작 시간과 완료 시간 ( Si, Fi )가 주어진 상태에서 하나의 기계만 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제

 

 

4.7.2 알고리즘

ActivitySelection (T[][],n) 

 

입력 : T [ 0..n-1 ][ 0..1 ] :

             T [i][0] : 작업 i의 시작 시간

             T [i][1] : 작업 i의 완료 시간

         n : 작업의 개수

출력 : m : 하나의 기계에서 처리할 수 있는 최대 작업 개수

 

 { 

        작업을 완료 시간의 오름차순으로 정렬;

        m=0;

        for ( i = 0 ; i < n ; i++)

              if(작업 ti가 충돌을 일으키지 않으면 )

                    {

                          m=m+1; 작업 ti를 기계에 할당;

                    }

      returnm;

}

4.7.3 성능 분석

 

ActivitySelection ( T[][] , n )

{
       작업을 완료 시간의 오름차순으로 정렬;

       m=0;

       for ( i = 0 ; i < n ; i++)

            if(작업 ti가 충돌을 일으키지 않으면 )

                  {

                        m=m+1;

                       작업 ti를 기계에 할당;

                  }

         returnm;
}

 

시간 복잡도 :  O(nlogn)

 

 

 

 

4.8 허프만 ( Huffman coding) 코딩

 

4.8.1. 개념과 원리

 

문자의 빈도 또는 확률 정보를 이용하는 통계적 압축 방법

  → 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여 

      • 출현 빈도수가 높은 문자 → 짧은 코드

      • 출현 빈도수가 낮은 문자 → 긴 코드

 

접두부 코드prefixcode

    각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드 

 

허프만 코드 

 접두부 코드 , 최적 코드

      최적 코드 → 인코딩된 메시지의 길이가 가장 짧은 코드

 

인코딩 과정 

      1) 주어진 텍스트에서 각 문자의 출현 빈도수를 계산

      2) 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여

      3) 주어진 텍스트의 각 문자를 코드로 변환하여 압축된 텍스트를 생성

 

허프만 트리

허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진 트리 

  - 욕심쟁이 방법 적용

  -  리프 노드가 각 문자를 표시하는 전 이진트리

각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복

  -  각 노드는 빈도수로 표시

  - 좌우의 두 간선은 각각 0과 1로 레이블됨

  - 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성 

            → 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합

 

 

 

 

4.8.2 알고리즘

 

HuffmanTree (F[],n)

 

입력 : F [1..n] : 문자 ci의 빈도수

        n : 문자 집합의 크기 ( C1, C2 ,…, Cn )

출력 : Q : 허프만 트리

 

 {

   빈도수 F[]에 따라 최소 힙 Q생성;

   for(i=0;i<n;i++){

      u← 힙 Q에서 최솟값 삭제;

      v← 힙 Q에서 최솟값 삭제;

      새 노드 x를 생성하여 u와 v를 x의 두 자식 노드로 지정;

      노드 x의 빈도수 ← u의 빈도수 +v의 빈도수;

      노드 x를 힙 Q에 삽입;

        }

    returnQ;

} 

 

 

 

4.8.3 성능 분석

 

HuffmanTree (F[],n) 

{
     빈도수 F[]에 따라 최소 힙 Q생성;

     for ( i = 0 ; i < n ; i++)

       {

            u← 힙 Q에서 최솟값 삭제;

            v← 힙 Q에서 최솟값 삭제;

           새 노드 x를 생성하여 u와 v를 x의 두 자식 노드로 지정;

           노드 x의 빈도수 ← u의 빈도수 +v의 빈도수;

           노드 x를 힙 Q에 삽입;

        }

   returnQ;
}

최악, 최선, 평균 수행 시간은 모두 O (n log n + m ) 이다.

 

 

 

4.8.4. 특징

각 문자의 빈도수를 모르는 경우 주어진 텍스트를 두 번 읽음

  ① 각 문자의 빈도수를 계산할 때, 

  ② 텍스트를 읽으면서 실제 인코딩할 때 

     >>  이 경우 속도가 상당히 느려져 실용성이 없음

 

압축된 데이터를 디코딩하려면 

 각 문자의 빈도수,허프만 트리에 대한 정보,문자 집합 정보가 필요 

     압축된 데이터의 헤더로서 필요한 정보 제공 → 실제 압축률 저하

 

 

 

 

2020/04/29 - [방송통신대학/알고리즘] - 7강 제 4장 욕심쟁이 알고리즘

7강 제 4장 욕심쟁이 알고리즘

2020/05/02 - [방송통신대학/알고리즘] - 9강 제 5장 정렬알고리즘 1

9강 제 5장 정렬알고리즘 1