Greedy Algorithm(1)

욕심쟁이 방법 원리

• 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함
  • 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘
• 동적 프로그래밍 방법
  • 소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 → 항상 전체적인 최적해를 구함
• 욕심쟁이 방법
  • 소문제(각 단계)에 대해서 하나의 최적해만 고려 → 전체적인 최적해를 구하지 못할 수도 있음

동전 거스름돈 문제

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

  ex) 동전의 종류가 500, 100, 50, 10만 있다면,

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

  500 → 100 → 50 → 10

• 알고리즘

    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)

but!

동전의 액면가가 임의로 주어지는 일반적인 경우, 거스름돈 문제는 욕심쟁이 방법으로 해결이 불가능하다. 비효율적인 결과를 산출함

( 큰 값부터 줄여나가기 때문에 )

배낭문제

• 최대 용량 M인 하나의 배낭과 n개의 물체
  • 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pi

  배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법(최대이익)을 구하는 문제

  • 가정 → 물체를 쪼개 넣을 수 있음

  • 아이디어

  → 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 최대한 넣는 방식

  • 단위무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복. 남는 배낭의 용량만큼 물체를 쪼개서 넣을 수 있다.

  • 알고리즘

      Knapsack (p[], w[], M, n, x[]) 
      {
      	for (i=0; i<n; i++) // O(n) 
      		x[i] = 0; 
      	r = M;
      	for (i=0; i<n; i++) // O(n)
      		if ( w[i] <= r ) { 
      			x[i] = 1;
      			r = r - w[i]; 
      		}
      	else break;
      	if ( i<n ) //용량이 꽉 차면 물체를 나눔
      		x[i] = r / w[i];
      }
    

    성능 → O(n)

    • 만약 정렬을 함께 고려하는 경우

      O(nlogn)

  • 0/1 배낭 문제 특징

    • 물체를 쪼갤 수 없는 형태의 배낭 문제의 경우

      → 욕심쟁이 방법으로 적용이 불가능

      (* 후에 참조)

최소 신장 트리

• 신장 트리

  : 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리

  • 조건 1) 무방향 그래프 2) 모든 정점을 포함 3) 사이클 X

    → 즉 트리여야 한다.

• 개념

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

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

• 종류

  • 크루스칼(Kruska) 알고리즘
  • 프림(Prim) 알고리즘

→ 욕심쟁이 방법

Greedy_MST ( G=(V, E) ) {
	T← Ø ;
	while ( T가 신장 트리를 만들지 않았음 ) {
		최선의 간선 (u, v)를 선택; //사이클을 형성하지 않으면서 최소의 가중치를 갖는 간선
		T ← T ∪ { (u, v) }; 
	}
return (T); 
}

크루스칼 알고리즘

• 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면 추가시키는 방법

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

    →n =

    V

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

• 알고리즘

    Kruskal ( G ) {
    	T = Ø;
    	for (각 정점 v에 대해)
    		정점 v로 구성된 연결 성분 초기화; // O(|V|)
    		가중치가 증가하는 순으로 모든 간선을 정렬; // O(|E|log|E|)
    	for ( 가중치가 가장 작은 간선부터 모든 간선 (u,v)∈E에 대해서 )
    		if ( u와 v가 다른 연결 성분에 있으면 ) {  // 사이클을 형성하지 않는 경우 
    			T = T ∪ { (u,v) };
    			u의 연결 성분과 v의 연결 성분을 합침; O(|E|a(|E|,|V|))
    		}
    		else 간선 (u,v)를 버림;
    	return T; 
    }
  

• 성능

  → 1) O(|V|) 2) O(|E|log|E|) 3) O(|E|a(|E|,|V|))

  (* a(|E|,|V|) → 간선 여부를 확인하는 알고리즘)

  ⇒ O(|E|log|E|)

프림 알고리즘

• 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법
  • 이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법
    • 이미 선택된 정점의 집합 S와 미선택 정점의 집합 V-S를 잇는 간선 중에서 가중치가 최소인 간선을 선택해서 추가하는 방법

• 알고리즘

    Prim ( G ) {
    	T = Ø;
    	S = { a }; //임의의 정점(예, 여기서는 a)으로 초기화 
    	while ( S != V ) {
    		u∈S, v∈V-S인 것 중 가중치가 최소인 간선 (u,v) 선택; 
    		T = T ∪ { (u,v) 
    	};
    	S = S ∪ { v };
    	}
    	return T;
    }
  

• 성능
  • 인접 행렬의 경우 → O(|V|2)
  • 인접 리스트 + 힙 사용 → O(|V| + |E|) log|V|)