[ 알고리즘 ] 7. Greedy 알고리즘 (2)

An Activity-Selection Problem

: 각 Exclusive한  Activity 에 스케줄이 있고,

   그 Activity들의 수를 최대한 많이 선택하는 문제

 

  ex) 주어진 시간동안 많은 놀이기구를 타는 경우

 

 

[ 2 ,3 )  [ 3, 5 ) 는 서로 Mutually compatible하다.

*Compatible : 'Overlap이 없다'

 

---

 

▶ Compatible한 Activity들을 최대한 많이 선택하기

 

 

si  = 시작하는 시간  → [

fi  = 끝나는 시간      →  )

 

 

---

 

● S 라는 set은 n 개의 activity 가 있다.

● Si,j 는 ai로 시작해서 aj로 끝나는 S의 Subset이다.

 

 

얘를 DP로 풀어보자.

 

1. 우선 Si,j에 대한 Optimal schedule을 구한다.

   - 양 끝 ai, aj빼고 Optimal을 구해보자 

 

2. Sij에서 ak를 골라서 Sik, Skj를 만든다.

   - ak를 선택했을 때 Compatible하지 않은 건 제외시킨다.

 

3. Sik , Skj 에서 Optimal한 값을 구한다.

 

4. ai + [ Sik의 Optimal한 값 ] + ak + [ Skj의 Optimal한 값 ] + a

 

아래 사진에서 ,
 cik = Sik에서 구한 Activitiy 개수

 1 = ak 도 Activity니까

 

 

---

Dynamic Programming    VS   Greedy 

 

● SubProblem의 개수

● DP : J - i - 1

전체 있는 개수는 J개

- ai 는 하나 골랐으니 subproblem이 아니고

- ak 도 뽑았으니 subproble에서 1개 제외.

 

 

 

● Greedy : 1

 

▶ 하나의 SubProblem에 대한 두 개의 차이

 

- DP : 하나에 Subproblem에 대한 모든 경우의 수에서 가장 좋은 값을 가져옴

- Greedy : 현재 단계에서 가장 좋은 선택을 하고 다음 Subproblem으로 넘긴다.

 

 

 

이걸 Greedy에서 생각해보면

S0,12를 생각해보자.

 

1. 현재 Finish time이 가장 빠른 놈 고르기. 
   = a1

 

2. a1 Finish time에 Compatible한 놈 으로 찾기

   = si 가 fi 이후인 애!  

   = a2 ,a3 안 됨, a4가능!

 

3.  a4 Finish time에 Compatible한 놈 으로 찾기

...

 

Running time

: 한 번씩만 돌면 됨

   = 세타(n)

 

하지만 이렇게 한 번씩 돌기 위해선 Sorting이 되어있는 상태여야 한다.

Sorting , scan을 해야하므로

Running time  = Sorting 시간 + Scan 시간을 생각해야 한다. ( scan 시간은 이미 세타n으로 구함 )

=  무슨 Sorting 알고리즘이냐에 따라 나뉜다.

= 주로 빠른 게 세타(n * log n )

 

Running time = Sorting 시간 + Scan 시간

                      =  세타(n * log n ) + 세타(n)

---

주의할 점

● 가장 많은 것을 하려고 할 땐 Greedy가 잘 맞다.

 

● 하지만 가장 오랜 시간동안 하는 걸 생각할 땐 Greedy가 바람직하지 않을 수 있다.

  ex1)
  - 하나의 강의실을 가장 많은 사람이 쓰게 하는 방법 = 10분 15분 20분 Compatible하게 사용

         = Greedy로 하면 됨

 

  -  하나의 강의실이 가장 오래 사용되게 하는 방법 = 2시간 한 번 사용하는 사람한테 줌

 

ex2) 

     - 가장 많은 놀이기구를 타는 법 : Greedy

     - 가장 오래 놀이기구같은 걸 하는 법 : 사파리 이런 거 타야함 (개수가 많진 않다.)

 

 

● 그럼 언제 Greedy 써야 함?

   = 하위 문제에 대해서 Subproblem 생각 안 하고, 현재에 가장 좋아보이는 선택을 하면 됨

   = 다음 Subproblem 생각 안 하는 YOLO 알고리즘이라 생각하자.

   

 

 

 

 

(출처)

한동대학교 용환기교수님 - 알고리즘