7강 욕심쟁이 알고리즘(1)

욕심쟁이 방법의 원리(greedy algorithm)

• 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 최적해를 선택함으로써 전체적인 최적해를 구하는 방식
• 동적 프로그래밍 방법과의 비교
  • 공통점
    1. 최적화 문제(최솟값, 최댓값)에 주로 사용된다.
    2. 최적성의 원리가 적용된 방법이다.
  • 차이점
    1. 동적 프로그래밍
       소문제의 여러 최적해로부터 다음 크리의 문제에 대한 최적해가 결정 → 항상 전체적인 최적해를 구함
    2. 욕심쟁이 방법
       소문제에 대해서 하나의 최적해만 고려 → 전체적인 최적해를 구하지 못할 수 있다.
  • 욕심쟁이 방법의 한계
    소문제의 해는 구해도 전체의 해를 못구할 수 있다.

동전 거스름돈 문제

• 고객에게 거스름돈을 돌려 줄 때 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제
  → 거스름돈 액수를 넘지않는 조건에서 액면가가 큰 동전부터 최대한 사용하여 거슬러 준다.
• 성능
  O(n) / O(nlogn)
• 동전의 액면가가 임의로 주어지는 경우
  → 욕심쟁이 기법을 적용하여 문제의 해를 구하면 최적해가 아니다. (이러한경우는 욕심쟁이 방법으로 해결 불가하다)

배낭 문제

• 최대 용량이 m인 하나의 배낭과 n개의 물체가 있을 때 (각 물체 i에는 물체의 무게 w와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 p) 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 구하는 문제
  (가정: 물체를 쪼개서 넣을 수도 있다)
  → 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 최대한 넣는다. (단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복한다)
• 성능
  O(n)
  O(nlogn) → 단위 무게 당 이익의 정렬도 고려해야하는 경우
• 물체를 쪼개 넣을 수 없는 형태의 배낭 문제(0/1 배낭 문제)
  → 욕심쟁이 방법 적용이 불가하다

최소 신장 트리

• 신장트리?
  가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리(사이클이 없다)
  그래프에서 정점이 n개이면 트리에는 n-1개의 간선이 존재한다.
• 최소 신장 트리 알고리즘
  1. 크루스칼 알고리즘 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면 추가시키는 방법 (서로 다른 덩어리에 속하는 정점을 잇는 최소 가중치의 간선을 선택한다)
     성능 : O(|E|log|E|)
  2. 프림 알고리즘
     임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법(이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법)
     성능: 인접행렬 O(|V|**2), 인접 리스트 O((|V|+|E|)log|v|)