탐욕 알고리즘과 함께 언급되는 Dynamic Programming (동적 계획법)
탐욕 알고리즘: 매순간 최적의 방법을 찾음
DP: 모든 경우의 수를 조합해 문제 해결
DP의 문제 해결 과정
1) 주어진 문제를 하위 문제 Sub problem으로 나눈다
2) 하위 문제의 해결 방법을 결합하여 문제를 해결한다
DP의 조건
- 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems)
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)
function fib(n) {
if(n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...위 Fibonaci 문제 해결 방식도 DP와 같다.
1) Overlapping Sub-problems
fid(7)을 해결하려면 fib(5)와 fib(6)의 값이 필요하다. 각각의 값을 다시 하위 문제로 나누어 찾을 수 있는데, 이 때 fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번이 반복해서 사용된다.
2) Optimal Substructure
하위 문제에서 해결한 값을 상위 문제에서 쓰이게 된다.
Recursion + Memoization
function fibMemo(n, memo = []) {
// 이미 해결한 하위 문제인지 찾아본다
if(memo[n] !== undefined) return memo[n];
if(n <= 2) return 1;
// 없다면 재귀로 결괏값을 도출하여 res 에 할당
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
memo[n] = res;
return res;
}재귀를 활용하여 상위 문제에서 하위 문제(Top-Down)로 값을 찾아가는 여정을 가진다. base case에 도달하면서 memo라는 배열에 값을 추가해 나간다.
단순 재귀가 아닌 Memoization 방법을 활용함으로써, 시간 복잡도를 O(2^n)에서 O(n)으로 줄일 수 있다.
Iteration + Tabulation
function fibTab(n) {
if(n <= 2) return 1;
let fibNum = [0, 1, 1];
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}재귀와 Memoization 방식과 달리 인수 n의 값까지의 for문을 돌려 배열에 입력해 나가고 해당 인수에 해당하는 배열의 값을 조회하는 방식이다. 문제를 하위 문제로 나눈 것은 맞으나, 값의 탐색이 가장 아래에서부터 위로 향하고 있기에 Bottom-Up 방식이라고 한다.
두 방법 모두 효과적인 시간복잡도를 가지지만, 재귀와 같은 방법은 call stack의 overflow를 야기할 수 있는 단점이 있다. 큰 값을 찾는 식이 stack에서 쌓이고 차례대로 stack이 쌓이게 된다.
