[컴퓨터알고리즘] 13. 그리디 알고리즘

Greedy Algorithms 그리디 알고리즘: 각 단계에서 최적의 수를 찾아 전역 최적해를 구함.

- ex) 수업 시간표 짜기: (1) 젤 빨리 끝나는 과목 먼저 신청 (2) 첫번째 과목 끝난후 시작해서 젤 빨리 끝나는 과목 신청

- 그리디 알고리즘은 지역 최적해로 전역 최적해를 구하는 방식. DP로 얻은 최적해보다 덜 최적일 수 있음.

 

Activity Selection Problem 행동 선택 문제

- 입력: n개의 행동이 담긴 집합 S = {1,2,..n}. 시작 시간 si, 종료 시간 fi라 할때 행동 i는 [si,fi)를 차지함.

- 목표: 호환가능한. 안겹치는 행동들로 최대 개수의 행동을 하기. (시간을 얼마나 쓰는진 고려대상x)

S = { [1,4), [5,7), [2,8), [3,11), [8,15), [13,18) }

// S를 종료시간 오름차순으로 정렬해서 사용한다.

 

1) 최적의 부분구조 결정

2) 재귀적 해결법 수립

3) 그리디로 풀면 오직 하나의 부분문제만 존재함을 보이기

4) 항상 그리디로 푸는게 안전한 이유 증명

5) 재귀적인 그리디 알고리즘 작성

6) 반복적인 알고리즘으로 변환하기

 

S_ij = a_i 이후 시작되고 a_j 시작 전 끝나는 행동 a_k들 집합

       = {a_k 가 S의 원소 : f_i <= s_k < f_k <= s_j }

 

A_ij가 S_ij의 호환되는 행동들로 구성된 최대 크기 집합이라고 하자.

A_ij에 속하는 a_k를 선택하면 -> 부분문제 2개 생김. (1) S_ik로도, (2) S_kj로도 찾아야 함

|A_ij| = |A_ik| + |A_kj| + 1    // |A|는 카디널리티, 원소 갯수

- 증명: Skj의 호환되는 행동들로 구성된 집합 |A'_kj| > |A_kj| 가 존재한다고 하면 |A_ik| + |A'_kj| + 1 >  |A_ik| + |A_kj| + 1 = |A|, |A|가 최적해라는 것과 모순된다.

 

One recursive solution - DP로 풀어보면?

A_ij는 S_ik와 S_kj 두 부분문제의 최적해들을 포함해야 함

c[i,j] = { 0      # if S_ij = 공집합

             max {c[i,k]+c[k,j]+1}      # if S_ij != 공집합. S_ij에 속하는 모든 a_k 비교해 최댓값 구함.

어떤 a_k를 골라야 할지 모르므로, 모든 k를 시도해서 table을 찾아야 하는 결과...

 

Greedy Choice Property

- 중복되는 부분문제들과 최적해 특성 여기서도 있음.

- 그리디만의 특성: locally optimal choices의 시퀀스가 optimal solution.

 

그리디 특성 증명

재귀적인 그리디 알고리즘 REC-ACTIVITY-SELECTOR(s,f,k,n)

반복적인 그리디 알고리즘 GREEDY-ACTIVIRY-SELECTOR(s,f)