왜 다이나믹 프로그래밍이 다이나믹 프로그래밍 인 줄 아십니까...?
1. 문제의 발단.
그렇다. 이유는 없다. 멋있어서 붙여진 이름이라고 한다. 그러니 나처럼 왜 다이내믹 이냐?라는 의문을 품고 이유를 찾게 되면 전혀 없으니 다른 방식으로 이해를 해 보려고 한다.
2. 기본 원리
- 큰 하나의 문제를 위해 그 문제를 새부적인 문제들로 나눠서 이전에 작은 문제를 풀었던 답을 이용해 다음에 나올 문제를 풀고, 마지막에 그 결과들을 합쳐서 큰 문제 하나의 답을 도출 해 낸다.
- 이때, 작은 문제들의 결과를 계속 이용하기 위해 따로 그들을 저장해 놓는다.
- 이는 재귀함수를 이용할 때 사용했던 메모이제이션(Memoization)을 이용하는 것과 같다.
3. 언제 사용하나요?
- 큰 문제를 작은 문제들로 나눠서 생각할 수 있는경우
- 같은 문제를 구할 때, 계속 구할 때마다 답은 같은 경우
4. 다시 돌아온 피보나치
- 피보나치수열을 이용해 알아보자
- 피보나치수열의 경우 계속해서 자신이 구했던 값들을 다시 계산해서 그 자리 위치를 맞추어 계산하게 된다.
- 하지만 이전에 이미 계산한 수를 저장했다가 다시 사용하면 효율을 굉장히 올릴 수 있다.
const fibo = (n, arr = [0]) => {
// 처음 3 보다 작으면 무조건 1이다.
if(n < 3) {
arr[n] = 1;
}
// arr에 작게 나눈 문제들의 답(각각의 이전 fibo의 결과들)이 들어가 있다.
// 만약 찾을 수 없다면?
if(!arr[n]) {
// 계산해서 arr에 넣어준다.
arr[n] = fibo(n - 1) + fibo(n - 2)
}
return arr[n]
}