피보나치 수열 2 (Memoization, Dynamic Programming ver)

<피보나치 수열 (Recursive)>

이전 포스팅!

https://m-falcon.tistory.com/84

피보나치 수열

[Memoization 정의]

재귀호출상 반복되는 결과를 메모리에 저장해서 같은 결과를 중복하여 이용하는 횟수를 줄임으로써

성능 향상을 기대하는 코딩 기법.

 

 

지난번 포스팅에서는

재귀함수를 통한 피보나치를 구현했다.

 

n번째 피보나치 수열 값을 구하는

프로그램을

Memoization, Dynamic Programming 기법으로 구현해보자.

 

 

1. Memoization ver

[JavaScript Node.js source code]

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

// 100칸의 배열을 원소 0으로 초기화 var arr = Array.apply(null, new Array(100)).map(Number.prototype.valueOf,0);     function Fibonacci(n){   if(n <= 2){     return 1;   }   else if( arr[n] != 0){ // 0이 아닌 (이미 호출된 자리의 경우 memo된 값을 return)     return arr[n];   }   else { // 0 (아직 값을 구하지 않은 자리는 재귀호출)     return arr[n] = Fibonacci(n-1) + Fibonacci(n-2);   } }   console.log(Fibonacci(10));

 

 

 

결과창 10번째 피보나치 수열 55 출력!

memoization의 핵심은 다음 코드다.

0이 아닌 값이란건 이미 재귀로 값을 구한적이 있다는 뜻이다. arr[n]을 return할 경우 함수를 더 이상 재귀적으로 호출하지 않고 이전에 구한 값을 그대로 리턴한다는 뜻이다.

 

 

 

T(n) TimeComplexity Tree (추후 포스팅 예정)

 

2. Dynamic Programming ver

 

 

1 2 3 4 5 6 7 8 9 10 11 12

ar arr = Array.apply(null, new Array(100)).map(Number.prototype.valueOf,0);   function Fibonacci(n){      arr[1] = arr[2] = 1; // 1, 2번째 숫자는 1로 고정     for(let i = 3; i <= n ; i++){        arr[i] = arr[i-1] + arr[i-2]; // 함수를 호출하지 않고 이미 쓰여진 값을 통해 누적 합     }     return arr[n]; }   console.log('Dynamic Programming Result : ' , Fibonacci(10));

 

Memoization 버전은 else 파트에서만 재귀호출이 일어났는데

Dynamic Programming 버전은 아예 함수호출이 단 한번이다.

 

재귀적으로(이 때 재귀함수 호출이 아니라 알고리즘 자체가 재귀적) 구해진 결과값을 재사용하는 것이다.

표시된 부분이 앞서 구한 피보나치 수열 값을 재사용 하는 파트이다.

 

10번째 피보나치 수 실행 결과창

T(n) TimeComplexity Tree (추후 포스팅 예정)

 

 

3. 관련된 문제풀이

https://m-falcon.tistory.com/153

피보나치 수열 3 (feat. 백준 1003 피보나치 함수)

 

백준 1003번 문제 피보나치 함수문제에 동적 프로그래밍 기법이 적용 된다.