그리디 알고리즘(탐욕법, Greedy Algorithm)

WHAT IS?

각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적으로 최적의 해답에 근사한 값을 찾는 알고리즘!

위 설명에서 알 수 있듯이 그리디 알고리즘은 그 자체로 항상 최적해를 보장해 주진 못한다.
그렇기 때문에 보통 스택과 같은 자료구조나 정렬 알고리즘과 짬뽕해서 사용하곤 한다.

WHAT CONDITIONS?

그리디를 사용하기 위해서는 아래 두 조건을 만족하여야 적용할 수 있다.

1. 탐욕 선택 속성(Greedy Choice Property)
   앞의 선택이 이후의 선택에 영향을 주지 않는다.
   각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말함. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것임.

2. 최적 부분 구조(Optimal Substructure)
   문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
   전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미함.

HOW USE?

그리디 알고리즘은 아래 3단계를 걸쳐 적용될 수 있다.

1. 선택 절차(Selection Procedure)

   ‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다.
   

2. 적절성 검사(Feasibility Check)

   선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다.
   

3. 해답 검사(Solution Check)

   모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다.
   

그리디 알고리즘의 대표적인 문제로 거스름돈 문제가 있습니다.

❓500원, 100원, 50원, 10원의 동전이 있을 때, 주어진 금액을 최소 개수의 동전으로 거슬러주려면 어떻게 해야 할까요?

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.

2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다.

3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다.

public int GreedyAlgorithm(int k) {
    int[] arr = new int[]{500, 100, 50, 10, 5, 1};
    int answer = 0;
    for (int n : arr) {
      if (k > 0) {
        int temp = k / n;
        answer += temp;
        k -= (n * temp);
      }else break;
    }
    return answer;
}

DP와의 비교

핵심부터 말하자면

DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태이다.

-end-