[알고리즘] 그리디 알고리즘(Greedy Algorithms)

그리디 알고리즘(Greedy Algorithms)

그리디 알고리즘은 문제 해결과정에서 순간순간마다 최적이라고 생각되는 해를 선택하여, 최종 해답에 도달하는 문제 해결 방식이다.

 

 

출처 : https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

위의 그림은, 선택을 해야하는 순간에 가장 최선이라고 생각되는 해를 선택하는 동작방식을 보여준다.

최대 값을 구할때, 1과 9 중 하나를 골라야할때, 그 뒤의 값들은 전혀 고려하지 않고, 당장의 1과 9만 두고 어떤 것을 선택할지 고른다. 1과 9 중에는 당연히 9가 크기 때문에 9를 고르고, 3과 12 중에는 12를 고르게 된다. 이런 식으로 구한 최대 값은 12이다. 하지만 그림을 보면 알 수 있듯 이 이진 트리에서 최대 값은 99이다.

 

이렇듯 그리디 알고리즘과 같이 순간순간 최선의 결정을 선택하는 것이 항상 문제의 최선의 해결책이 되지는 않는다.

 

하지만 이런 단점들을 극복하는 그리디 알고리즘의 가장 큰 장점은 계산 속도에 있다. 그리디 방법으로 해결할 수 있는 몇몇 문제에서는 최적해를 빠르게 찾아낼 수 있다.

 

그리디 알고리즘을 사용할 수 있는 문제는 아래 두가지 속성을 만족한다.

1.  greedy choice property : 앞의 선택이, 이후의 선택에 영향을 주지 않는다.

2.  optimal substructure : 문제 전체에 대한 최적해가 부분문제에 대해서도 역시 최적해가 된다.

 

대표적인 그리디 알고리즘 문제를 살펴보자.

---

분할 가능한 배낭 문제

배낭문제는 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이때 분할 가능한 배낭 문제는, 이 짐들을 쪼갤수 있는 경우이다.

 

이러한 분할 가능한 배낭 문제는, 무게당 가치가 가장 큰 짐을 먼저 넣으면 최적의 해를 구할 수 있다.

순간순간의 선택이 이후 선택에 영향을 주지 않고(greedy choice property) , 순간순간의 최적의 선택이 전체 문제의 최적해와 일치한다(optimal substructure).

 

반면에 짐을 쪼갤수 없는 배낭 문제, 0-1 배낭문제는 동적 계획법을 이용하여 문제를 풀어야한다. 가능한 모든 조합에 대해 가치를 따져보고, 이 중에서 합이 최대가 되는 것을 골라야하기 때문이다.

 

---

회의실 배정 문제

회사에 회의실이 1개 있다. 각 부서는 미리 회의실 사용을 미리 신청 받아 스케줄링을 한다. 회의실을 사용하고자 하는 부서는 원하는 회의 시작시간과 종료시간을 명시하여 신청서를 제출한다. 이렇게 받은 n개의 회의 신청에 대해 회의실 사용 스케줄을 정하려고 한다. 

겹치는 회의가 없게 하면서, 가장 많은 수의 회의를 할 수 있도록 하는 것이 목표이다.

(구현을 위해, 앞 회의 종료 시간과 바로 다음 회의 시작 시간이 같아도 된다.)

 

생각해 볼 수 있는 Greedy한 아이디어는

 

1. 소요시간이 가장 짧은 회의순

2. 시작시간이 가장 빠른 회의순

3. 종료시간이 가장 이른 회의순

 

여러개의 Greedy한 아이디어가 있지만, 이중에서 그리디 알고리즘이 최적해를 보장하는 것은 3. 종료시간이 가장 이른 회의순 뿐이다.

 

- 알고리즘

Greedy_Schedule(S, n) {
// S = 신청 회의, n = 신청 회의 수
// si = 시작시간 , ti = 종료시간

종료시간에 대한 오름차순으로 정렬하고, 이 순서대로 S의 번호를 다시 매긴다.
T <- {1}
last <- 1
for (i <- 2, i<=n, i++) 
	if (tlast <= S[i]) { // last회의의 끝나는 시간이 다음 회의 시작시간보다 작은 경우
    	T <- T U {i}
        last <- i
      }
 
 return T;

예를 들어, 아래와 같이 8개의 회의가 신청되었다고 하자. (시작 시간, 종료 시간)

(3, 5) , (1, 6) , (6, 7), (5, 9), (8, 13), (7, 14), (12, 18), (16, 20)

위의 알고리즘 대로 회의실 스케줄을 짜면, 

(3, 5) , (1, 6) , (6, 7), (5, 9), (8, 13), (7, 14), (12, 18), (16, 20)

 

 

---

 

◎ 참고 자료

ratsgo.github.io/data%20structure&algorithm/2017/11/22/greedy/

탐욕 알고리즘 · ratsgo's blog

https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm)

쉽게 배우는 알고리즘. Chapter 11 그리디 알고리즘