Activity Selection Problem의 증명

[obzva]

들어가며

#279 문제는 잘 생각해보면 Activity Selection Problem이라는 Greedy 문제의 한 유형으로 볼 수 있습니다.

Activity Selection Problem이 무엇인지에 대해선 아래 두 링크를 참고해주세요.

• 위키피디아
• 이 유형에 속하는 유명한 백준 문제

예전에 위 백준 문제의 솔루션을 찾아보던 중에, 이렇게 하면 됩니다에 대한 글은 많은데 이렇게 하면 왜 되는지에 대한 글이 적은 것 같아서 제가 위키피디아를 참고하여 증명을 한국어로 정리해두었습니다.

저처럼 이 Greedy 알고리즘이 왜 잘 작동하는지에 대해 궁금하신 분들께 일독 추천 드립니다! :)

이 글에서는 해당 문제의 Greedy 접근법에 대한 정당성을 수학적으로 증명합니다. 증명은 다음 두 부분으로 구성됩니다:

1. Greedy한 선택이 현재의 문제에서 최적인지
2. 하위 문제(Subproblem)에 대해서도 정당한지

1. Greedy 선택의 최적성 증명

회의가 끝나는 시간의 오름차순으로 정렬된 회의 $a_i$ 들의 집합 $S$가 있습니다.

$S = {a_1, a_2, a_3, ... , a_n}$

이때, $A \subseteq S$인 최적의 해 $A$가 아래의 조건과 함께 존재한다고 가정합시다:

• $A$ 역시 회의가 끝나는 시간의 오름차순으로 정렬된 회의들의 집합
• $A$의 첫 번째 원소 $a_k (\in S)$는 $a_1$이 아님

$a_1$, $a_k$ 모두 $S$의 원소이며 $S$는 끝나는 시간의 오름차순으로 정렬되어 있으므로:

$finish\ time\ of\ a_1 \leq finish\ time\ of\ a_k$

이제 새로운 집합 $B$를 다음과 같이 정의합니다:

$B = (A \setminus {a_k}) \cup {a_1}$

앞서 언급한 $a_1$과 $a_k$의 관계 때문에 $A$에서 $a_k$ 자리에 $a_1$을 대신 집어넣은 $B$라는 집합을 만들 수 있습니다.

$|A| = |B|$

이때, $A$와 $B$의 크기는 같기 때문에 $B$ 또한 $A$와 마찬가지로 최적의 해가 됩니다.

따라서 끝나는 시간이 가장 빠른 가능한 회의를 고르는 것이 최적의 선택이라는 사실을 알 수 있습니다.

2. 하위 문제의 최적성 증명

이제 $S$의 부분집합인 $S'$에 대한 하위 문제를 살펴봅시다.

$S' = {a_i \in S : starting\ time\ of\ a_i \geq finish\ time\ of\ a_1}$

즉, $S'$는 $a_1$의 끝나는 시간보다 시작 시간이 더 늦은 회의 $a_i$로 이루어진 집합입니다.

$A$를 Greedy한 방식을 통해 얻은 $S$에 대한 최적해라고 할 때, $A'$을 다음과 같이 정의합니다:

$A' = A \setminus {a_1}$ ... (1)

이때, $A'$이 $S'$에 대한 최적해임을 증명하겠습니다. ... (2)

귀류법을 통한 증명

만약 $A'$이 $S'$에 대한 최적해가 아니라면 (2의 부정):

$there\ exists\ B'\ such\ that\ |B'| > |A'|$

$S'$에 대한 최적해 $B'$가 존재할 것이고 $B'$의 크기는 $A'$보다 클 것입니다.

이 때,

$B' \cup {a_1}$ would be optimal for $S$

$|B' \cup {a_1}| > |A| = |A' \cup {a_1}|$

$B'$이 $S'$에 대한 최적해이므로, $B'$에 $a_1$을 추가한 집합은 $S$에 대한 최적해가 됩니다.

$B'$의 크기는 $A'$의 크기보다 크기 때문에 $B'$에 $a_1$을 추가한 집합은 $A$보다 크기가 큰데, $A$는 $S$에 대한 최적해이므로 이는 (1)에 대한 모순입니다.

따라서 $A'$는 $S'$에 대한 최적해가 맞습니다.