알고리즘 - 탐욕 기법

✔ 탐욕 기법(Greedy)

• 최적해를 구하는데 사용되는 근시안적인 방법
  • 가능한 해들 중 가장 좋은(최대 또는 최소) 해를 찾는 문제.
  • 일반적으로 떠오르는 생각을 검증없이 구현하면 Greedy 접근.
    • 단순하며, 제한적인 문제들에 적용.
  • 각 선택 시점에서 이루어지는 결정은 지역적으로 최적, 최종적인 해답이 최적이라는 보장이 없음 => 검증 필수.
  • 단점 : 최적해를 반드시 구한다는 보장이 없음.

◾탐욕 알고리즘 필수 요소

• 탐욕적 선택 속성(Greedy Choice Property) : 탐욕적 선택은 최적해로 갈 수 있음을 보여라.
  • 탐욕적 선택은 안전하다.
• 최적 부분 구조(Optimal Substructure Property) : 최적화 문제를 정형화하라.
  • 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.
• [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명하라.

◾대표적인 탐욕 알고리즘

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

1. 배낭 짐싸기(knapsack)

• knapsack 정형적 정의
  • S : {item1, item2, ..., itemn}, 물건의 집합.
  • wi : itemi의 무게.
  • pi : itemi의 값.
  • W : 배낭이 수용할 수 있는 최대 무게.
  • 문제 정의 : 물건을 선택하는 부분 집합(A) 찾기
    • A의 무게 합 <= W.
    • A의 값 합이 최대.
• knapsack 문제 유형
  • 0-1 Knapsack
    • 배낭에 물건을 통째로 담아야 하는 문제
    • 물건을 쪼갤 수 없는 경우
  • Fractional Knapsack
    • 물건을 부분적으로 담는 것이 허용되는 문제
    • 물건을 쪼갤 수 있는 경우

◾0-1 Knapsack 문제

• 완전 검색 방법
  • 완전 검색으로 모든 부분 집합 구하기.
  • 총 무게가 W를 초과하는 집합 제외. 나머지 집합에서 총 값이 가장 큰 집합 선택.
  • 물건의 개수가 증가하면 시간 복잡도 지수적 증가.
    • 크기 n인 부분 집합의 수 2n
• 탐욕적 방법1 : 값이 비싼 물건부터 채우기.
  • W : 30, {w, p} : {{25, 10}, {10, 9}, {10, 5}
  • 탐욕적 결과 : {25, 10} => 10
  • 최적해 : {10, 9}, {10, 5} => 14
  • 따라서, 최적이 아님.
• 탐욕적 방법2 : 무게가 가벼운 물건부터 채우기.
  • W : 30, {w, p} : {{25, 15}, {10, 9}, {10, 5}
  • 탐욕적 결과 : {10, 9}, {10, 5} => 14
  • 최적해 : {25, 10} => 15
  • 따라서, 최적이 아님.
• 탐욕적 방법3 : 무게 당 값이 높은 순서로 물건 채우기.
  • W : 30, {w, p} : {{5, 50}, {10, 60}, {20, 140}
  • 탐욕적 결과 : {5, 50}, {20, 140} => 190
  • 최적해 : {10, 60}, {20, 140} => 200
  • 따라서, 최적이 아님.

0-1 Knapsack 문제에서는 탐욕적 방법으로 문제를 해결하기 어려움.

◾Fractional Knapsack 문제

• 물건의 일부를 잘라서 담을 수 있음.
• 탐욕적 방법 : 무게 당 값이 높은 순서로 물건 채우기.
  • W : 30, {w, p} : {{5, 50}, {10, 60}, {20, 140}
  • {5, 50} : 5, {10, 60} : 5, {20, 140} : 20 => 무게 30 : 값 220

2. 회의실 배정

• 회의실 배정
  • A : {A1, A2, ..., An}, 회의의 집합(시작 시간, 종료 시간).
  • si : Ai의 시작 시간.
  • fi : Ai의 종료 시간.
  • 서로 겹치지 않는(non-overlapping) 최대 갯수의 활동 집합 S 구하기.

◾회의실 배정 문제

• 양립 가능한 활동들의 크기가 최대가 되는 S0, n+1의 부분 집합 선택.
  • 종료 시간 순 활동 정렬
  • S0, n+1 : a0 종료 시간부터 an+1의 시작 시간 사이에 포함된 활동들.
• 탐욕적 방법 : 가능한 회의 중 종료 시간이 가장 빠른 회의부터 선택.
  1. ai 종료 시간부터 시작 가능한 활동 중 종료 시간이 가장 빠른 am 선택.
  2. Si, j = {am} ⋃ Sm, j의 해집합
     • 가장 늦은 회의 종료 시간 : 11일 경우
     • S1, 11 에 대해 am1 선택.
     • Sm1, 11 에 대해 am2 선택.
     • ...
     • Sm(k-1), 11 에 대해 amk 선택. 종료.
     • k개의 회의 선택.

// A : 활동들의 집합, S : 선택된 활동(회의)들 집합
// si : i 활동 시작 시간, fi : i 활동 종료 시간, 1 <= i <= n

Sort(A) // by finish time(종료 시간순 오름 차순 정렬)
S <= {A1}
j <= 1
For i in 2 -> n
	If fj <= si
    	S <= S ⋃ {Ai}
        j <= i