일반적으로 상당 수의 분할 정복 기법은 동일한 문제를 다시 푸는 단점이 있습니다. 이는 단순 분할 정복 으로 풀게 되면 심각한 비효율성을 낳습니다.
피보나치 수열을 예를 들어서 보면 피보나치는 1,1,2,3,5, ...
의 수를 이루게 됩니다. 즉 다음수열값 = 이전 수열 + 두단계 전 수열의 합입니다.
피보나치 수열의 5번째를 구하기 위해서는 3번째와 4번째의 값이 필요합니다. 그리고 4번째 값을 구하기 위해서는 2번째, 3번째 값이 필요합니다. 이와 같은 경우에 5번째 값을 구하기 위해서 3번째 값이 필요하고 4번째의 값을 구하기 위해서도 3번째 값이 필요한 것을 알 수 있습니다
피보나치 수열의 경우 첫번째, 두번째 수열은 1로 고정이기때문에 3번째 수열의 값은 언제나 3입니다. 또 4번째 수열은 2번째, 3번째 값을 구하므로 정답이 같다는 사실을 알 수 있습니다.
하기와 같이 출력하여도 문제는 없으나, 피보나치 수가 늘어날수록 컴퓨터에서 함수를 호출하는 횟수가 2의 n제곱이 되므로 메모이제이션이 사용되어야합니다.
function getFibonacci(n){
if(n<=2){
return 1;
}
else{
return getFibonacci(n-1) + getFibonacci(n-2);
}
}
console.log(getFibonacci(5))
하기와 같이 코드 구현시 이미 계산된 결과의 경우 배열 arr에 저장되기 때문에 한 번 구한 값을 다시 구하는 일이 없습니다.
let arr = [0];
function getFibonacci(n){
if (n<=2){
return 1;
}
if(!arr[n]){ // 내가 저장한 값 중에 없다면...
arr[n] = getFibonacci(n-1) + getFibonacci(n-2);
}
return arr[n];
}
console.log(getFibonacci(5));