동적계획법이란
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
원리
일반적으로 주어진 문제를 풀기 위해서,
문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음,
그것을 결합하여 최종적인 목적에 도달하는 것이다.
각 하위 문제의 해결을 계산한 뒤,
그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.
동적 계획법과 그리디 알고리즘의 차이
차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자.
이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다.
반면, 그리디 알고리즘은 전체적인 상황을 고려하지 않고 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다.
동적 계획법을 사용하면 약간의 시간이 걸린다는 단점이 있다.
그러나 이렇게 얻어낸 경로는 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다.
반면, 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다.
각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다.
즉, 동적 계획법은 그리디 알고리즘에 비해 시간적으로는 효율적이지 못할 수는 있어도, 그 결과에 대해서는 효과적인 값을 구할 수 있다.
피보나치 수열
function fib(n)
if n = 0
return 0;
else if n = 1
return 1;
else
return fib(n-1) + fib(n-2)
보통 피보나치 수열을 구하는 함수는 이렇다.
예로, fib(5)를 구하려면
- fib(4) + fib(3)
- (fib(3) + fib(2)) + (fib(2) + fib(1))
- ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
fib(2)가 3번이나 중복되어 계산되고,
이것은 전체적인 계산 속도를 떨어뜨린다.
이 알고리즘의 시간복잡도는 지수 함수가 된다.
여기에서 각 함수의 계산값을 저장하는 객체를 하나 생성해주면
arr[n] <- initalize 0
arr[0] = 0;
arr[1] = 1;
fib_Dynamic(n){
if(!arr[n]){
arr[n] = fib_Dynamic(n-1) + fib_Dynamic(n-2);
}
return arr[n];
}
각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.
피보나치는 반복 알고리즘으로도 구할 수 있다.
arr[n] <- initalize 0
arr[0] = 0;
arr[1] = 1;
fib_While(n)
for i<-2 to n
arr[i] = arr[i-1] + arr[i-2];
return arr[n-1] + arr[n-2];
