(알고리즘) 그리디 알고리즘

*그리디 알고리즘 성립조건

예를들어, 여러개의 동전의 금액이 주어질 때, 다음 동전이 항상 이전 동전의 배수로 이루어질 때 Greedy알고리즘이 성립한다.


증명방법)
https://www.acmicpc.net/problem/1931

이 문제에서 그리디 알고리즘에 의해 발생하는 답과 똑같은 답이 존재하는데 이를 최적해라고 한다.
이를 증명할 수 있는 방법은 그리디알고리즘으로 이루어진 답의 일부분을 최적해 답의 일부분으로 바꾸는 것이다.


그 이유는
탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

다음 문제를 보자. 

서로 다른 수 n개 a1, a2, a3, ..., an가 주어졌다. 이 중 k개(물론 k는 n보다 작거나 같은 수이다)의 숫자를 뽑아 이들의 합을 가장 크게 만들어주려면 어떻게 해야할까?

답은 간단하다. 바로 '가장 큰 숫자 k개를 뽑는 것'이다. 즉, '숫자를 뽑는 선택'을 내리는 매 순간마다 남아있는 숫자 중 '가장 큰' 숫자를 뽑는 것, 이것이 바로 Greedy Algorithm의 한 예라고 볼 수 있겠다. 

그러면 Greedy Algorithm으로 얻은 답은 항상 옳을까? 이는 증명해 보아야 할 문제이다. 어떤 문제를 풀던 간에 Greedy Algorithm으로 접근하여 답을 얻었다면 이 답이 옳은지를 증명하여야한다.  

위의 문제 역시 자명해 보이지만, 엄밀하게는 증명이 필요하며 증명은 다음과 같다.

증명

​

Greedy Algorithm으로 얻은 k개의 숫자의 집합을 G={g_1, g_2, ..., g_k} (g_1>g_2>...>g_k),

그리고 최적해의 집합을 O={o_1, o2_, ..., o_k} (o_1>o_2>...>o_k}라고 하자.

그리고, O와 G가 다르다고 가정하자. (귀류법)

​

그렇다면, o_m와 g_m의 값이 달라지는 최소의 자연수 m이 존재한다.

이때, g_m는 Greedy Agorithm에 의해 선택된 m번쨰로 큰 숫자이기 때문에 g_m는 o_m보다 크게 된다.​

​

새로운 집합 S를 다음과 같이 정의하자.

​S = {o_1, ..., o_(m-1), g_m, o_(m+1), ..., o_k}

이때 S의 원소의 합은 O의 원소의​ 합보다 크게 되며, O가 최적해의 집함임에 모순된다.

​

이와 같은 방법으로 증명하는 방법을 "​Exchange Argument" 라고 부르며, Greedy Algorithm과 최적 해가 동일함을 증명할 때 자주 사용되는 증명 방법이다.