[알고리즘] 16 Greedy Algorithms

• 최적화를 위한 알고리즘은 너무 많은 단계를 거칠수도 있다
  dynamic programming 은 overkill -> greedy algorithm

• greedy algorithm 그 순간에 best인 선택을 한다

• 그리디는 반드시 최적해를 구하지는 않을 수도 있지만, 대부분 가능

1. activity-selection problem
   S = {a1, a2, ... an} activities
   ai ( 0< si < fi < inf) [si, fi)]
   intervals 가 안겹치면 양립가능한 activity

activity-selection problem
: 양립가능한 activity들을 가장 많이 뽑아내는

: finish time의 단조증가로 정렬되어있다.

DP : 여러 choices를 고려한다
: 우리는 그리디 초이스 하나만 고려해야한다 : -> 오직 하나의 부분문제만 남는다
1. recursive greedy algorithm
2. -> iterative one

Sij= {ak <S : fi <= sk < fk <= sj}
Aij가 ak 를 포함한다면

ak를 최적해에 포함하고 , Aik 와 Akj 를 찾아 , Aij 는 이들의 합집합입니다

Aij 는 Sik와 Skj의 두가지 부분문제의 최적해를 반다시 포함한다

-> 재귀적 해 (by DP) : ak를 선택할 수 있다는 확신이 없다

Sij의 크기 = c(i,j )
c(i,j) = c(i,k) + c(k,j) +1

= { 0 (if Sij = 0) / max(c(i,k) + c(k,j) +1) (if Sij != 0)

-> 그리디 초이스로 전환

우리의 Optimal solution 에 넣을 첫번째 솔루션을 선택한다면?
-> 그리디 초이스에서 반드시 a1을 최적해로 넣을 것이다 ( 마감시간에 따른 단조증가 배열이라면)
:: am을 Sk 에서의 젤빠른 마감 활동이면 am 은 Ak 에 반드시 포함된다
증명) 젤 빠른 활동이 am일떄/ am이 아닐때

-> 그리디 알고리즘은 탑다운 방식이다
1. 재귀적 방식

RECURSIVE-ACTIVITY-SELECTOR(s, f, k ,n)
m = k+1
while m <= n and s[m] < f[k]:
	m = m +1
if m <= n:
	return {am} 합집합 RECURsIVE-ACtiVIty-SELECTOR(s,f,m,n)
else:
	return 공집합

2. 순환형방식

GREEDY-ACTIVITY-SELECTOR(s,f)
n = s.length
A = {a1}
k = 1
for m = 2 to n
	if s[m] >= f[k]
    	A = A 합집합 {am}
        k = m
return A

둘 모두 finish time으로 단조증가 정렬되었다는 가정하에 O(n) 만큼 시간이 걸린다

greedy strategy

1. 문제의 최적 부분구조를 정의한다
2. recursive solution 을 도출한다
3. 각 recursion 단계의 optimal solution 이 greedy solution 임을 증명한다
4. 그리디 초이스로 만들면 오직 하나의 부분구조만 존재함을 보여라
5. 재귀적 그리디 알고리즘을 도출해라
6. 재귀 알고리즘을 반복 알고리즘으로 바꿔라

0-1 problem (dynamic programming) vs fractional knapsack problem (greedy)

fractional 은 단위무게당 가격 기준으로 먼져 넣고 , 남은 공간은 분할해서 채우면 된다ㅏ