Greedy Alogorithm

2 분 소요

Greedy는 ‘탐욕스러운, 욕심 많은’이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
탐욕스런 선택 조건이란

앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다.
최적부분 구조 조건이란

문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.
이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.
하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다.
이 구조를 매트로이드라고 한다.

나는 오늘도 편의점에서 아르바이트하고 있다.
손님이 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다.
손님은 계산하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.

선택 절차
- 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
적절성 검사
- 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
- 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
해답 검사
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
- 액수가 부족하면 1번 과정부터 다시 반복한다.

가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.

이 문제 구조는 매트로이드다. 탐욕 알고리즘을 사용해도 언제나 최적해를 찾아 낼 수 있다.

나는 아르바이트를 하러 간 사이에, 나의 집에 도둑이 들었다.
도둑의 가방은 35KG까지의 물건만 담을 수 있고, 나의 집에는 4개의 물건이 있다.

도둑의 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 가방에 담을 수 있다.
남는 공간이 5kg밖에 남지 않아 더 훔칠 수 있는 물건이 없다. 그리고 이때 훔친 물건의 총 가치는 그림 하나의 가치와 그림 하나의 가치와 같은 $3,000이다.
만약 그림 대신 컴퓨터와 반지를 가방에 담았다면 어떨까?
35kg이 넘지 않으면서 총 가치는 $3,500으로 그림 하나만 훔칠 때보다 더 많은 가치의 물건을 훔칠 수 있다. (즉, 탐욕 알고리즘으로 최적해를 구하진 못한다.)

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도답하는 문제 해결 방식이다.

그러나 도둑의 예와 같이 항상 최적의 결과를 보장하지는 못 한다는 점을 명시해야 한다.

따라서 두가지의 조건을 만족하는 “특정한 상황”이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.

Ref.