탐욕 기법(그리디 알고리즘)

탐욕(Greedy) 알고리즘

• 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
• 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제
• 일반적으로, 머리 속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 된다.
• 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
• 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다.
• 항상 최적해를 구한다는 보장은 없다.
  ex) 거스름돈 800원을 greedy하게 접근해보았을 때 (500,400,100,50,10)원 동전이 있을 때 500원 1개 100원 3개로 해가 나오지만 400원동전 2개가 최소 동전의 최적해이기 때문

배낭 짐싸기(Knapsack)

• Knapsack 문제의 정형적 정의

  • S = {item1, item2,...,itemn} 물건들의 집합
  • Wi : itemi의 무게, Pi : itemi 의 값
  • W : 배낭이 수용 가능한 총 무게
  • 문제 정의
    

• Knapsack 문제 유형

  • 0-1 Knapsack
    • 배낭에 물건을 통째로 담아야 하는 문제
    • 물건을 쪼갤 수 없는 경우
  • Fractional Knapsack
    • 물건을 부분적으로 담는 것이 허용되는 문제
    • 물건을 쪼갤 수 있는 경우

• 0-1 knapsack에 대한 완전 검색 방법

  • 완전 검색으로 물건들의 집합 S에 대한 모든 부분 집합을 구하기
  • 부분집합의 총 무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택 가능
  • 물건의 개수가 증가하면 시간 복잡도가 지수적으로 증가
    • 크기 n인 부분집합의 수 22

• 0-1 Knapsack에 대한 탐욕적 방법1

  • 	무게	값
    물건1	25kg	10만원
    물건2	10kg	9만원
    물건3	10kg	5만원

  • 값이 비싼 물건부터 채운다.

  • W = 30kg

  • 탐욕적 방법의 결과 : (물건1)->25kg, 10만원

  • 최적해 : (물건2, 물건3) -> 20kg, 14만원

  • 최적 X

• 0-1 Knapsack에 대한 탐욕적 방법2

  • 	무게	값
    물건1	25kg	10만원
    물건2	10kg	9만원
    물건3	10kg	5만원

  • 무게가 가벼운 물건부터 채운다.

  • W = 30kg

  • 탐욕적 방법의 결과 : (물건2, 물건3) -> 14만원

  • 최적해 : (물건1) -> 15만원

  • 최적 X

• 0-1 Knapsack에 대한 탐욕적 방법3

  • 	무게	값	값/kg
    물건1	5kg	50만원	10만원/kg
    물건2	10kg	60만원	6만원/kg
    물건3	20kg	140만원	7만원/kg

  • 무게 당(kg) 값이 높은 순서로 물건을 채운다.

  • W = 30kg

  • 탐욕적 방법의 결과 : (물건1, 물건3) -> 190만원

  • 최적해 : (물건2, 물건3) -> 200만원

  • 최적 X

• Fractional Knapsack 문제

  • 	무게	값	값/kg
    물건1	5kg	50만원	10만원/kg
    물건2	10kg	60만원	6만원/kg
    물건3	20kg	140만원	7만원/kg

  • 물건의 일부를 잘라서 담을 수 있다.

  • 탐욕적인 방법

  • (물건1 5kg + 물건3 20kg + 물건2의 절반 5kg) -> 30kg, (50만원+140만원+30만원->220만원)

탐욕 알고리즘의 필수 요소

• 탐욕적 선택 속성
  • 탐욕적 선택은 최적해로 갈 수 있음을 보여야한다.
    • 탐욕적 선택은 항상 안전하다.
• 최적 부분 구조
  • 최적화 문제를 정형화하기
    • 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.

• [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명해야 한다.

대표적인 탐욕 기법의 알고리즘들

알고리즘	목적	설명	유형
Prim	N 개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	서브트리를 확장하면서 MST를 찾는다.	그래프
Kruskal	N 개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	싸이클이 없는 서브 그래프를 확장하면서 MST를 찾는다.	그래프
Diijkstra	주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다.	주어진 정점에서 가장 가까운 정점을 찾고,그 다음을 정점을 반복해서 찾는다.	그래프