👀 memoization이란?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.

출처: 위키백과

🕸 Fibonacci Numbers (by JS)

피보나치 수열을 재귀적으로 구현했을 때 수를 구할 때마다 함수가 호출되므로 수가 커지면 실행속도가 느려지는 문제가 있다. 다음과 같이 이미 구한 수는 배열에 저장해두고 다음 수를 구할 때 메모리에서 찾아 리턴하게 되면(memoization) 실행 속도를 O(n)까지 단축할 수 있다!

let numbers = [];
function fibo(n) {
    if(numbers[n] > 0) {
        return numbers[n];  //이미 구한 수는 재귀호출 없이 저장된 값 리턴(memoization)
    }else if(n === 1|| n === 2) {
        return numbers[n] = 1;
    }else {
        return numbers[n] = fibo(n - 2) + fibo(n - 1); 
    }
}