[algorithm] 그리디 알고리즘

• 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함
  • greedy -> 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘

동적 프로그래밍 방법	그리디 알고리즘
최적화 문제 해결에 주로 사용
최적성의 원리가 적용된 방법
소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 -> 항상 전체적인 최적해를 구함	소문제(각 단계)에 대해서 하나의 최적해만을 고려 -> 전체적인 최적해를 구하지 못할 수도 있음

 

• 그리디 알고리즘 방법의 원리
  • 그리디 알고리즘의 한계
    • 예를들어 가장 멋진바지, 가장 멋진 넥타이, 가장 멋진 자켓을 입는다고 할 때 그런 옷을 입은 멋쟁이씨는 과연 세상에서 가장 멋쟁이라고 할 수 있는가?
    • 그리디 알고리즘으로 해를 구할 수 없는 문제도 많음
• 동전 거스름돈 문제
  • 개념과 원리
    • 고객에게 돌려줄 거스름돈이 있을 때 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제
      • "동전 문제", "거스름돈 문제"
    • 기본 아이디어
      • 거스름돈의 액수를 초과하지 않는 조건하에서 단순히 액면가가 가장 큰 동전부터 '욕심을 부려' 최대한 사용해서 거스름돈을 만듦
      • 시간복잡도: O(n)

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];
    }
}

 

•  
  • 특징
    • 동전의 액면가가 임의로 주어지는 일반적인 경우
      • 예: 동전의 종류 -> 500원, 120원, 100원, 50원, 10원
      • 거스름돈 650원에 대해서 욕심쟁이 방법으로 적용하면 
        • 500원짜리 동전 -> 1개 
        • 120원짜리 동전 -> 1개
        • 10원짜리 동전 -> 3개
          • 5개의 동전이 필요
        • 최적해 -> 500원 * 1개, 100원 * 1개, 50원 * 1개  => 3개
          • 일반적인 경우의 거스름돈 문제는 욕심쟁이 방법으로 해결 불가
• 배낭문제
  • 최대 용량 M인 하나의 배낭과 n개의 물체
    • 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pi
  • 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법(또는 최대 이익)을 구하는 문제
    • 가정 -> 물체를 쪼개서 넣을 수 있다.
  • 기본 아이디어
    • 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 욕심을 내어 최대한 넣는다.
    • 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복, 만약 물체를 통째로 넣을 수 없으면 남는 배낭 용량만큼 쪼개서 넣으면 됨

Knapsack(p[], w[], M, n, x[]){
// 입력: p[i], w[i]: 물체 i의 이익과 무게
//      (단위 무게당 이익이 감소하는 순으로 정렬) // O(nlogn)
//      n, M: 물체의 개수와 배낭의 용량
// 출력: X[i]: 배낭과 물체 i의 비율
    for(i=0; i<n; i++) x[i] = 0; // O(n)
    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];
}

 

• 0/1 배낭 문제
  • 물체를 쪼갤 수 없는 형태의 배낭 문제
    
    •  그리디 알고리즘 적용 불가
• 최소 신장 트리
  • 신장 트리(spanning tree)
    • 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리
  • 최소(비용) 신장 트리(minimum spanning tree)
    • 간선 (u,v)마다 가중치 w(u,v)를 가진 연결된 무방향 그래프 G = (V,E)에 대해서 다음을 만족하는 트리 G`= (V,E`)
    • 신장 트리 중에서 간선의 가중치의 합이 가장 작은 트리
    • 최소신장트리 알고리즘
      
      • 크루스칼(Kruskal) 알고리즘
        • 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면 추가시키는 방법
          • 서로 다른 연결 성분에 속하는 정점을 잇는 최소 가중치의 간선을 선택
            • n=|V|개의 정점이 서로 다른 연결 성분으로 구성된 상태에서 시작해서 간선이 추가될 때마다 연결 성분들이 합쳐지고 최종적으로 하나의 연결 성분을 형성
        • 성능: O(|E| long|E|)
      • 프림(Prim) 알고리즘
        • 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법
          • 이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법
            • 이미 선택된 정점의 집합 S와 미선택 정점의 집합 V-S를 잇는 간선 중에서 가중치가 최소인 간선을 선택해서 추가하는 방법
        • 성능
          • 인접행렬의 경우: O(|V|^2)
          • 인접리스트 + 힙 사용: O(|V| + |E|) log(|V|)
• 정리
  • 그리디 알고리즘의 원리
    • 각 단계마다 국부적인 최적해를 선택해서 전체적인 최적해를 구함
      • 항상 전체적인 최적해를 구한다는 것을 보장하지 못함
    • 동전 거스름돈 문제
      • 단순히 액면가가 가장 큰 동전부터 최대한 사용해서 거스름돈을 만ㄷ름
        • O(n) (n: 동전의 종류), 동전의 액면가가 일반적인 경우에는 해결 불가
    • 배낭 문제
      • 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣음
        • O(n) (n: 물체의 개수), 물체를 쪼갤 수 있는 경우에만 적용 가능
    • 최소 신장 트리
      • 그래프의 모든 정점을 포함한 연결된 트리중에서 가중치의 합
        • 크루스칼 알고리즘 -> O(|E|log|E|)
        • 프림 알고리즘 -> 인접행렬 O(|V|^2), 인접리스트 O( (|V|+|E|) log|V| )
• 프림 알고리즘, 크루스칼 알고리즘 -> 최소신장트리 알고리즘 -> 그리디 알고리즘 적용
• 다익스트라 알고리즘 -> 단일 출발점 최단 경로를 구하는 알고리즘 -> 그리디 알고리즘 적용
• 플로이드 알고리즘 -> 모든 정저 간의 최단 경로를 구하는 알고리즘 -> 동적 프로그래밍 방법 적용