그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

그리디 알고리즘은 다른 말로 탐욕법이라고한다. 이름에서 알수 있듯이 어떠한 문제가 있을 때 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 모든 선택지를 고려하고 그중 전체 답이 가장 좋은 것을 찾아야하는 다른 알고리즘 방법과 다르다.

 

코딩테스트에서 그리디 알고리즘 유형의 문제는 매우 다양해서 암기한다고 잘 풀 수 없다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다. 따라서 이런 기준을 정렬 알고리즘을 사용했을 떄 만족시킬 수 있으므로 정렬 알고리즘과 짝을 이뤄 출제된다.

 

위와 같은 트리가 존재할 때, 시작점에서 가장 큰 값을 구해야한다고 가정한다면 사실 3→ 100을 통해 가장 큰 값을 구할 수 있지만 그리디 알고리즘은 지금 당장 좋은것(큰 값)만 구하기 때문에 3 과 10중에 10을 선택, 7 과 8중에 8을 선택하게된다. 즉, 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠영향에 대해서는 고려하지 않는다.

대표적은 문제로는 거스름돈 문제가 있다.

예제1. 거스름돈 

Q. 내가 마트의 점원일때 카운터에는 거스름돈으로 500원,100원,50원,10원이 있다. 이때 손님에게 거슬러 줘야할 돈이 N원일때 거슬러 줘야할 동전의 최소 개수를 구하라. 단 N은 항상 10의 배수이다.

public class Greedy {
    public static void main(String[] args) {
        int n = 1260;
        int[] coins = {500, 100, 50, 10};

        int minCnt = 0;

        for (int coin : coins) {
            n %= coin;
            minCnt += n / coin;
        }
        System.out.println(minCnt);
    }
}

이 거스름돈 문제는 간단한 아이디어만 있으면 해결할 수 있는데 그것은 가장 큰 화폐단위부터 돈을 거슬러 주는 것이다.

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 선택’을 찾을 수 없을 가능성이 크다. 하지만 거스름돈과 같이 ‘가장 큰 화폐 단위’와 같이 탐욕적으로 문제에 접근 했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이다.

따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야한다. 예를들어 거스름돈 문제에서 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기때문이다.

 

만약에 500원, 400원 ,100원의 동전단위로 800원을 거슬러줘야한다면 이 경우 위의 그리디 알고리즘으로는 500 + 100+ 100+ 100원 으로 총 4개의 동전이 필요한데 사실 최적의 해는 2개의 동전 400원+ 400원을 주는 것이다. 따라서 이경우에는 위의 ‘가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수’ 가 아니므로 정당하지 않다.

이렇듯 그리디 알고리즘에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.