욕심쟁이 알고리즘 (1)

대표적인 알고리즘 설계기법 중 하나인 욕심쟁이 방법의 개념과 이를 적용한 동전 거스름돈 문제, 배낭 문제, 그리고 최소 신장 트리를 구하는 알고리즘의 원리와 동작, 그리고 성능과 특징에 대해서 학습한다.

 

욕심쟁이 방법의 원리

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

동전 거스름돈 문제

• 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제
  • 동전 문제, 거스름돈 문제
  • 동전의 종류 - 500원,100원,50원,10원
• 기본 아이디어
  • 거스름돈의 액수가 초과하지 않는 조건하에서 단순히 액면가가 큰 동전에 대해서 욕심을 부려서 주는 것
  • 동전의 액면가가 임의로 주어진 문제는 해결할 수 없음

배낭 문제

• 최대 용량 M인 하나의 배낭과 n개의 물체
  • 각 물체 i에는 물체의 무게 w_i와 해당 물체를 배낭에 넣을 때 얻을 수 있는 이익 p_i
• 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법
• 기본 아이디어
  • 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 '욕심을 내어' 최대한 넣음
  • 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복, 물체를 통째로 넣을 수 없으면 남은 배낭의 용량만큼 물체를 쪼개서 넣음
• 성능
  • 단위 무게당 이익이 감소하는 순으로 정렬 되어있다면 -> O(n)
  • 정렬을 고려한다면 -> O(nlogn)
• 0/1 배낭 문제
  • 물체를 쪼갤 수 없는 형태의 배낭 문제
  • 욕심쟁이 방법 적용 불가 ( 욕심쟁이 방법을 적용하려면 물체를 쪼갤 수 있어야 한다.)

최소 신장 트리 (spanning tree)

• 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리
  
  • 신장 트리 -> 정점이 n개이면, 트리에는 n-1개의 간선이 존재
• 최소 (비용)신장 트리 
  • 간선 (u,v)마다 가중치 w(u,v)를 가진 연결된 무방향 그래프 G(V,E)에 대해서 다음을 만족하는 트리
  • 신장 트리 중에서 간선의 가중치의 합이 가장 작은 트리
• 개념과 원리
  • 욕심쟁이 방법 
    • 크루스칼 알로기즘
    • 프림 알고리즘
  • 최선의 간선? 사이클을 형성하지 않으며 최소의 가중치를 갖는 간선
  • 크루스칼 알고리즘
    • 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면 추가시키는 방법
      • 서로 다른 연결 성분에 속하는 정점을 잇는 최소 가중치의 간선을 선택
        • n개의 정점이 서로 다른 연결 성분으로 구성된 상태에서 시작해서, 간선이 추가될 때마다 연결 성분들이 합쳐지게 되고, 최종적으로 하나의 연결 성분을 형성
    • 성능
      • O(|E|log|E|) 가중치가 증가하는 순서로 모든 간선을 연결
  • 프림 알고리즘
    • 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법
    • 이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법
      • 이미 선택된 정점의 집합 S와 미선택 정접의 집합 V-S를 잇는 간선 중에서 가중치가 최소인 간선을 선택해서 추가해 나가는 방법
    • 성능
      • u가 S, v가 V-S에 속하는 것 중 가중치가 최소인 간선 (u,v) 선택
        • 인접 행렬의 경우 : O(|V|^2)
        • 인접 리스트 + 힙 사용: O( (|V|+|E|) log|V| )

cf) 욕심쟁이 방법으로 해결 가능한 문제/알고리즘

→ 동전 거스름돈, 배낭 문제(물체를 쪼갤 수 있는 경우)

→ 최소 신장 트리(크루스칼 알고리즘, 프림 알고리즘)

→ 단일 출발점 최단 경로(데이크스트라 알고리즘)작업 스케줄링 문제, 작업 선택 문제, 허프만 트리

 

① 프림 알고리즘, 크루스칼 알고리즘 → 최소 신장 트리 알고리즘

② 데이크스트라 알고리즘 → 단일 출발점 최단 경로를 구하는 알고리즘

③ 플로이드 알고리즘 → 모든 정점 간의 최단 경로를 구하는 알고리즘

④ 벨만-포드 알고리즘 → 음의 간선이 있더라도 음의 사이클이 없는 경우의 최단 경로를 구하는 알고리즘(교재에서 다루지 않음)

 

정리하기

1. 욕심쟁이 방법
   - 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택하므로써 전체적인 최적해를 구하는 방법
   - 소문제(각 단계)에서 하나의 최적해만을 고려하므로 항상 전체적인 최적해를 구한다는 것을 보장하지 못함

---

1. 동전 거스름돈 문제
   - 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제 → 단순히 액면가가 가장 큰 동전부터 최대한 사용해서 거스름돈을 만듦
   - 성능(n: 동전의 종류) : O(n)
   - 동전의 액면가가 임의로 주어지는 일반적인 경우는 욕심쟁이 방법으로 해결 불가

---

1. 배낭 문제
   - 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣은 방법을 찾는 문제 → 물체를 쪼개서 넣을 수 있다고 가정 → 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣음
   - 성능(n: 물체의 개수) : O(n), 그러나 물체의 무게/이익이 단위 무게당 이익에 따라 정렬하는 경우까지 고려하면 O(nlogn)
   - 물체를 쪼갤 수 없는 형태의 0/1 배낭 문제는 욕심쟁이 방법으로 해결 불가

---

1. 최소 신장 트리
   - 신장 트리(주어진 그래프에서 모든 정점을 포함하는 연결된 트리) 중에서 가중치의 합이 가장 작은 트리 → 욕심쟁이 방법을 적용한 크루스칼 알고리즘과 프림 알고리즘으로 구함
   - 크루스칼 알고리즘 : 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 형성하지 않으면 추가시키는 방법 → 사이클을 형성하지 않으려면 서로 다른 연결 성분에 속하는 간선을 선택해야 함 → 성능 : O(|E|log|E|)
   - 프림 알고리즘 : 임의의 한 점에서 시작해서 연결된 정점을 하나씩 선택해서 추가시키는 방법 → 이미 선택된 정점 집합 S와 미선택 정점 집합 V-S를 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가 → 성능 : 인접 행렬로 구현하면 O(|V|^2), 인접 리스트로 구현하고 힙을 사용하면 O((|V|+|E|)log|V|)