DP와 Greedy Algorithm

◎ Greedy Algorithm 이란? 

 

탐욕 알고리즘(Greedy Algorithm) 이란, 최적해를 구하는데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다. '순간' 이라고 정의하는 선택은 Local 하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그것이 최적이라는 어떠한 보장도 없다.

 

 탐욕 알고리즘에는 대표적으로 '분할 가능 배낭문제' 가 있는데, 다음과 같은 예시를 들어보자.

한 은행의 화폐 단위가 7원/5원/1원 이라고 하자. 
한 사람이 14원의 돈을 들고 화폐를 교환하려고 은행에 들렀다. 
은행은 Greedy Algorithm을 사용하여 화폐를 교환해준다.

Greedy Algorithm은 매 순간마다 최적의 수를 고려한다. 따라서 14원이라는 돈이 주어졌을 때 최대로 줄 수 있는 금액은 7원이므로 7원 화폐 2장으로 교환해주면 된다. 이는 Global Optimal과 일치하므로 최적해를 찾았다고 할 수 있다.

 

그렇다면, 다음과 같은 예시를 보자.

한 은행의 화폐 단위가 12원/7원/5원/1원 이라고 하자. 
한 사람이 14원의 돈을 들고 화폐를 교환하려고 은행에 들렀다. 
은행은 Greedy Algorithm을 사용하여 화폐를 교환해준다.

 

 14원 이라는 금액에서 최대로 줄 수 있는 금액은 12원 화폐이므로 12원 화폐 1장을 지급한다.

나머지 금액은 2원 이므로 1원 화폐 2장을 지급한다.

따라서 14원의 화폐는 12원의 화폐 1장, 1원의 화폐 2장으로 총 3장의 화폐로 교환된다.

하지만 14원은 직관적으로 알 수 있듯이, 7원짜리 2장이면 교환이 가능하다. 

 

 Greedy Algorithm은 최적해를 찾기 위해 매 순간(Local)마다 최적의 수를 계산하여 최종적으로 최적화된 값을 찾을때도 있지만, 위의 예시와 같이 SubProblem이 모여진 해답이 Global하게는 항상 최적이라는 보장을 하지 않는다. Greedy Algorithm이 잘 동작하기 위해서는 Greedy Choice Property 와 Optimal substructure라는 두 가지 속성을 만족해야한다.

- Greedy Choice Property : subproblem의 해답이 다음 subproblem에 영향이 가지 않는다는 독립적인 연산 속성

- Optimal Substructure : 문제 전체의 최적해(Global Optimal)이 Subproblem에서도 최적해가 된다는 속성

 

 쉽게 말하면, Greedy Algorithm은 매 순간마다 최적의 수를 계산한다 했으므로 각 순간은 독립적이며 그 결과가 어느 순간에도 영향을 끼치지 않는다는 속성과 매 순간마다 구한 최적의 수가 전체 문제에 대한 최적해와 같아야된다는 속성입니다.

 

◎ 그렇다면 Greedy Algorithm 이 저 두 속성을 만족하지 않는다면 안좋은 것일까? 

 

 아니다, 위와 같이 Greedy Algorithm이 최적해를 보장하지 않지만 근사 알고리즘으로 사용이 가능할 수 있으며 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용이 가능하다. (이 경우에도 역시 어느정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다) 최적해는 아니지만 최적해에 가까운 값을 사용함으로써 어느정도의 Loss를 감안하고 빠른 실행 시간 또는 다른 이득을 취할 수 있다는 것이다.

 

 

◎ Dynamic Programming 과 Greedy Algorithm 비교

 

Dynamic Programming에 대한 설명은 이전 Post를 참고.

DP(Dynamic Programming)

 

 Dynamic Programming 은 '쪼갤 수 없는 배낭문제' 를 주로 다룬다. 짐을 쪼갤 수 없기 때문에 가능한 모든 조합에 대해 일일이 따져본 후 가치의 합이 최대가 되도록 하는 조합을 찾는 문제가 된다. 다시 말해 모든 경우의 수를 따져보되 중간 계산 결과를 저장해두고 이를 다음 계산에 써먹는 방식으로 계산량 감소를 유도하는 전략이다. 주로 DP에선 Recursive 관계를 찾는 것이 핵심이다. 

 

배낭	A	B	C
가격(V)	60	100	120
무게(W)	10	20	30
가치(V/W)	6	5	4

다음과 같은 배낭 문제가 있다고 하자. 배낭의 무게는 최대 50까지 담을 수 있다. 쪼갤 수 없는 배낭 문제라는 것은 물건을 쪼개서 넣을 수 없고 선택지가 통째로 넣거나 아예 안 넣거나 두 개밖에 없기 때문이다. 

그렇다면 위의 예시에서 Global Optimal 은 무엇일까?

 

직관적으로만 본다면 가져갈 수 있는 최대 배낭의 무게가 50이므로  B와 C를 넣어 무게는 50, 가격은 220으로 가져가면 될 것이다. 하지만 컴퓨터에겐 직관이라는 것이없다. 컴퓨터는 직접 모든 경우의 수를 계산해보아야한다. 가장 간단하게 무게 대비 가치의 순서에 따라 짐을 고를 수 있을 것이다. 처음에 {A,B}를 골랐지만 이는 Global Optimal이 아니다. 다음 가치 순서에 따라 계속 비교한다.

 

Case	무게	가격
A,B	30	160
A,C	40	180
B,C	50	220

A,B,C 3개에서 2개를 조합해서 뽑는 경우의 수는 $$3C2$$ 이므로 3가지 이다. 각 3가지 경우의 수에 따라 가격을 모두 비교해본 후 가격이 제일 높은 {B,C} 경우의 수를 선택하게 된다. 사실 어떠한 정해진 방법이 없다. 그냥 모두 대입해 푸는 것이다.

 

 앞서 설명했듯, DP는 모든 경우의 수를 따져본다는 단점이 있다. 이러한 단점을 극복하기 위해 나온것이 Greedy Algorithm인데 Greedy Algorithm 은 항상 최적해를 보장하진 않지만 모든 경우의 수를 따지지 않고 Local optimal을 찾아 계산 속도가 빠르고 근사 알고리즘으로 사용이 가능하다. 또한 Greedy Algorithm은 Minimum spanning tree(최소신장트리) 등 여러 문제에서 최적해를 구할 수 있음이 이미 입증되기도 했다. 

 

 DP와 Greedy Algorithm을 비교하기 위해 예시를 들어보자.

스크루지가 차를 몰고 퇴근하고 있다.
스크루지는 퇴근 시간이라 차량이 많이 막히는 정체 구간 A에서 
집으로 최대한 빠르게 이동하는 경로를 찾고 싶어한다.

 이 문제에 대해 DP를 사용한다면 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 요즘 네비게이션을 보면 주변 교통상황을 모두 따져보고 최적의 길을 알려주던데.. DP를 사용한것이라 생각한다.

반면, Greedy Algorithm을 사용한다면 전체의 교통상황은 고려하지 않고 순간순간 교차로가 보일 때마다 차량이 가장 적어보이는 가장 빠른 경로를 선택할 것이다.

 

 DP를 사용하면 Global Optimal을 찾을 수 있지만 Greedy Algorithm에 비해 그 연산량이 많아 시간이 오래 걸린다. Greedy Algorithm은 즉효성이 있는 대신 항상 Global Optimal을 찾아 주지 않는다. 각 구간마다 최적의 경로를 찾는다 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 

 

즉, DP는 Greedy Algorithm과 Optimal Substructure라는 하위 문제를 해결했을때 원래 문제를 해결할 수 있는 속성은 동일하지만 Time Complexity는 DP가 더 높고 그 결과에  대해 보다 신뢰적이라고 할 수 있겠다.