[Algorithm] 탐욕 알고리즘(Greedy Algorithm) 파해쳐보기

탐욕 알고리즘. 그리디 알고리즘(Greedy Algorithm)이라고도 불리는 알고리즘에 대해서 알아보겠습니다.(이하 그리디 알고리즘이라고 부름)

 

  그리디 알고리즘은 동적 프로그래밍(Dynamic Programming) 사용 시 지나치게 많은 처리를 한다는 것에 착안하여 고안된 알고리즘입니다. 동적 프로그래밍과 함께 상호보완하는 개념입니다.

 

  그리디(탐욕) 알고리즘이라는 이름이 붙게 된 이유는 '미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법'이기 때문에 지어졌다고 합니다. 각 단계에서 최선의 선택을 하는 것이 결국 전체의 최선이길 바라는 알고리즘이죠.

 

  모든 경우에서 그리디 알고리즘이 최대 효율을 만들어주지는 못합니다. 쉬운 예로 마시멜로 이야기와 함께 해보겠습니다. 지금 마시멜로우를 앞에 두고 당장 그 마시멜로우를 집게 되면 1개만 먹을 수 있지만 15분을 기다린다면 2개의 마시멜로우를 먹을 수 있는 경우 그리디 알고리즘을 사용하게 되면 항상 마시멜로우를 1개 밖에 먹지 못합니다. 당장 최선의 선택은 1개를 받는 거지만 15분을 기다린 다면 2개를 받는게 최선이기 때문이죠.

 

  그러나 그리디 알고리즘이 통하는 몇몇 문제들이 있습니다. 그 문제들 중 '활동 선택 문제'와 '분할 가능 배낭 문제'를 풀어보겠습니다.

 

 

 

 

 

[1] 활동 선택 문제

 

  활동 선택 문제는 쉽게 말하면 '하나의 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것'입니다.

 

i	a(1)	a(2)	a(3)	a(4)	a(5)	a(6)	a(7)	a(8)	a(9)
s(i)	1	2	4	1	5	8	9	11	13
f(i)	3	5	7	8	9	10	11	14	16

  위 표를 살펴봅시다. s(i)는 '시작시간', f(i)는 '종료시간'입니다. 같은 강의실을 사용해야 하므로 a(1)과 a(2) 또는 a(4)은 동시에 선택이 불가능합니다. 하지만 a(1)과 a(3)은 선택이 가능하죠. 이런 방식으로 시작시간과 끝나는 시간을 겹치지 않게 최대한 많이 운용할 수 있는 방법을 찾는 것입니다.

 

  이를 정리해보자면

 

case1 :  a(1) - a(3) - a(6) - a(8)

case2 : a(1) - a(3) - a(7) - a(9)

case3 ...

 

  와 같이 정리 됩니다. 결과적으로 보면 a(1), a(3), a(6), a(8)이나 a(1), a(3), a(7), a(9) 등을 고르면 정답입니다. 문제는 코딩을 통해 이걸을 어떻게 고르도록 시키느냐겠죠?

 

  이 문제는 동적 프로그래밍을 통해서도 풀 수 있습니다. 하나의 예를 들어 G18을 a(1)이 종료된 후부터, a(8)이 시작하기 전 활동들의 집합이라고 보면 G18 = {a(3), a(5), a(6), a(7)}입니다. 이 중에서 최적의 조합(활동들이 겹치지 않고 개수는 최대)을 B18이라고 하면, 하나의 예로 B18 = {a(3), a(6)} 또는 B18 = {a(3), a(7)}가 되겠네요.

 

  B18에서 a(6)을 골랐다고 치면 문제는 두개로 쪼개집니다. G16과 G68에서 각각 최적인 B16와 B18을 찾는 것이죠. 이제 B16과 B18을 더하면 최적 활동의 개수를 알 수 있습니다. 이를 식으로 나타내면

 

C[i, j] = max(C[i, k] + C[k, j] + 1)

 

  이 됩니다. C는 집합 Gij의 최적 개수를 개수를 나타냅니다. max는 B18에서 a(6) 말고 다른 골랐을 때의 경우도 모두 생각해서 그 중 최적을 찾는 겁니다.

 

  이렇게 동적 프로그래밍으로도 가능하지만, 문제는 이렇게 하면 모든 C들을 구해야 하며 우리에게 필요한 결과가 아닙니다. 하지만 우리는 그리디 알고리즘으로 더 효율적으로 풀 수 있습니다.

 

  직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동을 최대한 일찍 끝나게 해야합니다. 그래야 다른 활동들을 더 많이 선택할 수 있기 때문이죠. 위의 경우에서는 첫 선택으로 가장 빨리 끝나는 a(1)을 골라야겠죠. a(1)을 골랐다면 이제 a(2)와 a(4)는 고를 수 없습니다. 그 다음 선택은 그 다음으로 일찍 끝나는 a(3)가 될 겁니다. 그 다음은 a(6), 마지막은 a(8)이 되어 최종적으로 {a(1), a(3), a(6), a(8)}이 됩니다.

 

[example_1]

  1. sort()을 통해 끝나는 시간 순으로 정렬

  2. 반복문을 돌며 집합의 끝나는 시간이 다음 행동의 시작 시간보다 작은 경우 집합에 추가

 

 

 

 

 

 

[2] 분할 가능 배낭 문제

 

  분할 가능 배낭 문제는 일정 무게를 담을 수 있는 배낭에 물건을 최대한 넣을 수 있도록 합니다. 또한 배낭에 넣을 물건을 쪼개어 넣을 수 있습니다. 물건을 쪼개어 넣을 수 있다는 가정 하에서는 무엇을 넣는 것이 최우선일까요?

 

  무게 대비 가치가 높은 물건들을 넣고 남은 무게에 따른 가장 높은 가치의 물건을 쪼개어 넣으면 됩니다.

 

i	1	2	3
v(i)	60	100	120
w(i)	10	20	30
v(i) / w(i)	6	5	4

 

  무게 제한은 50입니다. 최대한 꽉꽉 넣어주는 것이 중요하기 때문에 1번, 2번, 3번 순으로 넣고 3번을 넣을 때는 무게 초과이기 때문에 20만큼 쪼개어 넣으면 됩니다.

 

[exmple_2]

 

1. 무게 대비 가치 순으로 정렬

2. 가치 순으로 result에 집어 넣기

3. 무게가 제한 이하 일 경우 계속 집어 넣음

4. 물건 무게가 제한 초과일 경우 들어갈 현재 물건을 들어갈 수 있는 물게 만큼 잘라서 넣음(limit = 0을 통해 탈출)

 

  이 문제의 경우도 [1] 활동 선택 문제처럼, 앞에서부터 그때 그때 가장 최선인 선택을 하면 결과적으로도 최선입니다.

 

  지금까지 그리디 알고리즘을 알아보았는데요. 그리디를 사용한 프림 알고리즘과 다익스트라 알고리즘에 대해서도 알아보면 좋겠습니다.

 

 

원문 : https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188