메모이제이션

 

목차
1. 메모이제이션이란?
2. 메모이제이션을 사용한 피보나치

1. 메모이제이션이란?

• 동일한 계산을 할 경우 이전에 계산된 결과를 객체를 통해 메모리에 저장시켜 성능을 개선시키는 프로그래밍 기술

 

2. 메모이제이션을 사용한 피보나치

피보나치는 이전의 값과 현재 값의 합이 다음 번째 결과가 되기를 인덱스가 증가하면서 반복하는 수열을 말한다.

이전의 값 => 1
현재의 값 => 1
다음의 값 => 2
1 1 2 3  5 8 13 18 ...

1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8

이러한 피보나치 수열을 재귀함수를 통해 구현할 수 있는데 문제는 수가 커질수록 반복하는 연산이 많아져 메모리를 많이 사용하게 되어 인덱스가 커질수록 시간이 느려지고 프로그램이 멈출 수 있다. 

 

1) 피보나치 구현

function fibo(n) {
        if (n === 1 || n === 2) return 1;
        return fibo(n - 1) + fibo(n - 2);
}

재귀함수를 통해 피보나치 수열을 구현했다. 25번 반복연산한다고 가정했을 때 동작이 완료되는데 약 4초의 시간이 걸렸다. 이는 컴퓨터의 성능이나 상황에 따라 조금씩 날라질 수 있다. 하지만 이는 조금 오래 걸린거 같다. 그 이유는 이전에 수행했던 연산을 재귀를 통해 다시 연산들을 다시 하기 때문이다. 이러한 비효율적인 연산을 줄이기 위해 메모이제이션 기법을 사용한다. 

 

2) 메모이제이션을 통한 피보나치 구현

let memo = {};
function fibo2(n) {
    let result;
    //한번 연산이 된 상태인지 확인
    if (n in memo) {
        result = memo[n];
    } else {
        if (n === 1 || n === 2) {
            result = 1;
        } else {
            result = fibo2(n - 1) + fibo2(n - 2);
        }
        //다음번에 연산을 하지 않게 하기 위해서 상태값을 저장
        memo[n] = result;
    }
    return result;
}

이전과 같이 재귀함수를 사용하지만 객체에 연산의 결과를 저장함으로써 재연산을 하지않아 같은 결과를 출력하지만 실행되는 시간은 확연히 줄어들게 된다. 

 

 

 

참조

https://d2.naver.com/helloworld/9223303