Greedy Algorithm

안녕하세요. 이번 포스팅에서는 Greedy Algorithm에 대해서 다뤄보도록 하겠습니다.

 

코딩테스트를 준비하는 입장에서 Greedy 알고리즘은 가장 기본이 되는 유형으로 여겨집니다. 난이도가 상대적으로 낮은 유형에 해당하며, 그렇기 때문에 가장 먼저 시작할 수 있는 유형으로 많이 추천됩니다. 하지만 가장 기본이 되는 유형이라고 해서 결코 쉬운 문제들만 있는 것은 아닙니다. 실제로 여러 문제들을 살펴보면 Greedy 유형이더라도 많이 어려운 문제들도 있습니다. 즉, 결코 만만하게 볼 유형은 아닙니다. 그렇다면 지금부터 Greedy 알고리즘이 무엇인지에 대해서 알아보도록 하겠습니다.

 

Greedy Algorithm? 탐욕 알고리즘?

우선 알고리즘의 이름에 사용되는 "Greedy" 라는 단어의 사전적 정의를 찾아보면 다음과 같습니다.

탐욕스러운, 욕심많은

Greedy 알고리즘은 발음 그대로 "그리디 알고리즘" 이라고 표현하기도 하고, 번역하여 "탐욕 알고리즘" 이라고 부르기도 합니다. 이러한 사전적 정의가 해당 알고리즘과 어떻게 연결되는 것인 지 와닿지 않을 수 있습니다. 그렇다면 왜 "Greedy" 라는 용어가 사용된 것인지 알아보도록 하겠습니다.

 

우리가 Greedy 알고리즘을 기억할 때 꼭 기억해야할 한 가지 원칙은 다음과 같습니다.

현재 상황에서 가장 최선이라고 판단되는 선택을 한다.

 

 

예시를 통해서 알아보도록 하겠습니다. 만약 아래와 같이 구성된 Tree의 구성 요소 중에서 가장 작은 값을 탐색해야하는 상황이라고 할 때, 이 문제에 그리디 알고리즘의 접근방식을 적용하여 살펴보도록 하겠습니다. 아래와 같은 Tree가 있다고 할 때 한 사람이 해당 Tree를 구성하는 node 중에서 가장 작은 값이 무엇인지를 알아야 하는 상황입니다. 사람은 root node인 15에서 출발하고, 현재 자신이 위치한 node의 바로 아래단계에 위치하는 children node들의 값만을 볼 수 있습니다. 즉, 사람이 값이 15인 node에 있으면 한 단계 아래에 있는 3, 5의 값만 볼 수 있습니다.

"child node 중에서 더 작은 원소를 선택한다." 라는 접근 방법으로 해당 문제를 바라본다면 root node부터 출발했을 때 해당 Tree의 구성 node 중에서 가장 작은 값은 "3"이 됩니다. 하지만 실제로 해당 Tree에서 node의 값 중 가장 작은 값은 1이기 때문에 이러한 접근 방법을 통해서 최적의 해를 발견하지 못했음을 알 수 있습니다.

 

즉, 이 예시를 통해서 살펴볼 수 있는 중요한 점은 현재 상황에서 가장 최선이라고 판단되는 선택을 반복하는 것이 결과적으로도 최적의 해임을 보장할 수는 없다는 것입니다. 따라서, 반드시 어떤 주어진 문제의 상황에 대해서 최적의 해를 구해야하는 상황에 항상 Greedy 알고리즘이 유효한 해를 얻음을 보장할 수 없기 때문에 만약 Greedy 알고리즘을 적용하여 문제를 해결하고 싶다면, 항상 다음 질문에 대해서 생각해봐야할 필요가 있습니다. 

각 상황에서 가장 최선이라고 판단되는 선택을 하는 것이 결과적으로 최적해로 연결 됨을 보장할 수 있는 가?

 

 

그렇기 때문에 매번 최선의 선택을 하는 것이 결과적으로도 최선의 선택이 됨을 확인하기 위해서는 몇가지 조건을 체크할 필요가 있는데, 우리는 이것을 가리켜 "Greedy 조건" 이라고 표현합니다. 즉, Greedy 알고리즘을 사용하기 위해서는 다음 두 가지 조건을 만족해야 합니다.

1. 탐욕스러운 선택조건
2. 최적부분 구조조건

"현재 상황에서  가장 최선이라고 판단되는 선택을 한다" 라는 이 원칙을 가리켜서 우리는 "탐욕적인 선택" 이라는 표현을 사용하며, 다음 두 원칙을 설명함에 있어서 해당 용어을 사용하도록 하겠습니다.

 

1. 탐욕스러운 선택조건

"탐욕적인 선택은 항상 안전하다" 라는 사실이 보장되어야 합니다. 즉, 안전하다는 의미는 탐욕적인 선택을 반복하게 되면 결과적으로 항상 최적의 해에 도달할 수 있는 사실이 보장되어야 한다는 것입니다. 사실 이 사실을 증명하기 위해서는 상당히 복잡한 내용의 수학적 증명이 필요해집니다. 실제로 학부 과정에서 알고리즘 공부에 많이 사용하는 서적에서도 이러한 수학적 증명을 통한 접근 방법으로 이야기를 풀어가고 있습니다. 하지만 이 내용은 이해하기도 어려울 뿐더러 코딩테스트를 응시하는 입장에서 해결할 문제에 적용할 탐욕스러운 선택조건이 항상 안전함을 증명하기 위해 사용할 수 있는 시간은 없습니다.

 

그래서 완벽한 증명을 위해서는 원론적인 내용들도 많이 다루고 다소 복잡한 내용들이 많이 들어가기에, 이 부분에 대한 내용은 생략하고 넘어가도록 하겠습니다. 대신 현재 내가 풀어야하는 문제가 그리디로 풀어도 된다는 수학적 증명을 어떻게 할 지를 고민하는 것보다는 그리디 알고리즘을 사용한 유형의 문제를 많이 풀어보고 이를 통해 느낌을 잡아가는 것이 더 효율적이라고 볼 수 있겠습니다.

 

2. 최적부분 구조조건

"최적부분 구조조건"은 현재 문제에 대한 최적의 해결방법이 다른 부분 문제에 대해서도 최적의 해결방법이라는 사실이 보장되어야 한다는 것입니다. 주어진 문제를 여러 개로 나누고, 그 나눠진 각각의 문제에 대해서 최적의 해를 도출하여 이를 다시 하나로 모으면, 그것이 결국 해당 문제에 대한 최적의 해가 된다는 것입니다. 해당 조건은 주어진 문제를 여러 개의 소문제로 나눠보고 이를 이해하는 과정에서 판단할 수 있습니다.

 

Greedy 알고리즘의 방법론은 아주 강력해서 광범위한 문제에 적용됩니다. 단순히 이 알고리즘의 개념으로 끝나는 것이 아니라, 컴퓨터 공학에서 많이 등장하고 그만큼 중요한 다음 알고리즘들로 응용될 수 있습니다.

1. 최소신장트리(minimum spanning trees) 알고리즘
2. 다익스트라 알고리즘
3. Chvatal의 집합 감싸기 (set-covering) 휴리스틱

기회가 된다면 해당 알고리즘들에 대해서도 정리해보는 시간을 가지도록 하겠습니다.

 

이론만 하지 말고 문제풀이로도 접근해보자.

그리디 알고리즘을 사용한 문제해결의 가장 대표적인 예시는 바로 동전과 관련된 예시일 것입니다. 관련 문제로는 백준 11047번 문제를 인용하여 사용하였습니다.

https://www.acmicpc.net/problem/11047

11047번: 동전 0

해당 문제에서 요구하는 내용은 다양한 단위의 동전들을 주고, 목표 금액을 제시했을 때 해당 목표금액을 만들 수 있는 경우의 수 중에서 가장 적은 수의 동전으로 만족하는 경우를 구하는 것입니다. 이 문제를 해결하기 위한 방법을 생각해볼 때 이전에 살펴본 그리디 알고리즘의 이론을 쉽게 적용할 수 있습니다.

 

현재 남은 금액보다 작은 단위 중에서 가장 큰 단위의 동전을 선택한다.

 

 

현재 남은 금액보다 작은 단위 중에서 가장 큰 단위의 동전을 지속적으로 선택하는 방식이 결과적으로 주어진 목표금액을 가장 적은 수의 동전으로 지불할 수 있음은 직관적으로 이해할 수 있는 사실입니다. 아래의 예시를 통해서 해당 문제를 어떻게 접근하여 해결하고, 어떠한 부분이 그리디 알고리즘의 맥락과 일치하는 지 확인할 수 있을 것입니다.

 

즉, 각각의 나눠진 상황에서 최선을 선택을 하는 것이 결과적으로도 최적의 해로 이어지는 대표적인 Greedy 알고리즘을 활용한 문제 해결의 예시를 볼 수 있었습니다. 해당 문제를 해결하기 위한 코드도 아래와 같이 작성해볼 수 있습니다.

// BOJ - 11047
// Problem Sheet - https://www.acmicpc.net/problem/11047

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int n = key.nextInt(); // the number of coins
		int k = key.nextInt(); // values
		int[] values = new int[n]; // the unit of coins
		for(int i=0 ; i<n ; i++)
			values[i] = key.nextInt();
		int counts = 0; // the minimum number of coins
		int tmp = 0;    // cache for the calculation
		
		// find the optimal solutions
		for(int i=n-1 ; i>=0 ; i--) {
			if(tmp == k) break;
			if(values[i] <= k-tmp) {
				counts += (k-tmp)/values[i];
				tmp += values[i] * ((k-tmp)/values[i]);
			}
		}

		System.out.println(counts);

		key.close();
		System.exit(0);
	}
}

 

이것으로 Greedy 알고리즘에 대한 글을 마치도록 하겠습니다. 감사합니다.