04. 탐욕법

[1. 개요]

탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다.

각 단계마다 답의 한 부분을 만들어 간다는 점에서 

완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없으나,

각 단계마다 지금 당장 가장 좋은 방법만을 선택한다는 것이 다르다.

 

그래서, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

 

탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다.

=> 모든 단계를 고려하는 동적 계획법이 틀릴 이유가 없기 때문

 

그럼에도, 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 너무 크기 때문이다.

 

탐욕적 알고리즘을 설계하는 좋은 방법은

간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것

 

[2. 사용되는 경우]

A. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제인 경우

=> 동적 계획법보다 수행 시간이 훨씬 빠르다.

 

B. 시간/공간적 제약으로 인해 최적해를 찾기 어려운 경우, 적당히 괜찮은 값(근사값) 을 찾고자 하는 경우

 

알고리즘 문제에서는 A 인 경우로만 사용된다고 볼 수 있다.

그래서 여러개의 탐욕적인 방법 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기가 어렵다.

=> 알고리즘의 정당성을 증명하는 과정을 연습해야 한다.

 

 

[3. 정당성 증명]

예제) 각각의 회의 시간이 주어지고,

서로 겹치지 않는 회의들만을 골라낼 때, 최대 몇개나 선택할 수 있는가?

1. 완전 탐색 풀이
   => 집합의 크기가 n 일 때, 부분 집합의 개수는 2^n 이므로 시간 제한에 걸린다.
   => 재귀적인 방법으로 부분 집합을 만듬
   ==> 각 단계마다 회의 A 를 선택하는 경우와 선택하지 않는 경우... 
2. 탐욕 알고리즘
   = 오답 =>  길이가 짧은 회의 부터 선택
   ==> 반례, A: [0, 5], B: [5, 10], C: [4, 6] 일 때, C 를 선택하면 A, B 는 회의를 진행하지 못한다.
   ==
   = 정답 => 길이와 상관 없이 가장 먼저 끝나는 회의부터 선택한다.

위 탐욕 알고리즘의 정당성 증명과정

=> 탐욕 알고리즘 정당성 증명은 많은 경우 일정한 패턴을 갖는다.

=> 이 패턴은, 탐욕 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 두 가지의 속성을 증명하여 보인다.

탐욕적 선택 속성

 

위 속성이 성립할 경우, 각 단계에서 탐욕적인 선택을 해서 손해 볼 일이 없다는 것을 알 수 있다.

 

== 가장 종료 시간이 빠른 회의(Smin)를 포함하는 최적해(S)가 반드시 존재한다.

1. S 의 최적해 중, Smin 을 포함하지 않는 답이 있다고 가정을 한다.
2. 위 답에서 첫 번째로 진행하는 회의를 지우고, Smin 을 추가한다.
3. 지워진 회의는 Smin 보다 일찍 끝날 수 없다.
   => Smin 이 가장 먼저 끝나기 때문에,
4. 두번째 회의와 Smin 은 겹치지 않는다.
   => 지워진 회의와 Smin 은 겹칠 수 있어도,
   => 두번째 회의와 지워진 회의는 겹칠 수 없기 때문에
5. 그래서, 새로 만든 목록도 최적해 중 하나가 된다.

=> 항상 Smin 을 포함하는 최적해는 존재한다.

 

관련 예제) 탐욕법 관련 예제 정리 필요...

 

 

[4. 최적 부분 구조]

항상 최적의 선택만을 해서 전체 문제의  최적해를 얻을 수 있음을 보여야 한다.

탐욕법의 정당성을 위해 증명해야 할 두번째 속성은 최적 부분 구조이다.

 

이 속성은 대개 매우 자명해서 따로 증명할 필요가 없는 경우가 대부분이다.

 

위 예제에서 첫번째 회의를 잘 선택하고 겹치는 회의를 모두 걸렀다면,

남은 회의 중에 당연히 최대한 많은 회의를 선택해야 한다.

 

 

[5. 동적계획법으로 풀이하기 여려운 경우]

예제) 각 팀이 n 명으로 구성되어 있고, 1대1 경기를 벌여 더 많은 승리를 가져가는 팀이 우승하는데,

상대방 팀 선수들의 출전 순서를 알고 있을 때,

어느 순서대로 선수들을 내보내야 승리 수를 최대화 할 수 있는가?

(레이팅이 같을 경우 우리 선수가 승리한다고 가정)

 

1. 완전 탐색
   => 우리 팀 출전 방식 조합을 만드는 경우의 수는 n! 이므로, n 이 조금만 커져도 시간 초과
2. 동적 계획법
   => n! 개의 답을 모두 생성하는 완전 탐색 알고리즘에 메모이제이션 적용 방법
   => 각 선수를 지금까지 순서에 추가했는지를 나타내는 bool 배열 만을 받는 부분문제
   => order(taken) = taken 에 각 선수 출전 여부가 주어질 때,
                                남은 선수들을 적절히 배치해서 얻을 수 있는 최대 승수
                                // 캐시를 어떻게 구성하지?
   => taken에 포함된 true 의 개수를 세면,
   => 이번에 선택할 선수가 상대팀의 몇번째 선수와 경기하게 되는지 알 수 있다.
   => 시간 복잡도 O(n*2^n)
   
   
3. 탐욕 알고리즘
   => W: 상대방 선수(A) 를 이길 수 있는 한국 선수가 있는 경우, 그 중 레이팅이 가장 낮은 선수를 상대와 경기 시킨다.
   => L: 상대방 선수(B) 가 한국팀의 모든 선수보다 레이팅이 높다면, 남은 선수 중 레이팅이 가장 낮은 선수과 경기 시킨다.

=== 탐욕적 선택 속성 증명

우리가 하는 선택을 포함하는 최적해가 존재함을 증명해야 한다.

W 인 경우와 L 인 경우로 나눠 탐욕적 선택이 옳다는 것을 증명하도록 한다.

 

L(질 수 밖에 없는) 경우를 고려

1. 레이팅이 가장 낮은 선수 A 대신 B 를 내보내는 최적해가 있다고 가정한다.
2. 최적해에서 이 두 선수의 순서를 바꿔본다.
   => ... B ... A ... => ... A ... B ...
3. 기존 최적해에서 A 와 대결했던 선수는 레이팅이 더 높은 B 를 상대해야 한다.
4. 따라서 승수가 더 줄어들일은 없다
5. 이 경기에 A 를 내보내는 최적해가 존재 함을 알 수 있다.

W(이길 수 있는 경우를 고려)

1. 승리 할 수 있는 선수 중 레이팅이 가장 낮은 A 대신 레이팅이 더 높은 B 를 내보내는 최적해가 있다고 가정
2. 최적해에서 이 두 선수의 순서를 바꿔본다.
   => ... B ... A ... => ... A ... B ...
3. 기존 최적해에서 A 와 대결했던 선수는  레이팅이 더 높은 B 를 상대해야 한다.
4. 같은 전개로 이 순서 또한 최적해이다.

=== 최적 부분 구조 증명

첫번째 경기에 나갈 선수를 선택하고 나면, 남은 선수들을 배정하는 부분 문제를 얻는다.

이때 남은 경기에서도 최다 승을 얻어야, 전체에서 최다 승을 얻을 수 있다.

 

 

[6. 탐욕적 선택 속성 증명 패턴]

1. 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정한다.
2. 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만든다.

 

[7. 탐욕적 알고리즘 레시피]

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할 지 결정한다.
3. 아래 두 가지 속성을 증명한다.
   A) 탐욕적 선택 속성
   => 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 증명한다.
   => 보통, 우리가 선택한 답과 다른 최적해가 존재함을 가정한다.
   => 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이도록 한다.
   
   B) 최적 부분 구조
   => 대부분의 경우 자명하다.