Greedy Algorithm

어떤 알고리즘이 각 단계마다 지역적으로 최적인 선택을 하며, 이를 통해 궁극적으로 전역 최적해를 찾기를 바란다면, 이러한 알고리즘을 탐욕적(Greedy)알고리즘 이라고 한다.

조건

그리디 알고리즘이 작동하려면 다음 두 가지의 성질이 갖춰져 있어야 한다.

  1. 최적 부분 구조를 갖추고 있어야 한다. 전체 문제의 최적해는 그 안에 부분 문제에 대한 최적해를 포함하고 있어야 한다.
  2. 탐욕적 속성을 갖추고 있어야 한다. (시간이 중요한 대회 환경에서 이를 증명하기는 힘들다.)

예제

동전 교환 문제

목표 금액 $V$센트가 주어지고 $n$가지 동전의 액면가 목록이 주어진다. 즉, 동전의 각 종류 $i\in [0... n-1]$마다 coinValue[i]가 (센트 단위로) 주어진다. $V$만큼의 금액을 표현하기 위해 필요한 동전의 최소 개수는 얼마인가? 각 종류마다 동전의 양은 무한하다고 가정한다.

예를 들어 $n = 4$, coinValue = {25, 10, 5, 1} 센트이고, $V = 42$센트를 표현하려고 한다고 해보자.

항상 1센트를 포함한다고 가정한다. 그러지 않을 경우 그리디로 최적해가 안나오는 목록이 나올 수 있으며 그 경우 DP로 해결해야한다.

여기서 그리디 알고리즘을 사용할 수 있다. 남아있는 금액이하의 액면가를 갖는 동전 중에서 액면가가 가장 큰 동전을 선태가는 것이다.

$$ 42 - 25 = 17\\ 17 - 10 = 7\\ 7 - 5 = 2\\ 2 - 1 = 1\\ 1 - 1 = 0 $$

사용한 동전은 총 5개로 최적해가 도출된다.

앞서 언급했던 그리디 알고리즘의 두 가지 구성 요건을 고려해보자.

  1. 최적 부분 구조를 갖추고 있다. 42센트를 표현하는 과정에서 $25 + 10 + 5 + 1 + 1$을 사용하였다. 이는 원래 문제에 대해 5개의 동전을 사용하는 최적해다! 부분 문제에 대한 최적해는 5개의 동전을 사용하는 해 안에 포함되어 있다. 예를 들면 다음과 같은 경우 등이 있다.