욕심쟁이 방법은 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘 등으로도 불리는데 전체적인 상황을 종합적으로 판단하여 선택하는 것이 아니라 현시점의 정보를 바탕으로 현재 가장 이익이 되는 선택을 한다.

최적화 문제와 최적 부분구조

욕심쟁이 방법은 최적화 문제(Optimization problem) 을 해결하기 위한 방법이다. 최적화 문제란 가능한 모든 대안 중에서 가장 좋은 해답을 고르는 문제이다.

욕심쟁이 방법을 사용하기에 적합한 문제는 최적 부분구조(Optimal substructure) 라는 조건이 만족되어야 한다. 주어진 문제(problem)의 최적해가 부문제(subproblem)들의 최적해로부터 효율적으로 생성될 수 있다면 최적 부분구조를 갖는다고 말한다. 전체를 고려하지 않고 현재만을 생각하므로 비교적 간단히 구현되며 한번 내린 결정은 취소하거나 변경하지 않기 때문에 어떤 다른 최적화 문제 해결 기법보다 빠르다.

욕심쟁이 방법의 구성

욕심쟁이 방법이 최적해를 만들어가는 세 가지 작업

  1. 선택 작업

    현상태에서 최적해에 포함시킬 대안을 선택, 욕심쟁이 방법이 성공하려면 선택 작업이 결국 최적해를 구한다는 것을 증명 해야 한다.

  2. 타당성 조사

    선택된 해가 주어진 문제의 조건을 만족하는지 검사

  3. 해답 조사

    원래의 문제가 해결되었는지를 검사

greedy_method()
{
  solution = {};
    while(condition)
    {
      s = select();   //선택
      if(feasible(s)) // 타당성 조사
      {
        solution = solution U {s};
        if(proble_solved(solution))return solution; //해답 조사
      }
    }
}

타당성 조사를 통과하면 최적해에 포함되고 그렇지 않으면 다음 선택 작업을 수행한다. 타당성 조사는 경우에따라 생략될 수 있으며 해답 조사는 줄3의 condition에 포함될 수 있다.

최소 신장 트리

최소 신장 트리(MST: minumum spanning tree) 구하기는 욕심쟁이 방법을 사용하는 대표적인 알고리즘이다. 신장 트리란 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리이다. 따라서 정점의 수가 n개이면 신장 트리의 간선 수는 정확히 n-1개이다. 최소 비용 신장 트리(MCST: minumum cost spanning tree) 는 방향성이 없는 연결된 가중치 그래프가 주어졌을 때 간선들의 가중치 합이 최소가 되는 신장 트리를 구하는 것이다.

모든 정점 간에 간선이 있는 완전 그래프의 경우 신장 트리의 수는 n^(n-2)이다. 따라서 무작위 기법을 이용한 최소신장트리를 구하기는 현실적으로 불가능 하다.

크러스컬 알고리즘

각 단계에서 가중치가 작은 간선부터 선택한다. 선택한 간선 때문에 사이클이 만들어 진다면 선택한 간선은 과감히 버린다. 받아들여진 간선의 수가 n-1개가 되면 종료한다. 여기에 두 가지 고려 사항이 있다.

  1. 가중치가 작은 간선을 최소값 찾기 알고리즘으로 선택하는데 걸리는 시간이 많이 걸리기 때문에 선택을 시작하기 전에 모든 간선을 오름차순으로 정렬해 놓는다.

  2. 사이클이 만들어지는지 알 수 있는 효율적인 방법이 필요하다. 깊이 우선 탐색이나 너비 우선 탐색을 생각해 볼 수 있지만 둘다 무작위 탐색 기법이기 때문에 부담이 크다. 대신 배타적 집합의 union-find연산을 이용한다.

edge_set kruskal_MST(edge_set E, int n)
{
  sort(E);
  edge_set MST_E = {};
  for(i = 0; i < n; i++) init_set(i); // n개의 집합을 생성
  while(MST_E의 간선 수 < n-1)
  {
    (u, v) = E의 최소 가중치 간선;  //선택작업
    E = E - {(u, v)};
    if(find(u) != find(v)) // u와 v가 다른 집합 원소, 타장성 조사
    {
      MST_E = MST_E U {(u,v)};
      union(u, v);
    }
  }
  return MST_E;
}

크러스컬 알고리즘이 최소 신장트리를 구한다는 것이 증명되어 있기 때문에 해답 조사는 필요없다.

정점의 수가 n, 간선의 수가 e일때 크러스컬 알고리즘의 복잡도를 구해보자.

  • sort함수를 가장 성능이 우수한 기법을 사용하면 O(e loge)가 걸린다.
  • 기준 연산 init_set, find, union for에서 init_set n회, while 은 e회 일때 find는 2e회, union은 e회 모두 더하면 3e+n, n-1 <= e 이므로 O(e)이다.

결국 크러스컬 알고리즘의 복잡도는 정렬 알고리즘이 좌우한다. 간선의 수는 최대 O(n^2)이므로 O(eloge)=O(elogn^2)=O(2elogn)=O(elogn)이다 따라서 O(elogn)이라 이야기하는 경우도 있다.

프림의 알고리즘

프림의 알고리즘도 가중치가 낮은 간선부터 선택한다. 프림의 알고리즘은 처음부터 끝까지 트리를 유지한다. 아무 정점이나 하나를 선택하여 시작 트리로 초기화하고 매 단계에서 간선 하나와 정점하나를 붙여나가면 서 트리를 유지하면 된다. 모든 정점을 선택하면(n-1) 종료한다.

프림의 알고리즘은 사이클을 생성하지 않는다. 프림의 알고리즘을 구현하는데 있어 최소 가중치의 간선을 선택하는 방법이 성능을 좌우한다. 정점 u가 선택될 때마다 u에 인접했으나 아직 최소 신장 트리에 포함되지 않은 모든 정점 w에 대해 다음과 같이 재계산 하여야 한다. 간선 (u, w)의 가중치를 weight(u, w)라 하면

distance(w) = minimum{distance(w), weight(u, w)}
nearest(w) = u if distance(w)가 변경

void prim_MST_2(int graph[][MAX], int n, int s)
{
  bool MST_V[MAX];
  int distance[MAX], nearest[MAX], i, u, w;
  for(i = 0; i < n; i++)//초기화
  {
    MST_V[i] = false;
    distance[i] = graph[s][i];
    nearest[i] = s;
  }
  MST_V[s] = true;
  loop(n-2) //n-2번 반복
  {
    u = select_min(distance, n, MST_V);
    MST_V[u] = true;
    for(w = 0; w < n; w++)
    {
      if(MST_V[w] == flase)
      {
        if(graph[u][w] < distance[w])
        {
          distance[w] = graph[u][w];
          nearest[w] = u;
        }
      }
    }
  }
}

int select_min(int distance[], int n, bool MST_V[])
{
  int i, min = 1/0, min_index = 0;
  for(i = 0; i < n; i++)
  {
    if(distance[i] < min&&MST_V[i] == false)
    {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}

정점의 수가 n이고 간선의 수가 e일때 프림알고리즘의 복잡도

  • 초기화 블록은 Θ(n)이다. 프림 알고리즘의 전체 복잡도에 영향을 주지 못한다.
  • loop는 n-2회 반복한다. select_min함수가 Θ(n)이고 다음 for문 역시 Θ(n)이므로 loop 전체 복잡도는 Θ(n^2)이다.

결국 프림 알고리즘은 Θ(n^2)이다.

비교

간선의 수와 정점의 수가 비슷해지는 희소 그래프와 간선의 수가 O(n^2)이 되는 고밀도 그래프에 따라 장단점이 있다. 크러스컬 알고리즘은 인접리스트와 이진 히프를 사용하는 프림알고리즘과 점근적으로 동일한 복잡도를 보였으며 인접 행렬과 순차탐색을 사용하는 프림 알고리즘은 희소 그래프에서는 가장 복잡도가 높았지만 고밀도 그래프에서 장점을 나타내었다.

알고리즘 점근 복잡도 희소 그래프 고밀도 그래프
크러스컬 O(eloge) O(nlogn) O(n^2logn)
프림(인접행렬, 순차탐색 O(n^2) O(n^2) O(n^2)
프림(인접리스트, 이진 히프) O(elogn) O(nlogn) O(n^2logn)

  • 최적 부분 구조

    둘다 최적부분 구조를 갖는다.