그리디(Greedy)
그리디 알고리즘은 탐욕 알고리즘이라는 뜻으로 최적해를 구하는 데에 사용되는 근사적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
위의 그림을 보면 가장 큰 숫자를 찾아야 하는데 단계 별로 큰 수를 찾는 방식으로 진행한다. 그 결과 최종적으로 12라는 숫자를 찾게된다. 하지만 실제로는 가장 큰 숫자는 12가 아닌 99이다. 이처럼 단계마다 한 선택은 최적이지만 막상 최종적(전역적)인 해답을 보면 최적 해답이 아니다.
그리디 알고리즘의 조건 및 사용 이유
그리디 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(Greedy choice property)과 최적 부분 구조 조건(Optimal substructure)이라는 두 가지 조건이 만족된다.
- 탐욕스런 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것
- 최적 부분 구조 조건 : 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것
위의 조건들을 성립하지 않으면 그리디 알고리즘은 최적해를 구하지 못한다. 그럼에도 불구하고 그리디 알고리즘은 빠르고 종종 최적에 대한 좋은 근사치를 찾기 때문에 유용하다. 또한 네트워크 라우팅에서도 쓰인다.
DP(Dynamic Programming)
DP는 동적 계획법이라는 뜻으로 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최종적인 목적에 도달하는 방법이다.
DP의 특징과 쓰임새
각 하위의 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. (쉽게 말해 한 번 계산한 것은 또 할 필요가 없다는 소리다.) 이러한 방법으로 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
그래서 DP는 주로 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 또한 피보나치 수열에도 쓰인다.
피보나치 수열
function f(n)
if n = 0
return 0
else if n = 1
return 1
else
return f(n-1) + f(n-2)여기서 f(5)를 구해보자.
f(5)
f(4) + f(3)
(f(3) + f(2)) + (f(2) + f(1))
((f(2) + f(1)) + (f(1) + f(0))) + ((f(1) + f(0)) + f(1))
(((f(1) + f(0)) + f(1)) + (f(1) + f(0))) + ((f(1) + f(0)) + f(1))여기서 세 번째 줄의 f(2)가 중복되어 계산되고, 이것이 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수함수가 된다.
이걸 각 함수의 계산값을 저장하는 객체 x를 추가하면 이 알고리즘은 다음과 같이 바뀐다.
var x = {
0 : 1,
1 : 1
} function f(n)
if (!x[n]) {
x[n] = f(n-1) + f(n-2);
}
return x[n];이렇게 각 계산값을 저장하면, 중복 계산이 줄고 시간 복잡도는 이다.
그리디 vs DP
DP는 가능한 모든 방법을 고려해야 한다는 단점이 있다. 이러한 단점을 극복하기 위해 그리디 알고리즘이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증 되었다.
우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 가정 해보자. 여기서 DP를 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 반면 그리디 알고리즘은 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다. 물론 DP로 경로를 검색하는 동안 우리가 운전을 잠깐 쉬어야 하듯이, 약간의 시간이 걸린다는 단점이 있다. 하지만 이렇게 얻어낸 경로는 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다. 반면 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다. 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 즉, DP는 그리디에 비해 시간적으로 효율적이지는 못하지만 결과에 대해서는 효율적인 값을 구할 수 있다.
Reference
