[Algorithm] 그리디 알고리즘(Greedy Algorithm)이란?

이 글은 '이것이 코딩테스트다'를 요약하여 그리디 알고리즘에 대하여 설명합니다.

 

학습 목표

· 그리디 알고리즘이란?

· 예시 - 거스름돈 문제

· 그리디 알고리즘의 정당성

---

 

그리디 알고리즘이란?

· 탐욕적으로 문제를 푸는 알고리즘

   - 탐욕적이라는 말은 ‘매 순간 가장 좋아 보이는 것만 선택하고 나중에 미칠 영향은 고려하지 않는’ 방식을 의미한다.

 

· 코딩 테스트에서 만나게 될 그리디 알고리즘 문제 유형의 특징:

   - 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다.

   - 문제 유형이 매우 다양하여 암기한다고 항상 잘 풀 수 있는 알고리즘 유형이 아니다.

      때문에 많은 유형을 접해보고 문제를 풀어보며 훈련 해야 한다. 

    - 일반적으로 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

      즉, 특정 문제에서 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다.

    - 다익스트라 알고리즘처럼 그리디 알고리즘이면서 암기가 필요한 알고리즘도 일부 존재한다.

    - 여러 개의 데이터를 빠르게 정렬해야 하는 문제를 위해 정렬 라이브러리의 사용 방법 숙지해야한다.

    - 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시한다.

       대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 자주 정렬 알고리즘과 짝을 이뤄 출제한다.

 

▶ 예시 - 거스름돈 문제

 

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

 

풀이

 

그리디 알고리즘의 대표적인 유형인 거스름돈 문제다.

이 문제는 ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 아이디어로 풀 수 있다.

N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.

이후 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

 

N = 1,260 이라고 가정하자.

 

1.  500원짜리로 거슬러 줄 수 있는 돈은 1,000원, 즉 500원 2개이고 남은 돈은 260원이다.

2. 100원짜리로 거슬러 줄 수 있는 돈은 200원, 즉 100원 2개이고 남은 돈은 60원이다.

3. 50원짜리로 거슬러 줄 수 있는 돈은 50원, 즉 50원 1개이고 남은 돈은 10원이다.

4. 10원짜리로 거슬러 줄 수 있는 돈은 10원, 즉 10원 1개이고 거스름돈 계산을 모두 마쳤다.

 

따라서 N = 1,260 일때 손님이 받은 동전의 최소 개수는 6개이다.

 

public class 거스름돈문제 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt(); // 거슬러 줘야할 돈

        int num = 0; // 필요한 동전 개수
        while (num != 0){
            if(money%500 == 0){
                money = money/500;
                num ++;
            }else if(money%100 == 0){
                money = money/100;
                num ++;
            }else if(money%50 == 0){
                money = money/50;
                num ++;
            }else if(money%10 == 0){
                money = money/10;
                num ++;
            }
        }

        System.out.println("필요한 동전의 개수: " + num);
    }
}

 

그리디 알고리즘의 정당성

 

· 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

  - ex) 거스름돈 문제에서 가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것

  - 하지만 대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해 찾을 수 없다.

      

· 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정단한지 검토해야한다.

   - 거스름돈 문제는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로

      작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.  때문에 그리디 알고리즘으로 해결할 수 있었다. 

    - 반대로 800원을 거슬러 줘야 하는데 화폐 단위가 500원, 400원, 100원인 경우 그리디는

      500원 + 100원 + 100원 + 100원 4개의 동전을 거슬러 줘야 한다고 나온다.

       하지만 최적해는 400원 + 400원 2개의 동전을 거슬러 주는 것이다.

       즉, 화폐 단위가 서로 배수 형태가 아니라면 그리디 알고리즘을 사용할 수 없다. 이때는 다이나믹 프로그래밍으로 해결할 수 있다.

 

·  코딩테스트에서 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 탐욕적인 해결법이 존재하는지 고민하자.

그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이나믹 프로그래밍(DP)이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민하자.

 

(+)추가적인 그리디 알고리즘 문제풀이

scshim.tistory.com/225

scshim.tistory.com/226

scshim.tistory.com/227