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

학습목표 

1. 욕심쟁이 방법의 개념과 원리를 이해할 수 있다.

2. 동전 거스름돈 문제와 배낭 문제의 개념, 동작, 그리고 특징을 이해할 수 있다.

3. 최소 신장 트리와 최단 경로를 구하는 방법의 개념, 동작, 그리고 특징을 이해할 수 있다.

4. 작업 스케줄링 문제와 작업 선택 문제의 개념, 동작, 그리고 특징을 이해할 수 있다.

5. 허프만 코딩의 개념, 동작 그리고 특징을 이해할 수 있다.

 

주요용어

#욕심쟁이방법 #동전 거스름돈 문제 #배낭 문제 #최소 신장 트리 #크루스칼 알고리즘 #프림 알고리즘 #최단경로 # 데이크스트라 알고리즘 #다익스트라 알고리즘 #작업스케줄링 문제 # 작업선택문제 #허프만 코딩 #허프만 트리

 

 

 

4.1 욕심쟁이 방법의 원리 

 

해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구하는 방법

 

소문제(각 단계)에서 하나의 최적해만을 고려하므로 항상 전체적인 최적해를 구한다는 것을 보장하지 못함

 

 

 

4.2 동전 거스름돈 (coin change ) 문제

 

4.2.1 개념과 원리 

 

고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제

 “동전 문제”,“거스름돈 문제”

동전의 종류 → 500원,100원,50원,10원

 

기본 아이디어

 거스름돈의 액수를 초과하지 않는 조건하에서 단순히 액면가가 가장 큰 동전부터 ‘욕심을 부려서’ 최대한 사용해서 거스름돈을 만듦

 

4.2.2 알고리즘과 성능 분석

 

CoinChange (T,n,C[],X[])

입력 : T:고객에게 돌려줄 거스름돈,n:동전의 종류

        C[0..n-1]:동전의 액면가를 감소순으로 저장(500→100→50→10) 

출력:X[0..n-1]:거스름돈으로 돌려줄 i번째 동전의 개수

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

     {

          X[i]=T/C[i];

          T=T- C[i]*X[i];

      }
}                시간 복잡도  :    O(n)

 

 

 

4.2.3 특징

 

동전의 액면가가 임의로 주어지는 일반적인 경우의 동전 거스름돈 문제는 욕심쟁이 방법으로 동전의 개수가 최소가 되는 최적해를 얻지 못할 수 있다.

 

 

 

4.3. 배낭문제

 

4.3.1 개념과 원리

 

최대 용량 M인 하나의 배낭과 n개의 물체

- 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣을 때 얻을 수 있는 이익 pi

 

배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 

최대가 되도록 물체를 넣는 방법(또는 최대 이익)을 구하는 문제 

- 물체를 쪼개서 넣을 수 있다고 가정

 

 

기본 아이디어 

물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 ‘욕심을 내어’최대한 넣음
⇒ 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복, 

물체를 통째로 넣을 수 없으면 남은 배낭의 용량만큼 물체를 쪼개서 넣음

 

 

 

4.3.2 알고리즘

 

 

Knapsack(p[],w[],M,n,x[]) 

입력 : p[i], w[i] : 물체 i의 이익과 무게

                     (단위 무게당 이익이 감소하는 순으로 정렬)

        n,M:각각 물체의 개수와 배낭의 용량

출력 : X[i] : 배낭에 들어간 물체 i의 비율

 

{
     for(i=0;i<n;i++)x[i]=0;  // 결과 배열  x[]를 초기화

     r=M;                        // r은 남은 배낭의 용량으로, M으로 초기화

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

         if(w[i]<=r)             // 물체 i 의 무게가 남은 배낭의 용량보다 작으면

            {                      // 물체 i 전체를 배낭에 넣음

               x[i]=1; r=r- w[i];  // 배낭의 용량을 물체 i 의  무게만큼 감소

            }

      elsebreak;                     // 남은 배낭의 용량이 작아 물체를 넣을 수 없으면 반복문 종료

      if(i<n)x[i]=r/w[i];             // 남은 물체가 있다면, 물체를 쪼개서 배낭에 넣음
}

 

 

 

 

 

4.3.3 성능 및 특징

 

성능 분석

 

Knapsack(p[],w[],M,n,x[]) 

입력 : p[i], w[i] :물체 i의 이익과 무게

               (단위 무게당 이익이 감소하는 순으로 정렬)

          n,M:각각 물체의 개수와 배낭의 용량

출력 : X[i] : 배낭에 들어간 물체 i의 비율    

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

        x[i]=0;

     r=M;

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

     if(w[i]<=r)

     {

         x[i]=1;

          r=r- w[i];

      }

     elsebreak;

     if(i<n)x[i]=r/w[i];
}      

시간 복잡도  : O(n)

정렬까지 고려하면 O(nlogn)

 

 

 >> 물체를 쪼갤 수 없는 형태의 배낭 문제,  0/1배낭 문제 는 욕심쟁이 방법으로 해결 불가

 

 

 

4.4 최소 신장 트리

 

4.4.1 개념과 원리 

 

가중 무방향 그래프 ( weighted undirected gragh )

 

신장 트리 ( spanning tree ) : 주어진 그래프에서 모든 정점을 포함하는 연결된 트리

그래프의 정점이 n 개이면 신장트리에는 사이클이 존재하지 않으므로 정확히 ( n- 1) 개의 간선이 존재

 

최소 (비용) 신장 트리 minimumspanningtree

 

-간선 (u,v)마다 가중치 w(u,v)를 가진 연결된 무방향 그래프 G=(V,E)에 대해서 다음을 만족하는 트리 G′=(V,E′) 

-신장 트리 중에서 간선의 가중치의 합이 가장 작은 트리

 

Greedy _ MST (G)

입력 : 그래프 G = ( V, E )

출력 : 최소 신장 트리의 간선 집합 T

{

     T = ø                                  // 최소 신장 트리의 간선 집합의 초기화

     while ( T 가 신장 트리가 되지 않았다) 

           {

             사이클을 형성하지 앟는 최소의 가중치를 갖는 최선의 간선 ( u, v ) 를 선택 ;

              T = T ∪ { ( u, v ) } ;     //서낵된 간선을 T 에 추가

            }

     return T;

}

 

 

4.4.2 크루스칼 알고리즘 

 

(1) 개념과 원리

 

간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 

간선부터 하나씩 사이클을 만들지 않으면 추가시키는 방법

- 서로 다른 연결 성분에 속하는 정점을 잇는 최소 가중치의 간선을 선택

  - n개의 정점이 서로 다른 연결 성분으로 구성된 상태에서 시작해서,간선이 추가될 때마다 연결 성분들이 합쳐지게 되고,최종적으로 하나의 연결 성분을 형성

 

(2) 알고리즘 

 

Kruskal (G) 

입력 : G : 가중 무방향 그래프 G = ( V , E )

출력 : T : 최소 신장 트리의 간선 집합 T 

 

{
     T=Ø;

     for(각 정점 v에 대해)

        정점 v로 구성된 연결 성분 초기화;

     가중치가 증가하는 순으로 모든 간선을 정렬;

     for(가중치가 가장 작은 간선부터 모든 간선 (u,v)∈E에 대해서 )

       if(u와 v가 다른 연결 성분에 있으면 ){//사이클을 형성하지 않으면

         T=T∪{(u,v) };

         u의 연결 성분과 v의 연결 성분을 합침;

        }

     else간선 (u,v)를 버림;

     returnT;
}

 

(3) 성능 분석 

 

Kruskal (G) 

 

{
     T=Ø;

     for(각 정점 v에 대해)     >>>>>>>>>>>>>>>>>>>>>>>>>>> O ( |V| )

       정점 v로 구성된 연결 성분 초기화;

      가중치가 증가하는 순으로 모든 간선을 정렬;  >>>>>>>>>>>>> O ( |E|long|E| )

      for(가중치가 가장 작은 간선부터 모든 간선 (u,v)∈E에 대해서 ) >> O ( |E| α ( |E| ,  |V| ))

      if(u와 v가 다른 연결 성분에 있으면 )

      {

          T=T∪{(u,v)};

          u의 연결 성분과 v의 연결 성분을 합침;

      }

     else 간선 (u,v)를 버림;

    returnT;
}

 

 시간 복잡도 : O ( |E| log |E| )

 

 

 

4.4.3. 프림 알고리즘

 

(1) 개념과 원리

임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법

  -  이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법 

    -- 이미 선택된 정점의 집합 S와 미선택 정점의 집합 V-S를 잇는 간선 중에서 

      가중치가 최소인 간선을 선택해서 추가해 나가는 방법

 

(2) 알고리즘

Prim(G) 

 

입력:G:가중 무방향 그래프 G=(V,E)

출력:T:최소 신장 트리의 간선 집합 T

 

{
    T=Ø;

    S = { a };    //임의의 정점(예, 여기서는 a)으로 초기화

    while ( S != V )

     {

        u∈S, v∈V-S인 것 중 가중치가 최소인 간선 (u,v) 선택;

        T = T ∪ { (u,v) };

        S = S ∪ { v };

      }

     returnT;
}

 

(3) 성능 분석

 

Prim(G)

{ 
    T=Ø;

    S = { a };    //임의의 정점(예, 여기서는 a)으로 초기화

    while ( S != V )

     {

        u∈S, v∈V-S인 것 중 가중치가 최소인 간선 (u,v) 선택;

        T = T ∪ { (u,v) };

        S = S ∪ { v };

      }

     returnT; 
}

인접 행렬의 경우 : O ( |V|^2 )

인접 리스트 +힙 사용 : O (( |V| + |E|) log |V| )

 

 

 

 

6강 제 3장 동적 프로그래밍 알고리즘

6강 제 3장 동적 프로그래밍 알고리즘

 

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

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