피보나치 수열에 대해 코드로 구현할려면 반복문을 이용한 방법과 재귀함수를 이용한 방법 등등 나눠져있다.

function fibonachi(n) {

	if(n === 0) {
		return 0
	} else if(n === 1) {
		return 1
	} 
  
 	return fibonachi(n - 2) + fibonachi(n - 1) 

}

위의 피보나치 로직은 재귀함수로 구현하였는데 숫자를 크게 잡은 경우 콘솔창이

먹통되는 현상을 경험했을 것이다.

대략 n이 30에 근접할 때부터 출력 로딩이 길어지는데, 도대체 왜 이런 현상이 발생할까?

그 이유를 알기 위해 트리 구조로 해당 코드를 세분화 해보았다.

fibonachi(n) n이 4일 경우 위의 그림과 같은 트리 구조가 형성된다.

(분홍색 밑줄이 총 3개이므로 3이 출력)

만일 극단적으로 n이 100이라면 복잡한 트리 구조가 형성되고 너무 비효율적인 스택이 쌓여있는 셈이다.

컴퓨터가 아무리 성능이 좋아도 스택이 수도 없이 쌓여있으면 로직을 계산하는데 있어 한계가 있다.

위와 같은 문제를 해결하기 위해 있는 것이 바로 동적계획법(Dynamic Programming)이다.

동적계획법

동적계획법 (Dynamic Programming)
저장한 값들을 재활용해서 사용하는 알고리즘

메모이제이션(Memoization)
사용했던 계산이 필요한 순간마다 계산하여 저장

즉 동적계획법 안에 메모이제이션이라는 알고리즘 철학이 포함되어 있다고 보면 좋다.

지금부터 메모이제이션 특징을 살려 피보나치 수열의 비효율적 로직을 해결해보자.

메모이제이션을 통한 피보나치 수열

function fibonachi(n) {

	let memo = [0, 1]
    
    let fibo = () => {
		if(memo[n] !== undefined) {
			return memo[n]
		}
     	memo[n] = fibo(n - 2) + fibo(n - 1) 
     	return memo[n]
	}

	return fibo()
}

위의 코드로 n의 값을 100, 200 1000 큰 수를 선언하여도 평균 시간 복잡도 O(Nlog2N)에

상당히 빠른 속도로 결과를 출력한다.

녹색 메모 상자는 로직이 돌면서 계산된 결과를 메모에 저장하면서 이는 메모이제이션 철학에 따라

다음 높은 숫자를 불러와도 재활용하듯 쉽게 풀어낼 수 있다.

쉽게 생각하자면 위의 방식처럼 2번째 이전의 값과 1번째 이전의 값이 저장되어 있는 관계로

바로 합을 구하여 풀어낼 수 있게 된다.