Tutorial : 그리디 증명 방법 timer 1s memory 512MB

탐욕(Greedy) 알고리즘 증명

문제의 풀이로 그리디 알고리즘을 생각했다면, 이 풀이가 맞는지 어느 정도 증명이 필요하다.

만약 증명 없이 풀이를 짜서 낸다면, 틀리더라도 왜 틀렸는지 알아채기 힘들다.

그리디 문제를 증명하는 방법 중에서는 귀류법, 수학적 귀납법, 순서 교환 방법을 자주 사용한다.

귀류법

그리디 방법을 쓰지 않는 해가 정답이라면(또는 그리디 방법이 정답이 아니라면) 모순이 발생한다는 것을 증명하는 방법론이다.

예시 - 회의실 배정

시작시간과 종료시간이 정해진 N개의 회의가 주어진다. 시간이 겹치지 않게 최대한 많은 회의를 선택하여라.

다음과 같은 풀이를 생각할 수 있다.

매 순간마다, 종료시간이 가장 빠른 회의를 선택한 다음, 선택한 회의와 겹치는 다른 회의들을 제외한다.

남는 회의가 없을 때까지 반복한다.

증명

[반대 가정] 만약 종료시간이 가장 빠른 회의 A가 정답에 포함될 수 없다고 가정해보자.

정답에서 선택한 회의 중 종료시간이 가장 빠른 회의를 제외한 다음, A를 추가해보자. 가장 빠른 회의의 종료시간이 더 빨라졌으니, 당연히 다른 회의와는 겹치지 않는다.

따라서, A를 포함하는 정답을 새로 만들 수 있다.

처음에 회의 A를 포함하는 정답이 없다고 가정했으니, 모순이 발생한다.

따라서, A는 반드시 정답에 넣는다고 생각해도 문제 없다.

A를 정답 후보에 넣었으니, A 및 A와 겹치는 회의를 모두 제거한 다음 동일한 방법을 사용하면 된다.

이렇게 그리디를 사용하지 않는 정답을 가정한 다음, 더 좋은 정답을 만들어서 모순을 보이면 된다!

수학적 귀납법

수학적 귀납법이란, 작은 부분 문제에서 그리디 알고리즘이 돌아간다면, 큰 부분 문제에서 작은 부분 문제의 증명을 이용해서 그리디 알고리즘이 돌아간다는 것을 증명하는 방법론이다.

예시 - 무게 재기

한쪽에만 추를 올려놓을 수 있는 양팔저울 하나와 1, 2, 4, 16 그램의 추가 매우 많이 주어진다.

N 그램의 물체를 측정하는 데 필요한 최소 추의 개수는 몇개일까?

다음과 같은 풀이를 생각할 수 있다.

매 순간마다, 남은 무게보다 더 작거나 같은 가장 무거운 추를 추가한다.

남은 무게가 0이 될 때까지 반복한다.

증명 - 정답에 포함된 가장 무거운 추가 '남은 무게보다 더 작거나 같은 가장 무거운 추'라는 것을 증명

[작은 부분 문제] N < 20 (=4 + 16)일 때는 직접 최소 추의 개수를 계산하여 증명한다.

[큰 부분 문제] 1 ≤ N ≤ K일 때 전부 증명했다고 생각하고, N = K+1 ≥ 20일 때를 증명하자.

무게 N을 재는 정답에 포함된 가장 무거운 추의 무게를 생각해보자.

가장 무거운 추의 무게 X가 16이 아니라면, X는 4 이하이다.

N-X ≥ 16이므로, 수학적 귀납법에 의해 무게 N-X를 재려면 16그램짜리 추를 넣어야 한다.

이는 처음 가정한 '가장 무거운 추의 무게가 16이 아님'과 모순이다.

수학적 귀납법의 증명 방식은 동적계획법의 작동 원리와 비슷하니, 동적계획법에 익숙해진다면 수학적 귀납법으로 증명하는 그리디 문제도 문제없이 풀 수 있다.

순서 교환(Exchange Argument) 방법

N개의 일을 하는 순서를 정해야 하는 문제들을 풀 때 아래와 같은 발상을 하면 도움이 되는 경우가 많다.

• 질문) 일 1, 일 2, ..., 일 a, ..., 일 b, ..., 일 N을 순서대로 하는 게 가장 최적이려면 어때야 할까?

• 아이디어) 일 1, 일 2, ..., 일 b, ..., 일 a, ..., 일 N을 하는 것보다는 항상 좋아야 한다!

아이디어를 바탕으로 조건을 계산한다면, 그 조건을 바탕으로 우선순위가 높은 일과 낮은 일이 생긴다.

(Tip : 계산이 복잡하다면 우선 인접한 두 일을 바꿔서 답을 구해보자.)

계산한 우선순위 선정 기준에 따라 일들을 정렬한 다음 문제를 해결하면 된다!

예시 - 재배열 부등식

길이 N짜리 수열 A, B가 주어진다. A, B의 원소 순서를 적절히 바꿔서 A_1 \times B_1 + \cdots + A_N \times B_N의 값을 최대화해라.

풀이 및 증명

우선 수열 A를 오름차순으로 정렬하자. 그러면 i < j이면 A_i \le A_j이다.

정답이 B_1, B_2, ..., B_N이라고 하자. 위에서 언급한 아이디어를 바탕으로 B_i와 B_j의 값을 바꾸면 계산값이 달라질 것이다.

• 바꾸기 전 : V_1 = A_1 \times B_1 + \cdots + A_i \times B_i + \cdots + A_j \times B_j + \cdots + A_N \times B_N

• 바꾼 이후 : V_2 = A_1 \times B_1 + \cdots + A_i \times B_j + \cdots + A_j \times B_i + \cdots + A_N \times B_N

처음 구한 정답이 최적이려면 V_1 \geq V_2를 만족해야 한다.

즉, V_1 - V_2의 값이 0 이상이어야 하는데, V_1 - V_2 를 계산하면 A_i \times B_i + A_j \times B_j - A_i \times B_j - A_j \times B_i = (A_i - A_j)(B_i - B_j) 이다.

따라서, A_i < A_j라면 반드시 B_i \leq B_j를 만족해야 한다.

만약 A_i = A_j라면 B_i와 B_j의 크기 관계가 크게 중요하지 않지만, B_i \le B_j를 만족해야 한다고 해도 무방하다.

수식 계산을 통해 작은 값이 앞에 와야 한다는 사실을 확인했으니, 수열 B까지 오름차순으로 정렬한 다음 정답을 구하면 된다.

앞서 언급한 재배열 부등식 문제를 해결하는 프로그램을 작성해보자!