안녕하세요. IT 엘도라도 에 오신 것을 환영합니다.
글을 쓰는 것은 귀찮지만 다시 찾아보는 것은 더 귀찮습니다.
완전한 나만의 것으로 만들기 위해 지식을 차곡차곡 저장해 보아요.   포스팅 둘러보기 ▼

자료 구조, 알고리즘 (Data Structure, Algorithm)

그리디 알고리즘 (Greedy Algorithm) 정당성 증명 방법

피그브라더 2020. 3. 29. 15:56

1. 그리디 알고리즘 정당성 증명

"매 순간 내리는 선택을 포함하는 최적해가 반드시 존재한다"를 증명하면 된다. 늘 그렇듯 기초가 가장 중요하므로, 쉬운 문제들을 예시로 삼아서 그리디 알고리즘의 정당성을 어떻게 증명하는지 한 번 살펴보도록 하자.

 

2. 백준 1931번 문제 <회의실 배정>

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

종료 시간이 가장 빠른 회의를 m이라고 하자. 이때 m이 최적해에 포함되지 않는다고 가정하자. 그러면 최적해의 회의들 중 종료 시간이 가장 빠른 회의를 m으로 대체하여 또 다른 최적해를 얻을 수 있다. 따라서 m을 포함하는 최적해는 반드시 존재한다. 그러면 이제는 m을 선택했다는 가정 하에 m을 제외한 나머지 회의들에 대해 동일하게 생각해보자.

 

전역 최적해를 얻기 위해서는 여기서도 최적해를 얻어야 한다. 그렇지 않으면 여기서 얻는 최적해를 이용하여 더 좋은 전역 최적해를 얻을 수 있어서 모순이 발생하기 때문이다. 따라서 이제는 m을 제외한 나머지 회의들에 대해서 "종료 시간이 가장 빠른 회의를 포함하는 최적해가 존재한다."를 증명하면 되고, 이는 위에서 했던 증명과 동일하다. 결국 이런 식으로 반복하게 되면, 매 순간 남은 회의들 중에 종료 시간이 가장 빠른 회의를 선택함으로써 전역 최적해를 얻을 수 있다는 것이 증명된다.

 

3. 백준 11047번 문제 <동전 0>, 5585번 문제 <거스름돈>

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

맞춰야 하는 금액이 K원이고, K원 이하의 크기를 가진 동전들을 크기 순서대로 내림차순 정렬했을 때 Xn, Xn-1, Xn-2, . . . , X1이라고 가정하자. 그리고 최적해가 (Xn-1 * Cn-1) + (Xn-2 * Cn-2) + . . . + (X1 * C1)이라고 가정하자. 이는 Xn-1 동전 Cn-1개, Xn-2 동전 Cn-2개, . . . , X1 동전 C1개를 사용한다는 것을 의미한다. 이때 Ci는 0 혹은 양의 정수이다(1 ≤ i ≤ n - 1). 즉, 최적해가 Xn을 포함하지 않는다고 가정하는 것이다.

 

 

그러면 Xn-1은 Xn의 약수이기 때문에 Xn = Xn-1 * A로 표현이 가능하다. 이때 A는 2보다 크거나 같은 양의 정수이다. 이해를 돕기 위해 이를 그림으로 표현하면 위와 같다. 개념적으로, 1개의 Xn 블록이 A개의 Xn-1 블록으로 구성된다고 생각할 수 있다.

 

이때 만약 Cn-1 ≥ A라면, Cn-1개의 Xn-1 블록들 중 A개의 Xn-1 블록들은 1개의 Xn 블록으로 대체할 수 있다. 그런데 이렇게 되면 최적해보다 적은 개수의 동전을 사용하는 해를 얻을 수 있기 때문에 가정에 모순이 발생한다.

 

그러나 만약 Cn-1 < A라면, Cn-1개의 Xn-1 블록들을 활용하여 1개의 Xn 블록을 구성하는 Xn-1 블록들의 자리를 채우면 총 (A - Cn-1)개의 Xn-1 블록들이 남게 된다. 그러면 이제 남은 (A - Cn-1)개의 Xn-1 블록들에 대해 다시 생각해보자. Xn-1 = Xn-2 * B로 표현한다면(마찬가지로 B는 2보다 크거나 같은 양의 정수), 남은 (A - Cn-1)개의 Xn-1 블록들은 B * (A - Cn-1)개의 Xn-2 블록들로 바꿔 생각할 수 있다. 그러면 이러한 B * (A - Cn-1)개의 Xn-2 블록들은 마찬가지 원리로 Cn-2개의 Xn-2 블록들로 다 채워질 수도 있고, 몇 개가 남을 수도 있다. 남게 되면 이 과정을 똑같이 반복하면 된다.

 

이 과정을 반복하면서 Xn 블록을 잘게 계속 쪼개다 보면, 언젠가 Xn 블록이 전부 채워지는 순간이 온다. Xn 블록을 가득 채운 작은 단위의 블록들의 총개수를 C라고 한다면, C개의 블록들을 1개의 Xn 블록으로 대체할 수 있는 것이다. 그런데 이렇게 되면 앞서 설명했듯이 최적해보다 적은 개수의 동전을 사용하는 해를 얻을 수 있다는 것이므로, 가정에 모순이 발생한다. 이로써 Xn를 포함하는 최적해가 반드시 존재함이 증명된다.

 

그리고 이번에도 마찬가지로 전역 최적해를 얻기 위해서는 Xn 동전 하나를 제외한 나머지 동전들에 대해서도 최적해를 얻어야 한다는 점을 이용한다. 그렇지 않으면 여기서 얻는 최적해를 이용하여 더 좋은 전역 최적해를 만들 수 있기 때문이다. 따라서 같은 과정을 반복하면, 매 순간 남은 금액보다 작거나 같은 크기의 동전들 중 가장 크기가 큰 동전을 선택함으로써 전역 최적해를 얻을 수 있음이 증명된다.