탐욕 알고리즘 (그리디 알고리즘, Greedy Algorithm)

Greedy Algorithm

탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다.

목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다.

그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다.

하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까?

그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 

이와 같이 그리디 알고리즘은 최적의 해를 보장하지 않는다. 일반적으로는 최적의 해와 근사한 해를 구하는 용도로 사용된다.

 

그리디 알고리즘을 적용할 수 있는 문제

하지만 그리디 알고리즘을 적용했을 때 최적해를 구할 수 있는 문제들도 존재한다.

이러한 문제들은 대부분 다음과 같은 조건을 만족한다.

 

Greedy Choice Property

각 단계에서 최적의 선택을 하면, 전역적인(Global) 최적해에 도달할 수 있다.

 

Optimal Substructure

문제 전체에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다.

즉, 결정 상황에서 그리디 알고리즘을 통해 선택하는 방법 자체가 곧 문제 전체를 해결하는 방법과 같아야 한다.

 

그리디 알고리즘을 적용해 해결할 수 있는 문제들의 대표적인 유형 두 가지에 대해 알아보자.

활동 선택 문제 (Activity Selection Problem)

간단하게 설명하자면 최대한 많은 강의를 듣는 시간표를 짜는 것과 같다. 다음과 같은 예시를 보자.

활동 선택 문제 : 강의 시간표 짜기

위와 같은 강의 목록들 중, 강의들이 겹치지 않게 최대한 많은 강의를 수강하려면 어떻게 해야 할까? 

내가 들을 수 있는 강의의 개수를 많게 하기 위해서는, 빨리 끝나는 강의를 선택하는 것이 유리할 것이다. 강의가 빨리 끝날수록, 내가 선택할 수 있는 강의의 폭이 더 넓어지기 때문이다.

그리디 알고리즘을 적용해, 빨리 끝나는 강의 순서대로 겹치지 않는 한 강의를 선택하면 다음과 같다.

답은 (1, 3, 7, 9)도 가능하다.

이 문제는 각 상태에서 최적의 선택을 진행했을 때 전체 문제의 최적해에 도달할 수 있는 문제이다.

1번 강의를 수강한 이후 다음 최적의 강의를 선택하는 방법도 최초 1번 강의를 선택한 방법과 같고, 이는 곧 문제 전체를 해결하는 방법과 같기 때문에 그리디 알고리즘을 통해 해결할 수 있는 문제가 된다.

 

분할 가능 배낭 문제 (Fractional Knapsack Problem)

0-1 배낭 문제는 각 보석들이 주어졌을 때, 배낭에 담는 보석들의 가치 총합이 최대가 되도록 하는 문제이다. 이 문제에서 모든 보석들은 담거나, 담지 않거나 두 경우만 가능하다.

하지만 분할 가능 배낭 문제는 보석들을 원하는 무게만큼 쪼갤 수 있다. 다음과 같은 예시를 보자.

분할 가능 배낭 문제

0-1 배낭 문제와는 달리, 분할 가능 배낭 문제는 주어진 보석들의 총 무게가 배낭의 수용 가능 무게 이상이라면 반드시 배낭을 꽉 채워 보석을 담을 수 있다.

따라서, 이 문제를 해결하기 위해서는 각 보석들의 실질적인 가치 순으로 담아야 할 것이다.

분할 가능 배낭 문제의 해결

위와 같이 각 보석의 가치는 무게 1당 가격을 통해 나타낼 수 있다. 이 가치가 가장 높은 보석부터 배낭이 허용하는 한 최대로 담는다면, 최대 가격으로 보석들을 담을 수 있다.

이 문제에서도 "무게 당 가격이 가장 높은 보석을 가능한 담는다" 라는 방법이 각 보석을 담는 단계마다 사용되었다. 초록색 보석을 모두 담은 후에도 이 방법은 변하지 않는다.

이 방법 자체가 문제 전체의 최적해를 구하는 방법과도 같으므로, 이 문제는 그리디 알고리즘으로 해결할 수 있다.

 

그리디 알고리즘과 다이나믹 프로그래밍

그리디 알고리즘과 다이나믹 프로그래밍은 많은 부분에서 유사하다.

맨 처음 소개한 예시를 다시 들어보자.

목적지까지 최단 경로로 가고 싶다!

다이나믹 프로그래밍은 모든 부분 문제를 풀어 항상 최적의 답을 구한다. 최단 거리의 예제에서는, 가능한 모든 길을 다 살펴본 후, 그 중 최단거리인 길을 선택하여 가는 것과 같다.

하지만 그리디 알고리즘은 모든 부분 문제를 풀지 않는다. 그저 선택이 필요할 때 마다 이후의 상황은 고려하지 않고 그때그때 최선인 선택을 하는 것이다. 이를 통해 구한 답은 정답일 수 있지만, 그렇지 않을 확률도 높다.

그렇다면 그리디 알고리즘은 왜 쓰는 것일까?

다이나믹 프로그래밍은 모든 부분 문제를 풀기 때문에, 전체 문제의 크기가 클수록, 가능한 선택의 경우가 많을수록 최적해를 찾는 데 많은 메모리와 시간이 소요된다. 하지만 그리디 알고리즘은 메모리와 속도 면에서 다이나믹 프로그래밍에 비해 효율적이다. 

따라서 그리디 알고리즘과 다이나믹 프로그래밍은 서로 보완하는 관계로 이해한다.

 

그리디 알고리즘 응용 문제 해결

그리디 알고리즘 문제는 DP문제와 비슷한 경우가 많다. 그리디 알고리즘 문제는 다이나믹 프로그래밍으로도 해결 가능하기 때문이다. DP문제의 느낌이 나지만 시간 또는 메모리 제약이 빡빡하거나 다루어야 할 케이스가 지나치게 많을 것 같은 경우 그리디 알고리즘 문제로 의심해볼만 하다.

문제가 유사하기 때문에 DP 문제와 동일한 느낌으로 어렵다. 문제 해결의 Key를 찾는 것이 곧 문제 해결로 이어지기 때문에 이 Key를 캐치하지 못하면 풀이 시간이 정말 오래 걸릴 수 있다.

그리디 알고리즘을 통한 해결을 의도한 문제들은 대부분 다음과 같은 해결 과정을 따른다.

① 각 요소들을 특정 기준으로 정렬한다.

② 정렬한 요소들을 훑으며 부분 문제들을 해결하면서 결과적으로 전체 문제를 해결한다. (DP와 유사)

 

[연습 문제]

BOJ 11000 강의실 배정 : www.acmicpc.net/problem/11000

11000번: 강의실 배정