탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin

탐욕 알고리즘(Greedy Algorithm)이란 ?

- 최적해를 구하는데 사용되는 방법

- 여러 경우 중 하나를 선택해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하며 각 선택의 시점에서 이루어지는 결정은    지역적으로는 최적이지만 그것들을 계속 진행하였을 때 나온 해답이 최적이라는 보장은 없음.

예를 들어, 거스름 돈 830원을 받아야 하는데 동전의 개수를 가장 적게 받고 싶다면 당연히 500원 짜리로 받을 수 있는 만큼 많이 받고, 그 다음 100원으로 받을 수 있는 만큼 받아야 동전의 개수가 가장 적어질 것이라 생각할 것이다. 이 문제의 경우 실제로 그렇겠지만 말이다.

또는 이전의 완전 검색(Exhaustive Search) 방식에서 보았던 Baby-gin 문제를 Greedy Algorithm 방식으로 문제에 접근한다고 가정해보자.

" Baby-gin은 어차피 앞의 숫자 3개, 뒤의 숫자 3개만 검사하니까 숫자를 정렬한 후 앞,뒤 숫자3개만 run 또는 triple인지 비교하도록 해보자" 

이렇게 접근했을 때 과연 최적의 해답을 구할 수 있을까? "{ 6, 4, 4, 5, 4, 4 }" 라는 숫자를 정렬하면 "{ 4, 4, 4, 4, 5, 6 }" 로 Baby-gin에 해당된다. 그러나

" { 1, 2, 3, 1, 2, 3} 은 이대로 두면 Baby-gin에 해당되지만 정렬하면 { 1, 1, 2, 2, 3, 3} 으로 Baby-gin에 해당하지 않는다.

즉, Greedy Algorithm 방식의 접근은 최적의 해 또는 해답을 보장하지 않는다는 것이다. 

Baby-gin 문제를 또 다른 Greedy Algorithm 방식으로 구현해보자. 

" 숫자 6개의 개수를 표현하는 배열(numbers)에 담아서 run 또는 triple에 해당되면 확인 후 숫자의 개수를 감소시키자. "는 방향으로 접근하여 구현하였다.