Greedy Algorithms(탐욕법, 탐욕 알고리즘)
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란
"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"
라는 모토를 가지는 알고리즘 설계 기법이다.
예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.
단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.
탐욕스러운 선택 조건(Greedy choice property)
최적 부분 구조 조건(Optimal Substructure)
위의 조건이 성립되어야 잘 작동한다.
<탐욕스러운 선택 조건 (Greedy choice property)>
앞의 선택이 이후의 선택에 영향을 주지 않는 조건.
<최적 부분 구조 조건(Optimal Substructure)>
문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다는 조건.
Dynamic Programming (동적 계획법)
Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 길이 막힐 때 돌아가는 길로 가는 것이 더 빠르게 도착한다는 사실을 알고 있다면 같은 상황에서 돌아가는 길을 계속 선택한다. 그럼 결국 최적의 경로를 찾게 된다.
다시 말하면 최종 문제를 해결하는 많은 방법들을 모두 탐색하게 된다. 하위 문제들 각각의 해결 방법들을 모두 탐색하기 때문이다. 하지만, 반복되는 하위 문제를 찾아 간단히 해결하도록 만드는 것으로 계산 횟수를 줄일 수 있다.
Dynamic programming의 대표적인 예시는 피보나치 수열이다.
여기서 n번째 있는 수를 찾는 함수는
function fn (n) {
if (n === 0) {
return 1;
} else if (n === 1) {
return 1;
} else {
return fn(n-1) + fn(n-2);
}그런데 한가지 문제가 생긴다. fn(2)는 이미 계산이 되어 알고 있는데 계속 결과를 구하는 과정이 반복이 된다. 숫자가 커질 수록 이런 중복 계산은 기하급수적으로 많아질 것이다. 이를 해결하기 위해 함수가 돌아가면서 새로운 인자를 가진 함수가 실행되면 그 값을 객체에 저장하고, 이미 저장된 함수를 실행하면 그 값을 그냥 가져오자.
var obj = {
0: 1,
1: 1
}
// 부분 함수의 결과 값을 저장하는 obj
// key는 부분 함수의 인자이다.
// value는 fn(key)의 결과이다.위의 객체를 이용한 피보나치 수를 구하는 알고리즘은 다음과 같다.
function fn(n) {
if (!obj[n]) {
obj[n] = fn(n - 1) + fn(n - 2);
}
return obj[n];
}함수의 결과 값을 저장하면서 최종 결과물을 찾는 함수이다. 이러한 방식으로 계산 횟수를 줄이면서 전체 값을 모두 탐색할 수 있다.
