탐욕 (그리디) 알고리즘 [코딩 테스트, 코딩 면접 준비]

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

단순하지만 강력한 문제 해결 방법이다. 어떠한 문제가 있을 떄 단순 무식하게, 탐욕적으로 문제를 해결하는 알고리즘이다. 즉 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

탐욕 알고리즘 예제

[문제]

당신은 음식점의 계산을 도와주는 점원이다. 카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일때 거슬러줘야 할 동전의 최소 개수를 구하라, 단, 거슬러 줘야 할 돈은 N의 항상 10의 배수이다.

[문제 해설]

그리디 알고리즘을 이용해 해결 할 수 있는 대표적인 문제이다. 가장 큰 화폐 단위부터 돈을 거슬러 주면된다.

예를 들어 N이 1,260이라면 동전의 최소 개수는 아래와 같다.

화폐 단위	500	100	50	10
손님이 받은 개수	2	2	1	1

[예제 자바 코드]

public class Main {

    public static void main(String[] args) {
        int n = 1260;
        int cnt = 0;
        int[] coinTypes = {500, 100, 50, 10};
		
        for (int i = 0; i < 4; i++) {
            int coin = coinTypes[i];
            cnt += n / coin;
            n %= coin;
        }

        System.out.println(cnt);
    }

}

대부분의 그리디 알고리즘은 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 어떠한 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해보자.

Reference

「이것이 코딩테스트다」 - 한빛미디어 (나동빈 저)