[알고리즘] Greedy Algorithm(탐욕 알고리즘)

탐욕 알고리즘이란?

Greedy Algorithm: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법

동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 

각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘인 것이다.

탐욕 알고리즘은 일정 공식없이 창의력을 요구하는 문제 유형이다. 때문에 문제를 풀기위한 최소한의 아이디어를 떠올려야 할 것이다.

 

물론 모든 경우에서 그리디 알고리즘이 통하는 것은 아니다. 예를 들어 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로우를 1개밖에 받지 못한다. 지금 당장의 선택은 마시멜로우 1개를 받는 것이지만, 결과적으로는 1분 기다렸다가 2개를 받는 게 최선이기 때문이다.

 

 

탐욕 알고리즘으로 문제를 해결하는 방법

다음과 같이 단계적으로 구분할 수 있다.

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

탐욕 알고리즘을 보장하는 조건

탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

탐욕 알고리즘이 사용되는 예시

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리(Minimum spanning tree) 
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘
• 허프만 코드
• UNION&FIND 알고리즘

 

---

탐욕 알고리즘의 대표적 문제

예제 1) 거스름돈

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

거스름돈 960원을 채우기 위해서 먼저, 500원 짜리 동전을 선택한다. 그다음 100원짜리 동전을 4개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택한다. 이렇게 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 구분할 수 있다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다.

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 최적의 해를 보장한다 말할 수 있다. 만약 800원을 거슬려야할 때, 500원, 400원, 100원 이라면? 탐욕 알고리즘 사용시 500원 1개 100원 3개, 최적의 해 400원 2개. 큰 단위가 작은 단위의 백수가 아니라면 탐욕 알고리즘을 사용할 수 없다.

이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야한다.

public int GreedyAlgorithm(int k) {
    // TODO:
    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;
}

 

예제2) 회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

입력)

5
1 4
2 3
3 5
4 6
5 7

출력)

3

회의시간 끝나는 기준으로 Sort해준다. 끝나는 기준으로 Sort하는 이유는 그 시간에 맞게 각 회의를 배정하기 위함이다. 시작하는 시간을 기준으로 둔다면 회의가 언제 끝날지 모르므로 최적의 해를 구할 수 없다. 끝나는 시간과 그 다음 회의시간의 시작시간을 비교하여 시작시간이 같거나 크다면 다음 회의로 배정할 수 있는 최적의 해이기 때문에 해당 회의를 배정해준다. (만약 끝나는 시간이 같으면, 시작 시간으로 다시 sort해줘야 함)

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

class Meeting implements Comparable<Meeting>{
    int start;
    int end;
    Meeting(int s, int e){
        this.start = s;
        this.end = e;
    }

    @Override
    public int compareTo(Meeting o) {
        if(this.end == o.end) return this.start - o.start;
        else                  return this.end - o.end;
    }
}

public class Main {
    static ArrayList<Meeting> arr= new ArrayList<>();

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        for(int i = 0; i < n; i ++){
            arr.add(new Meeting(in.nextInt(), in.nextInt()));
        }
        System.out.println(solution());
    }

    public static int solution(){
        int answer = 0;
        Collections.sort(arr);
        int nEnd = arr.get(0).start;
        for(Meeting m : arr){
            if(m.start >= nEnd){
                nEnd = m.end;
                answer++;
            }
        }
        return answer;
    }
}

 

다음으론 그리디 알고리즘 기법을 사용한 다익스트라 알고리즘, Union&Find, 최소 스패닝 트리(크루스칼, 프림)에 대해서 블로깅을 할 예정이다.