Dynamic Programming, DP
동적 계획법이라고도 한다.
주어진 문제를 여러 개의 하위 문제(subproblem)으로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 방법이다.
하위 문제에서 해결한 해결책을 저장한 후에(Memoization), 같은 하위 문제가 나왔을때 그것을 이용한다. 이를 통해 계산 횟수를 줄일 수 있다(중복 계산 방지). 하위 문제의 수가 기하급수적으로 증가할때 유용하다.
답을 구하기 위해 했던 계산을 또 해야 하는 종류의 문제 구조를 최적 부분 구조(Optimal Substructure)라고 한다. DP는 이런 문제에서 효과를 낸다.
‘기억하며 풀기’ 라고 이해해도 된다.
DP를 사용할 수 있는 경우
대부분의 문제에는 DP를 사용할 수 없다. 아주 적은 문제들은 DP를 사용할 수 있는데, DP를 사용하면 성능에 아주 큰 차이가 있다.
DP를 사용할 수 있는지 확인하기 위해서는 두가지를 확인해야 한다
- Subproblems하위문제가 있는지
- Optimal substructure최적 부분 구조가 존재하는지
하위문제가 있다는 말은 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능하다는 말이다.
각각의 조각이 다른 모습이면 안된다. 여러번 재사용되어야 한다.
Subproblems 하위문제가 있는가?
피보나치 수열을 구하는 함수를 만들때 다섯번째 수는 네번째 수와 세번째 수를 쓴다. 여기서 세번째 수는 앞에서 이미 계산했던 값이다. 중첩된다. → 사용가능
반대로 합병정렬의 경우 여러개의 작은 조각으로 쪼개기는 하지만, 그것이 중첩되지는 않는다. → 사용불가
이런 구조는 보통 분할 점령 방식으로 해결이 된다.
Optimal substructure 최적 부분 구조가 존재하는가?
최적 부분 구조
하위 문제의 최적 해답을 통해서 더 큰 범주의 문제의 최적 해답을 구성할 수 있는 경우
해당 문제가 최적 부분 구조를 가진다고 한다.
피보나치 수들은 해당이 된다. 다섯번째 피보나치 수를 찾으려면 네번째 피보나치 수와 세번째 피보나치 수를 더해야 하니까.
또한 그래프에서 최단 경로를 찾는 문제에서
A → D로 가는 최적의 해답은 A → C로 가는 최적의 해답을 가지고 구성할 수 있다.
C로 가는 최적의 해답은 B로 가는 최적의 해답으로 구할수 있다.
시작지점에서 목적지로 가는 최단경로에는 해당 경로 위에 있는 한 지점에 대해 그 경로가 최단 거리이다.
이것이 바로 최적 부분 구조.
피보나치 함수 : 재귀를 사용하는 naive한 방법
재귀만 사용한 버전
function fib(n) {
if(n <= 2) return 1;
return fib(n-1) + fib(n-2);
}피보나치 수열을 재귀로만 구현했을때 빅오는 O(2^N)이다. 그야말로 1씩 늘어날때마다 기하급수적으로 커진다.
정말 좋지 않은 방식이다. 매우 느리다.
왜 느린가? → 중복으로 계산하기 때문
fib(5)를 예로 들면, 위에 이미지에서 fib(4) 밑에 있는 fib(3)을 계산하고, fib(5)밑에 있는 fib(3)을 또 계산한다. 이미 계산해서 값을 알고 있는데도 중복으로 또 계산하는 것이다. fib(100)만 되어도 중복 계산은 기하급수적으로 많아져 속도 차이가 매우 크게 난다.
💡 **앞에서 계산한 값을 저장해놨다가 중복 계산 안하면 되겠네?**→ 이게 바로 동적 프로그래밍의 핵심이다.
Memoization 메모이제이션
앞에서 계산한 값을 저장해놓는 법
배열이나 객체로 데이터를 저장할 구조를 만들고, 이미 계산한 값들을 저장한 후,
다음 번에 계산을 할때, 테이블을 확인해서 이미 들어있는 값이 있나 확인.
값이 있으면 그걸 사용한다.
이미 풀었다는 것을 기억한다면 그걸 가지고 와서 계산을 다시 반복하지 않는다.
function fib(n, memo=[]) {
if(memo[n] !== undefined) return memo[n]
if(n <= 2) return 1;
var res = fib(n-1, memo) + fib(n-2, memo);
memo[n] = res;
return res;
}memo라는 배열의 해당 숫자의 인덱스에 피보나치 수를 저장한다. 이렇게 하면 한번 계산한 값은 다시 계산할 필요가 없다.
Memoization 방법의 시간복잡도 Big-O
메모이제이션을 사용하지 않고 재귀만 사용했을때 시간복잡도는 O(2^n) 이었다. 매우 좋지 않다.
메모이제이션을 사용, 즉 DP를 사용하면 O(n) 이다. 매우 빠른 속도.
- O(2^N)
- O(n)
두 시간복잡도는 하늘과 땅 차이다.
아주 큰 차이가 있다.
코드 상에는 큰 차이가 없는데 성능상으로 이렇게 차이가 커져버린다.
Tabulation 타뷸레이션
메모이제이션이 아닌 DP 방법으로 타뷸레이션이 있다.
메모이제이션이 필요할때 계산하고, 계산한 값을 저장하는 방식이라면 타뷸레이션은 값을 미리 계산해둔다.
앞에서 피보나치 수를 구하는 메모이제이션 방식은 Top-down 방식이었다.
찾으려고 하는 값에서 시작해서 아래로 내려가면서 빈칸을 채우는 방식
반대로 Bottom-up으로 밑에서 시작해서 위로 구하는 방식도 가능하다.
그것이 타뷸레이션
타뷸레이션은 보통 루프와 같이 순환을 통해 작업을 한다. 밑에서부터 시작을 해서 하위문제를 풀고 그 결과를 테이블에 저장한다.
function fib(n) {
if(n <= 2) return 1;
var fibNums = [0,1,1];
for(var i = 3; i <= n; i++) {
fibNums[i] = fibNums[i-1] + fibNums[i-2];
}
return fibNums[n];
}재귀를 사용하지 않고 맨 앞에 피보나치 수의 처음 0,1,1를 넣어두고 시작한다.
이렇게 하면 fibNums 배열이 앞에서부터 차례대로 채워진다. → 상향식!
타뷸레이션의 장점은 배열 하나만 사용하기 때문에 스택 오버플로우가 일어날 일이 없다.
메모이제이션은 그래도 재귀를 사용하기 때문에 fib(10000)정도 되면 스택 오버플로우가 일어난다.
콜스택이 엄청나게 쌓이는 것.
그에비해 타뷸레이션은 배열 하나에 값만 계속 추가되니 빠른데다 공간도 적게 써서 스택오버플로우도 일어나지 않는다.
코드도 직관적. 루프 하나만 사용.
시간복잡도는 둘다 O(n)이다.
