Greedy Algorithm
한국말로는 탐욕 알고리즘이라고도 하고, 욕심쟁이 알고리즘이라고도 한다.
Greedy 알고리즘이란 문제를 풀기 위해 선택을 내려야 할 매 순간마다 '최고'의 선택을 내리는 알고리즘이다.
다음 문제를 보자.
서로 다른 수 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과 최적 해가 동일함을 증명할 때 자주 사용되는 증명 방법이다.
Reference)
http://sehoon95.blog.me/220115473322
댓글 없음:
댓글 쓰기