[알고리즘] - Greedy 알고리즘

-본 내용은 학교 수업을 바탕으로 제가 이해한 것을 정리한 거여서 약간의 오류가 있을 수 도 있습니다

 

GREEDY Algorithm에 대해 

선택지가 여러 개있을 때, 그걸 다 꼼꼼히 보는 게 아니라 좋은 것같아 보이는 것을 선택한다.

 

전체를 보는 것이 아니라 주변을 보고 선택

이게 무슨 말인가

그건 이제 차차 살펴보도록 하자

 

문제하나를 예시를 들겟다.

Coin Change Problem

 - input : 0이상의 정수 k

 - output : K를 만들 수 있는 최소 동전 갯수

 

● 대부분의 나라에서 통하는 알고리즘

  1. k=0이면 그만한다.

  2. K>0이면, K보다 작은 동전 중 가장 액면가가 큰 것을 선택

  3. 그 액면가를 c라고 하면,

       k<- k-c로 줄이고 , 동전 개수 한개를 추가한다.

  4. 이걸 반복한다.

 

※모든 coin system에서 이 알고리즘이 동작하지는 않는다.

가장 큰 단위의 동전을 고르고 나면 가장 작은 부분문제로 가버리니깐 근시안적으로 봤을 때는 최선인것처럼 보인다.

이 문제의 알고리즘이 그리디 알고리즘이다.

 

Greedy algorithm을 설계하는 과정

● 주어진 문제를 해결하기 위해 계속해서 결정을 해야한다.

● DP에서와는 다르게 결정의 순간에 최선을 고르기 위해 모든 경우를 보며 점화식을 찾는 게 아니라

    greedy choice를 한다.

     -즉 멀리 보지 않고 주변만 보고 최선의 선택을 하는 것을 말한다. 

     - 모든 경우 꼼꼼하게 보지 않고 그 상황에서 바로 결정을 내려버림 -> 그래서 이런 방법이 제대로 동작될리가 없는데    가끔 되는 경우가 있어서 되는 이유를 증명해야 한다. 

     -기준에 의해서 그 시점에서 가장 최선인 것 같은 것을 선택한다. 

     -전체적으로 봤을 때는 최선의 선택이 아닐 수 도 있다.

● 그래서 greedy algorithm의 정확성을 증명해야 한다. 

       greedy choice를 해도 그것이 실제로 최고의 선택이라는 것을 증명해야 되는데 이 부분이 어렵다.

 

◎ Greedy 알고리즘으로 동작하는 문제들

Storing Files on Tape

- 마그네틱 테이프에 n개의 파일을 저장할려고 한다.

- 테이프이기 때문에 1차원 배열이라고 생각한다.

-n개 파일의 길이 : L[i] - i번째 파일의 길이

-순서대로 저장한다면 k번째 파일에 접근하기 위해 필요한 cost는

앞에 있는 파일들의 길이의 합이다.

k번째 파일을 읽는 비용은  L[1]부터 자기 자신의 길이 까지 합이다.

일단 저장을 해놓고 나면 자기자신을 읽기 위해서는 내 앞에 있는 것까지의 시간이 추가로 걸린다.

-저장하는 파일의 순서를 잘 조정하면 걸리는 시간을 줄일 수 잇을 것이다.

 1) 모든 파일이 다 같은 빈도만큼 acces 될 것이다.라는 가정을 해보자

 2) n개 중에서 랜덤으로 어느 파일을 접근 할 때 필요한 cost의 기댓값은 

   

같은 확률로 선택되니깐 n분의 1곱해줘야 한다.

3) 만약에 우리가 테이프에 저장되는 순서를 바꾼다면 어떻게 될까

    ㅠ(i)를 i번째 위치에 저장할 파일의 번호라고 하자

테이프에 저장된 순서를 바꿨다.

    ㅠ(1)=6 ...

     파이가 곧 순서이다.

     파이 함수를 우리가 어떻게 설정하느냐에 따라서 cost가 달라진다.

   

 

  문제 : 그러면 어떤 순서로 정하는 게 cost의 값을 최소화할 수 있을까? 

      - 어떤 순서가 최적일까?  

         1번위치에있는 파일은 어느 위치에 있는 파일을 읽을려고 할때마다 1번위치에 있는 파일은 흝고 지나갈 수밖에 없다.

         즉 , 앞에 있는 파일은 여러번 지나가야 한다.

         그러면 앞에 있는 파일을 길이가 짦은 놈으로 두면 되겠다. 그니깐 매번 많이 지나가야 될 놈이면 이왕 짦은거를 두는게 낫지

         그럼 길이가 증가하는 순서대로 놓으면 되겠다

       

       - 알고리즘 

          길이 순으로 file을 정렬한 후 그 순서로 테이프에 저장한다.

           문제는 이 순서가 최선인지 어떻게 확신할까를 증명해야 한다.

           증명해야 될 명제 : 길이를 순서대로 정렬했을 때, cost[ㅠ]의 기댓값이 최소화된다.

          증명 )

라고 가정해보자

그러면 어떻게 되느냐  : i번째 있는 파일의 번호를 a라고 하고,

                                          i+1번째 파일의 번호를 b라고 한다.

                                        a와 b를 바꿔보자

             a를 액세스할 때 필요한 cost는 b의 길이 만큼 증가, b를 액세스할 때 필요한 cost는 a의 길이만큼 줄어들음

            그럼 cost의 기댓값은 b만큼  늘어나고 a만큼 줄어들었으니깐 L[b]- L[a]만큼 늘어났다. 이후 나누기 n을한다

             중요한 건 b의 길이가 a의 길이보다 작으니깐 음수가 되지!!

             a와 b를 바꿧더니 cost가 줄어들었네

             문제의 가정대로  L[ㅠ]에 대해서 E[cost(ㅠ)]가 최소한의 값이 였다면 이건 모순이다.

             (왜 모순이냐고? 앞서 봤던 것처럼 둘의 순서를 바꿧더니 cost가 더 줄어들었으니깐!! L[ㅠ]에 대해서 E[cost(ㅠ)]가 최소                  값  이라고 볼 수 없지, L[ㅠ]에 대해서 E[cost(ㅠ)] <- 이 값보다 더 줄어들은 경우가 나왔으니깐!!)

             그래서 모든 i에 대해서 ㅠ(i)의 길이는 ㅠ(i+1)의 길이보다 크면 안된다.

             그래서 명제가 증명이 된다. (반대된 가정에 의해 발생한 모순증명완료)

   

 

Scheduling Classes

 - 수강신청 시, 어느 요일에 신청할 수 있는 과목 : n개

 - 빨리 졸업하기 위해서는 가능한 많은 과목을 신청해야겠지

 - input : 각 과목의 시작, 끝 시간

 - 문제 : 그러면 어떤 class들을 겹치지 않고 선택하면 최대한 한 요일에 많은 과목을 신청할 수 있을까?

    input : S[1..n] , F[1..n] (S[i]에 시작, F[i]에 끝난다)

    output: 겹치는 게 없는 가능한 많은 클래스들을 포함하는 집합

  ○ 가능한 Greedy choice : 1. 빨리 시작하는 것을 먼저 선택한다. 

                                     2. 길이가 짦은 것을 먼저 선택 

                                     3. 서로 겹치는 class 갯수가 가장 적은 것을 먼저 선택한다.

                                     4. 종료시각이 가장 이른 클래스를 먼저 선택

        가장 최적의  해를 찾을 수 있는 올바른 Greedy choice를 찾아야 한다.

         1. 시작시간이 가장이른것을 먼저 선택했을 때, 가장 많은 클래스르 고를 수 없더라는 반례찾는다.

           

         위 긴 막대기는 제일 빨리 시작하지만 길이가 길기 때문에,

        가장 최적의 해는 밑에 4개의 클래스를 선택하는 것임으로 1번은 올바른 그리디 초이스 기준이 될수 없다. 

        2. 길이가 짦은 클래스를 먼저 선택

       

          길이가 긴 것 두개가 겹치지 않고 있는 경우와 길이가 짦은 것 하나가 있는 경우 ,

            2번의 그리디 초이스 기준에 의해서는 길이가 짦은 것 하나의 경우를 선택하게 되므로 가장 많은 클래스를         고를 수 없으니깐 가장 최적의 해가 아니다. 

        3. 서로 겹치는 클래스의 개수가 가장 적은 것들을 먼저 선택

           이 경우 가장 많은 클래스들을 선택할 수 없는 경우가 있냐는 반례를 찾아보자

            

           이 경우에는 겹치는 클래스가 가장적은 맨 밑의 것이 선택이 되겠지

           애를 선택하고 나면 총 3개 선택 가능 

           그런데 최적의 해는 4개 만들기 가능

       4. 종료시각이 가장 이른 클래스를 먼저 선택

           이게 가장 최선의 선택 

        

  ○ Greedy choice의 기준

       - 종료시각이 가장 이른 클래스를 먼저 선택

       - 종료시간을 기준으로 오름차순으로 정렬

       - 겹치는 애들 제외

       - 시작시간이 1번이 끝나는 시간 뒤에 바로 있는 애 선택

 

  ○ Greedy algorithm

       -클래스들을 F[]값에 대해 정렬한 후에 차례대로 보며 선택할 수 있으면(앞서 선택한 것과 겹치지않으면) 선           택

         - class i의 시작 시각: S[i], 종료 F[i} 둘다 정렬한다.  즉 클래스들을 정렬한다. 

         - count : 선택된 클래스들의 갯수

         - X [] : 선택된 클래스들을 저장할 배열 

        ⊙ 종료시간이 이른 애를 기준으로 정렬을 한다. 

           일단 1번클래스는 무조건 선택을 한다. (1번은 종료시간이 제일 이른 클래스) 

           2번부터 보는데, 언제 시작하는 지를 본다. 전에 있던 애가 끝나고 난 뒤에 시작할 수 있는지를 봐야겠지

           시작하는 시간이 앞에 있던 애 끝나는 시간 뒤에있다면 선택할 수 있으니깐 

           그 클래스를 선택하여 count를 증가시킨다. 그리고 X[count] 배열에 그 선택된 클래스를 넣는다.

           만약 전에 있던 애가 끝나기 전에 시작하는 애라면 겹치는 애니깐 count 불가

           마지막에는 배열 x를 리턴한다.

   

    ○ GreedtSchedule에 대한 정확성 증명

       명제 :    가장 먼저 끝나는 클래스를 포함하는 conflict-free 스케쥴이 존재한다. 

      즉 그렇기 때문에 가장 먼저끝나는 클래스를 포함해도 무방하다.

        증명 ) ⊙ f를 가장 먼저 종료하는 클래스라고 하자

                ⊙ X : maximal confilct-free 스케쥴이고 f는 X에 속하지 않는다고 가정

                ⊙ g : X에 포함 된 것 중 가장 먼저 끝나는 클래스

                - 그러면 f가 g보다 먼저 끝나기 때문에, X에서 g를 빼고, f를 넣어도 여전히 confilct-free하다

               

                - 즉 아래의 사진 역시 maximal conflict-free 스케쥴이다. 

            우리가 궁극적으로 보이고자 하는 궁극적인 명제 :  그리디 스케쥴이 optimal한 스케쥴이다.

            즉 가능한 최대갯수의 클래스들을 포함하게 되나

            증명 ) ⊙ f를 가장 먼저 종료하는 클래스라고 하자

                    ⊙  A를 f와 겹치지 않는 클래스들의 집합이라고 하자

                    ⊙ 아까 위의 증명에서 f를 포함한 optimal 스케쥴이 존재한다고 했으니깐 f를 선택한 스케쥴 중에                           서 최선인 것이 optimal 스케쥴이다. 

           증명 2) 교환하는 알고리즘 사용

                   <g1......g(j-1)..g(j)....gk>를 그리디 스케쥴

                   <g1......g(j-1)..c(j)........cm>을 optimal 스케쥴이라고 하자

                    즉 j 번쨰에 처음 다른게 나와. 그리고 k<=m이다.

                    ⊙ 교환 작업

                       optimal 스케쥴에서 cj를 빼고 gj를 넣어보자 

                         그럼 <g1......g(j-1)..g(j)........cm> 이것도 서로 겹치는 게 없으니깐 confilct-free->optimal 스케쥴

                      왜 안 겹쳐? 왜냐면 gj는 앞의 gj-1과 겹치지 않는 것 중에서 가장 빨리 종료하는 클래스니깐 

                      cj랑 비교하게 되면 cj 종료시각 보다 gj 종료시각이 더 이르다. 

                      그래서 앞에서도 겹치지 않고 뒤에서도 겹치지 않는다. 즉 gj는 cj+1과도 겹치지 않는다. 

                      교환 작업을 반복적용통해 같은 부분이 많아지도록 만들면 

                     

                        이것도 optimal 스테쥴

                      -그런데 여기서 문제 , 정말  k번째 이후에 ck+1이 존재 할 수 있을까? 

                        즉 k<m이면, ck+1은 gk랑 겹치지 않고 이후에 시작하는 클래스인데, 

                        그런게 존재하면 우리의 그리디 알고리즘은 k+1번째도 찾을 수 밖에 없다. 

                         따라서 k=m이여야 한다.

                         그래서 그리디 스케쥴은 optimal 스케쥴이다. 

                         

 

Greedy algorithm : 정확성 증명의 패턴 

 

(Exchange argument) 

Greedy solution과 optimal solution이 다르다고 가정한다.

두 solution에서 처음으로 다른 부분(다른 결정을한부분)에 대해서

그 부분을 Greedy solution의 greedy choice로 대체해도 여전히 optimal solution이 된다는 것을 증명한다. 

(이 과정에서 수학적 귀납법을 사용한다) 

마무리