욕심쟁이 알고리즘(Greedy Algorithm)

앞선 알고리즘 소개 포스트를 통해 완전 탐색을 알아보았는데, 완전 탐색(brute force)의 핵심은 큰 문제를 작은 문제로 분할하여 모든 경우를 탐색해보는 것이었으며 그 중, 작은 문제로의 분할이 가장 핵심이라고 볼 수 있다. 이는 비단 완전 탐색에 국한되는 것이 아니라 향후 다룰 동적 계획법(Dynamic Programming)이든, 지금 다룰 욕심쟁이 알고리즘이든 모든 알고리즘 문제의 가장 기본이 된다고 볼 수 있다.

 

완전 탐색이 모든 경우에 대해 체크한 후 최적의 해를 골라내는 것이었다면, 욕심쟁이 혹은 탐욕법(Greedy)의 경우 각 단계마다 현재 최선의 방법만을 선택하는 것을 의미한다.

 

다만 늘 현재의 최선의 해답만을 선택하므로, 앞으로 남은 선택지들에 대한 사항은 고려하지 않게 되는데 이로 인해 욕심쟁이 알고리즘을 선택할 수 있는 경우가 제한된다. 다시 말해, 욕심쟁이 알고리즘은 늘 최적의 답을 구해낼 수 없다는 의미이기도 하다. 그렇다면 언제 욕심쟁이 알고리즘을 선택해야 할까?

 

욕심쟁이 알고리즘에는 두 가지 핵심 속성이 존재하며, 이를 충족해야 욕심쟁이 알고리즘으로 풀이할 수 있다.

 

탐욕적 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure)

 

1. 탐욕적 선택 속성(greedy choice property)

탐욕적으로 부분 문제에 대한 해답을 선택하더라도, 최적해를 구할 수 있다.

각 단계에서 선택한 최적의 해답은 전체 문제의 최적해로 가는 길임을 증명할 수 있어야 한다는 내용으로, 탐욕적 선택을 하더라도 '손해보는 일'이 없다는 것을 증명해야 한다.

 

2. 최적 부분 구조(optimal substructure)

부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다.

계속해서 언급하는 부분 문제를 최적해를 선택할 수 있도록 구성할 수 있느냐는 의미이다. 이는 어찌 보면 당연한 내용인지라, 별도의 증명 과정은 필요로 하지 않기도 한다.

 

욕심쟁이 알고리즘을 설명할 때 흔히 회의실 배정 문제를 대표적인 예시로 제공하는데, 함께 살펴보도록 한다.

1931번: 회의실 배정

 

한 개의 회의실이 있고 N 개의 회의 스케줄이 존재할 때, 가장 많은 회의를 배정할 수 있는 경우 몇 개의 회의를 배정할 수 있을까? 에 대한 문제다.

 

무식하게 풀어보는 방법을 먼저 생각해봤을 때, 만들 수 있는 모든 부분집합을 생성하여 개최 가능한 회의의 개수를 세아려 볼 수 있겠다. 하지만 N개의 input 에 대한 부분집합의 개수는 `2^n` 개 만큼 존재하므로 연산 횟수가 기하급수적으로 늘어나게 될 것이다.

 

이 문제를 풀이하는 정답은 우선 '가장 일찍 끝나는 회의를 항상 선택한다' 이다.

 

이를 앞선 두 가지 조건에 대입해 본다면 다음과 같다.

 

1. 가장 빨리 끝나는 회의를 포함하는 최적해가 반드시 존재한다.

2. 가장 빨리 끝나는 회의를 선택하고 남은 회의(겹치지 않는 회의)들에서 가장 많은 회의를 선택하면 된다.

 

가장 빨리 끝나는 회의를 선택하고, 이 회의와 시간이 겹치는 회의는 목록에서 배제했을 경우에, 배제된 목록의 회의들은 선택한 회의보다 절대 빨리 끝날 수가 없는 회의들이다. 또한 배제 후에 생성된 목록은 또 다른 작은 문제로 풀 수 있으므로, 가장 빨리 끝나는 회의를 포함하는 최적해는 반드시 존재함을 증명할 수 있다.

 

코드를 통해 어떻게 풀이 되었는지 참고해보자.

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
        
		int N = Integer.parseInt(br.readLine());
		int arr[][] = new int[N][2];
		for(int i = 0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
        
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] a0, int[] a1) {
				if(a0[1] == a1[1])
					return Integer.compare(a0[0], a1[0]);
				return Integer.compare(a0[1], a1[1]);
			}
		});
        
		int cnt = 0;
		int end = -1;
		for(int i = 0; i < N; i++) {
			if(arr[i][0] >= end) {
				end = arr[i][1];
				cnt++;
			}
				
		}
        
		bw.write(String.valueOf(cnt));
		bw.flush();
		bw.close();
		br.close();
	}

}

 

끝나는 시간을 기준으로 input을 정렬 후에, 가장 빨리 끝나는 회의를 반복적으로 선택하는 과정을 확인할 수 있다.

---

사실 욕심쟁이 알고리즘의 경우 많은 문제를 접하고 풀어보는 것이 익숙해지는 가장 좋은 방법이라고 생각한다(어느 유형이든 안그렇겠냐만은). 욕심쟁이의 경우 대개 이를 완전 탐색으로 해결할지, DP로 해결할지 망설이는 유형의 문제들이 많은데 대표적인 케이스들을 문제로써 접해보고, 풀이를 보더라도 직접 증명하는 과정을 통해 욕심쟁이가 적합한 해결책임을 직접 느끼는 것이 최선이라고 생각한다. 완전 탐색으로 풀이해보고, 작은 문제들로 분리해본 다음 이전 값들을 활용해서 다음 최적해를 구할 수 있는가(DP)를 고민해 본 다음, 작은 문제들마다 최적해를 도출해도 무방하겠구나! 를 느껴봐야 하기 때문이다.

---

정리

• 욕심쟁이 알고리즘은 특정 순간에서의 최적의 해를 구할 수는 있으나, 종합적인 최적 해를 도출해낸다는 보장을 할 수 없다.
• 부분 최적해들의 집합이 전체 문제의 해답이 될 경우에만 사용할 수 있다.

---

참고 문제

1. Silver 5 - 거스름돈

 거스름돈 역시 대표적인 욕심쟁이 알고리즘 유형인데, 어떤 경우에 욕심쟁이 알고리즘을 채택할 수 있는지 고민해 보자.

14916번: 거스름돈

2. Silver 3 - 팰린드롬 만들기

1213번: 팰린드롬 만들기

3. Gold 5 - 주사위

1041번: 주사위

---

Reference

1.  프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1권_탐욕법_365p_구종만 지음