그리디 알고리즘
그리디 알고리즘은, 알고리즘의 각 단계에서 가장 최선의 선택을 하는 기법입니다.
최소 동전 갯수 문제가 가장 대표적인 그리디 알고리즘의 예시 중 하나입니다.
동전 단위가 5, 10, 50원 짜리만 있고, 870원을 최소의 동전 갯수로 표현하려고 하는 문제가 있습니다.
동전의 갯수가 적으려면, 큰 단위의 동전을 써야 할 것입니다.
따라서 단계별로 가장 최선의 선택, 즉, 제일 먼저 가장 단위가 큰 동전을 고릅니다. -> 50원 짜리
50원짜리를 계속 고르다가 18개를 고르게 되면, 870원을 초과합니다.
이 때는 50원보다 한 단계 단위가 작은 10원짜리를 고르고 다시 진행합니다.
이런 식으로 진행하면, 50원짜리 17개, 10원짜리 2개 를 고르면 가장 최소의 동전 갯수를 이룸을 알 수 있습니다.
즉, 구현을 할 때에는 전체 870원에 대해서 단계별로 50원씩 차감하다가(820,770,720,…),
값이 0이 되지 않게 딱 떨어지지 않는 단계에서는 취소하고 한 단계 단위가 작은 것을 골라 다시 진행합니다.
Baby-gin 게임을 그리디 알고리즘으로 풀기
그렇다면 Baby-gin 게임을 그리디 알고리즘으로 풀 수 있을까요? (Baby GIn 게임(클릭))
먼저, 입력받은 숫자 각각의 갯수를 매기는 int형 10칸 배열 COUNT를 선언합니다. (초기값 0)
444345 라는 숫자를 입력받았을 경우, COUNT[3] = 1, COUNT[4] = 4, COUNT[5] =1 이 들어갑니다.
이후, run(연속된 숫자)을 조사합니다.
COUNT 배열의 3개의 연속된 인덱스에 값이 1 이상 들어가 있다면 run일 것입니다.
run 조사가 끝났다면, 조사한 데이터는 COUNT 배열에서 삭제(차감)합니다.
그러면 COUNT[3] = 0, COUNT[4] = 3, COUNT[5] = 0이 될 것입니다.
여기에서 triplete(동일한 숫자 3개)를 조사합니다.
COUNT 배열의 값 중 3인 곳이 있다면 triplete**일 것입니다.
이렇게 run 혹은 triplete를 조사하여 2번이 나오면 해당 숫자는 Baby-gin 일 것입니다.
(조사 과정에서 run 혹은 triplete 둘 중 어느 것을 먼저 하는지는 상관이 없습니다.)
하지만 그리디 알고리즘은 항상 최적의 해를 찾아주는 것은 아닙니다.