[SW Expert Academy] Advanced-3 탐욕 알고리즘

탐욕 알고리즘(Greedy Algorithm)은 최적값(Max, Min)을 구하는 문제로, 순간 순간 최적해를 고르면서 해결한다. Greedy Algorithm는 하나의 문제에 대해 해가 다수일 수 있다. The 최적해를 구하는 게 아닌 An 최적해를 구하는 것이 목적이다.
하지만 순간 순간 고르는 최적의 선택이 글로벌한 최적값은 아닐 수 있음을 유의해야한다.
(Local optima가 Global optima를 의미하지 않는다.)

플로우 1. 동전 거스름돈 문제 2. Knapsack (배낭문제) 문제 3. 회의실 배정 문제를 통한 Greedy 증명

1. 동전 거스름돈 문제

-최소의 갯수의 동전으로 거스름돈을 주는 방법은?

-순간 순간, 가장 비싼 동전을 고르고, 거스름돈을 초과하지 않는지 조사한다.

2. Knapsack 문제

-Problem

1)무게 W를 담을 수 있는 배낭이 있다.

2)각 무게(W(i)), 가격(P(i))가 표기된 item(i)들의 집합 S가 있다. (S={item(1), item(2), ... , item(n)})

3)배낭의 무게 W를 초과하지 않으면서, 물건들의 가격의 합이 최대가 되도록 되는 S의 부분 집합 A를 구하자.

-Knapsack 문제는 크게 2가지 종류가 있다.

->0-1 Knapsack 문제: 물건을 쪼갤 수 없다.

->Fractional Knapsack 문제: 물건을 쪼갤 수 있다.

-0-1 Kapsack 문제 풀기

1)완전 검색

-S의 부분집합이 될 수 있는 모든 A(i)를 구한다.

-A(i)의 item의 무게의 합이 W가 초과이면 A(i)를 제거한다.

-나머지 중 최대의 가격(P)를 고른다.

-> 시간 복잡도 O(2^n)

2)Greedy

-비싼애부터? 가벼운애부터? 가치/무게가 높은애부터?

-하지만, 이 선택이 글로벌한 최적값을 보장하지 않는다. 

-풀이가 될 수 없다.

-Fractional Knapsack 문제 풀기

1) Greedy

-가치/무게가 높은애부터 고르면?

-글로벌한 최적값을 보장할 수 있다. 

3. 회의실 배정 문제

-Problem

1) 시작 시간(S(i)), 종료 시간(F(i))를 가지는 미팅(A(i))의 집합 S가 있다.

2) 서로의 미팅 시간을 겹치지 않으면서 회의실에 최대한 많이 배정해야 한다.

-Solution (수도코드)

Sort S by finish time //S=(a1, a2, .... an)

A <- {a1}

j<-1

for i <- 2 to n:

 if si > fj:

  A <- {ai}

  j <- i

-증명하기

[Global 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 보여야 한다.
즉, 매번의 선택이 항상 옳고 (= 최적해의 일부분이 되고), 선택 후 쪼개진 하위문제도 올바름을 보여야 한다.

1) 탐욕적 선택 증명
-종료시간이 가장 빠른 a[m]을 선택하는 것은 항상 안전하다.
-> [i,j]동안 가장 많은 미팅을 가지는 집합 A[ij]가 있다고 하자.
-> a[k]는 가장 종료시간이 빠른 A의 원소이다.
-> (1) a[m] = a[k]라면: a[m]이 A[ij]에 포함되므로 안전하다.
-> (2) a[m] != a[k]라면: A[ij]에서 a[k]를 제외하고 a[m]을 포함한다면 a[k]의 종료시간보다 a[m]의 종료시간이 빠르거나 같으므로 양립 가능한 해가 된다. 따라서 안전하다.

2) 문제의 해는 탐욕적 선택과 하위 문제의 최적해를 합한 것이다.
- A[ij]에서 a[m]을 선택하면, 하위 문제 A[im]과 A[mj]가 존재한다.
-만약 A[im]이 공집합이 아니라면, A[im]에 속하는 활동 a[k]는 a[m]보다 종료 시간이 빠르다는 것을 의미한다.
-이는 가장 빠른 종료 시간 a[m]을 선택한 것과 모순된다.
-따라서 A[im]은 공집합이다.

-> 사이트 강의에는 이렇게 되어있음. 다만 좀더 명확히 하자면, A[ij]에서 a[m]을 선택하면, 하위 문제는 엄밀히 말해 A[i, s[m]], A[f[m], j]로 나뉜다고 생각함. 
->여기서 s[m]은 a[m]의 시작시간, f[m]은 a[m]의 종료시간임
->그런데 A[i, s[m]]이 공집합이 아니라고 가정하자.
->이는 a[m]의 시작시간 s[m]보다 더 작은 종료시간 f[k]를 가지는 a[k]가 있다는 것을 의미함.
-> 즉, A[ij]의 원소 a[k]의 종료시간(f[k]) < a[m]의 시작시간(s[m]) < a[m]의 종료시간(f[m]) 이므로, a[m]의 종료시간보다 a[k]의 종료시간이 빠르게 됨
-> 이는 가장 빠른 종료 시간 a[m]을 선택한 것과 모순된다.
->따라서 A[i, s[m]]은 공집합이다.

3) 결론적으로, 탐욕적 선택(종료 시간이 가장 빠른 a[m]을 선택하는 것)는 항상 안전하고, 원문제의 최적화가 탐욕적 선택과 하위문제의 최적화를 합한것임을 증명하였다.
그러므로 Local optima가 global optima가 된다.

Reference
https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3FuEG6AMkBBAQ3