[Algorithm | Java] Greedy Algorithm(그리디 알고리즘)

이번 시간에는 그리디 알고리즘에 대해서 배워 볼 것입니다.

 

1. 그리디(탐욕) 알고리즘이란?

단어에서 알 수 있듯이 'Greedy'라는 단어가 '탐욕스러운', '욕심 많은' 이라는 뜻을 내포하고 있습니다.

 

그래서 말 그래도 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종 답에 도달하는 알고리즘입니다.

최적해를 구하는 데 사용되는 근사적인 방법이며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각이 드는 것을 선택해 나가는 방식입니다다.

• 매 선택에서 현재 당장 최적인 값이다.

 

그렇지만 그리디 알고리즘은 전체에서 최적값을 언제나 구할 수는 없습니다.

 

다음과 같은 그래프를 봅시다.

A에서 출발하여 E에 가야한다고 할 때 경우의 수는 다음과 같습니다.

1. 먼저 B or C or D 중에서 가야할 길을 찾는다.
   • 가장 걸리는 시간이 짧은 C경로로 간다.
2. 그리디 알고리즘은 이 최적의 선택으로 끝까지 쭉 진행하기 때문에 다른 경로는 고려하지 않습니다.
3. 그 후 바로 E에 도착하여 총 41시간이 소모 되었습니다.
   • 하지만 A-C-E로 갈 때 보다 A-B-E로 갈 때 뒷부분에서 소모 되는 시간이 더 적어 전체적인 시간 소모는 더 적은데,
   • 최초의 선택에서 최적의 선택은 했지만 전체 문제를 봤을 때 최적의 값은 구하지 못하게 된 것입니다.

이와 같이 그리디 알고리즘의 단점이 존재할 수 있는데 그럼에도 불구하고 그리디 알고리즘은 속도가 매우 빨라 간단한 문제에서 그 힘을 발휘할 수 있다.

(그냥 현재 상황에서 최선을 다한다! -> 현재 상황만 고려하면 됨. -> 빠름!)

 

 

하지만 항상 최적해가 되지 않는다는 제약에 의해 아래와 같은 특수한 조건이 만족되는 경우에만 그리디 알고리즘의 최적해를 구하는 데 사용하기로 합시다.

 

2가지 조건

1. 탐욕 선택 속성(Greedy Choice Property)
   • 이전의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure)
   • 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성 된다.
   • 즉, 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 하는 것이다.

 

이러한 조건이 성립하지 않는 경우 그리디 알고리즘의 최적해는 구할 수 없고 만약 이 조건을 만족한다면 어떤 특별한 구조가 있는 문제에 대해서 이 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있는데 이 구조를 매트로이드라 합니다.

• 매트로이드 - 조합론에서 일차 독립의 성질을 공리화하여 얻은 조합론적 구조

 

위의 2번 조건은 뒤에서 배울 Dynamic Programming의 2번 조건과 동일한 조건인데 이에 대해 간단히 설명하자면 다음과 같습니다.

• DP의 경우, 문제가 Overlapping되기 때문에 다음에 풀 문제가 이전의 작은 문제의 결과에 영향을 받게 됩니다. 즉, 다시 말해, 동일한 형식의 문제만 점점 커지는 것일 뿐, 이전의 경우에 영향을 받는다는 것입니다.
• 하지만 그리디 알고리즘은 이와 달리 영향을 받아서는 안 됩니다. 왜냐하면 그래야지 다른 경우의 결과와는 상관없는 최적해를 구할 수 있기 때문입니다.

 

정리

따라서 그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적의 근사한 값을 빠르게 도출해낼 수 있다는 장점이 있다. 이 장점으로 인해 그리디 알고리즘은 근사 알고리즘으로 사용할 수 있다.

그리디 알고리즘을 적용해도 언제나 최적의 해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다.

 

 

2. 그리디 알고리즘의 예시

Action Selection 문제

그리디 알고리즘의 가장 대표적인 예시 중 하나인 활동 선택(Action Selection) 문제에 대해 살펴보겠습니다.

활동 선택 문제는 "N개의 활동에 대해 각 활동에는 시작 시간 및 종료 시간이 있을 때, 한 사람이 최대한 많이 할 수 있는 활동(Acticity)의 수를 구하는 문제"입니다.

 

즉, 쉽게 말해서 각각의 활동(Activity)에는 시간이 소모되므로 하나를 선택했다면 그 동안에는 해당 시간에 다른 활동을 할 수 없습니다. 이 때 가장 많은 활동에 참여하기 위한 방법을 찾아내는 것입니다.

 

아래 표를 보면서 이해해 봅시다.

위에서 설명한 각 활동과 그것들의 시작/ 종료 시간이 설정 되어 있음을 알 수 있습니다. 이 문제는 이때 최대한 많은 활동을 해야 하므로 언제 시작하든지 간에 전체에서 가장 종료 시간이 빠른 것부터 선택해야 합니다.

 

어차피 시작 시간은 항상 종료 시간 이전일 것이기 때문에 고려하지 않아도 됩니다.

그래서 종료 시간을 기준으로 먼저 정렬한 뒤, 제일 먼저 끝나는 활동을 무조건 선택하고 끝났을 때, 바로 다음에 선택할 수 있는 활동을 찾아 수행하는 방식을 반복하여 해결할 수 있습니다.

 

1. 먼저 종료 시간 기준으로 정렬 후 제일 먼저 끝나는 D 활동을 선택한다.
2. D 활동이 종료하면 바로 다음 활동 가능한 C 활동을 선택한다.
3. C 활동 종료 후 B 활동을 시작 할 수 없으므로 건너 뛰고 활동이 가능한 시간인 A 활동을 선택한다.
4. A 활동도 종료하면 그 다음으로 활동 가능한 F를 선택하여 마무리 된다.

 

3. 코드로 구현

import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[] args){
        // 활동 정보를 List에 저장하고 정렬한다.
        ArrayList<Action> list = new ArrayList<>();
        list.add(new Action("A", 7, 8));
        list.add(new Action("B", 5, 7));
        list.add(new Action("C", 3, 6));
        list.add(new Action("D", 1, 2));
        list.add(new Action("E", 6, 9));
        list.add(new Action("F", 10, 11));
        Collections.sort(list);

        // Greedy 알고리즘 수행 후, 결과 출력
        ArrayList<Action> ans = greedy(list);
        for(Action act : ans){
            System.out.print(act.name + ", ");
        }
    }

    // Greedy 알고리즘을 통해 선택된 활동들을 반환한다.
    private static ArrayList<Action> greedy(ArrayList<Action> list){
        int time = 0;
        ArrayList<Action> ans = new ArrayList<>();

        for(Action act : list){
            if(time <= act.startTime){
                time = act.endTime;
                ans.add(act);
            }
        }
        return ans;
    }
}

// 활동 정보를 가진 Class로 Comparable을 구현하여 종료 시간 기준 오름차순으로 정렬함.
class Action implements Comparable<Action>{
    String name;
    int startTime;
    int endTime;
    public Action(String name, int startTime, int endTime){
        this.name = name;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Action a) {
        return this.endTime - a.endTime;
    }

    @Override
    public String toString() {
        return this.name;
    }
}

 

결과

D, C, A, F,

 

4. 예시 2 - 거스름돈 문제

이번엔 그리디 알고리즘의 유명한 예시인 거스름돈 문제에 대해서 보도록 합시다.

 

이번엔 돈을 낸 뒤, 거스름돈을 최소 개수의 동전 지폐의 조합으로 주는 경우, 그 개수를 구하는 문제입니다.

 

예를 들어,

• 누군가 2,730원 어치의 물건을 사고 5,000원을 냈다고 가정하면 거스름돈은 총 2,270원 일 것입니다.
• 이때, 지폐와 동전 종류가 아래와 같을 때, 최소의 개수로 거스름돈을 주는 경우는 어떤 경우일까요?
  • 지폐 및 동전의 종류: 1,000원, 500원, 100원, 50원, 10원
  • 정답: 1,000원 2개 / 100원 2개 / 50원 1개 / 10원 2개
  • 총 7개

이는 MSD(Most Significant Digit)으로 풀어낸 것으로 가장 중요한 단위를 먼저 계산하는 것을 의미합니다. 위의 경우에서 자신보다 더 큰 지폐 혹은 동전으로 거스름 돈을 준다면 나머지는 무조건 더 적은 개수로 반환하는 것이 가능하기 때문에 이를 사용할 수 있습니다.

 

따라서, 이전의 선택과 관련없이 현재 상태에서 최선의 결과를 선택하여 전체에서 최적의 결과를 낼 수 있게 됩니다.

 

그러나,

만약 거스름돈이 120원을 줘야하는 상황에서 거스름돈으로 줄 수 있는 동전의 종류가 다음과 같다면 어떨까요?

• 동전의 종류: 50원, 40원, 10원

 

이를 MSD 원리로 풀게 되면 50원 2개 / 10원 2개로 총 4개가 나오게 됩니다.

 

그런데 사실 이 문제는 40원짜리 3개를 거슬러 주면 더 적은 개수로 거스름돈을 줄 수 있습니다.

 

이러한 문제가 발생한 이유는 40원은 자신보다 큰 동전(50원)의 약수가 아니기 때문에 50원은 40원을 대체해 더 적은 숫자로 반환하는 경우라고 보장할 수 없게 됩니다.

 

이처럼, 그리디 알고리즘으로 해결할 수 있으려면 조건을 충분히 만족하는 지를 검증할 수 있어야 한다.

 

관련된 문제

• 백준 5585번 거스름돈
• 백준 11047번 동전
• 백준 11000번 강의실 배정