[알고리즘] 탐욕(그리디) 알고리즘

탐욕 알고리즘(greedy algorithm)

그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위해 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념입니다.

 

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불립니다. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘입니다.

 

물론 모든 경우에서 그리디 알고리즘이 통하지는 않습니다.(그리디 알고리즘은 단순히 지금 최선의 선택이 전체적으로도 최선의 선택이길 바랄 뿐이기 때문입니다)

 

쉬운 예를 들자면 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로를 1개밖에 받지 못합니다. 지금 당장 최선의 선택은 마시멜로 1개를 받는 거지만, 결과적으로는 1분 기다렸다가 2개 받는 게 최선이기 때문입니다.

 

 

관련 문제

그리디 알고리즘을 통해 해결할 수 있는 문제는 다양하다. 그 중에서 대표적인 문제는 다음과 같다.

 

• 활동 선택 문제
• 분할 가능 배낭 문제

 

이번 글에서는 활동 선택 문제에서 어떻게 그리디 알고리즘을 적용하고 JAVA로 코드를 구현해보겠다.

 

 

 

활동 선택 문제

활동 선택 문제의 대표적인 예는 한 강의실에서 여러 개의 수업을 듣는 다고 하였을 때 한번에 가장 많은 수업을 할 수 있는 경우를 고르는 문제이다.

 

아래의 표에서 Si는 시작시간, Fi는 종료시간을 의미하고 아래 그래프는 표를 시각화한 것이다.

다음의 예에서 매번 최선의 선택을 하는 경우는 최대한 많은 강의를 듣는 것이 목표이기 때문에 강의가 자신이 선택한 강의가 최대한 빨리 끝나면 되는 것이다.

 

그렇게 생각하였을 때 위의 상황에서는 첫번째 활동은 A1이 되고 그 뒤로 차례로 A3, A6, A8 강의를 듣게 되는 것이다.

 

 

코드 구현

import java.util.*;
import java.io.*;

public class Main {
    static class Lecture{
        int i; //몇번째 강의인지
        int start; //강의 시작시간
        int end; //강의 종료시간

        Lecture(int i, int start, int end) {
            this.i = i;
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine()); // 강의 개수 입력

        ArrayList<Lecture> lectures = new ArrayList<>();
        StringTokenizer str;

        for(int i = 0; i < n; i++) {  // 입력받은 강의 arraylist에 lecture 클래스 타입으로 저장
            str = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(str.nextToken());
            int start = Integer.parseInt(str.nextToken());
            int end = Integer.parseInt(str.nextToken());
            lectures.add(new Lecture(idx, start, end));
        }

        lectures.sort(new Comparator<Lecture>() { // 끝나는 시간 기준으로 오름차순 정렬
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return o1.end - o2.end;
            }
        });

        ArrayList<Integer> result = new ArrayList<>();
        int last = 0; //이전에 선택한 강의가 끝난 시점, 다음 강의는 이 시점 이후에 시작하는 강의를 선택
        for(int i = 0; i < n; i++) {
            if(last < lectures.get(i).start) {
                last = lectures.get(i).end;
                result.add(lectures.get(i).i);
            }
        }

        System.out.println(result.toString()); //결과 출력

        br.close();
        bw.close();

    }
}

 

위의 코드에서 input의 형태는 강의의 개수를 먼저 입력 받은 뒤 강의의 개수만큼 강의의 순서 index, 시작시간, 끝나는 시간을 공백으로 구분하여 입력 받는다. 위의 예시를 아래 코드에 적용하기 위해서 다음과 같이 input을 집어넣었고,

/*
9
1 1 3
2 2 5
3 4 7
4 1 8
5 5 9
6 8 10
7 9 11
8 11 14
9 13 16
*/

 

결과는 다음과 같이 출력이 된다.

// [1, 3, 6, 8]