동적프로그래밍

🤓오늘의 공부 주제: 동적프로그래밍🤓

메모이제이션(Memoization)

메모이제이션이란?
계산 결과를 저장해서 여러번 계산하지 않도록 하는 것.

재귀를 사용할 경우 콜스택에 계속 쌓이고 성능 문제가 있음.
피보나치 수열과 같은 하향식 문제에서 중복된 계산이 성능에 많은 영향을 끼침. 계산 결과를 저장해서 여러번 계산하지 않도록 하는 것.

빠른 데이터 탐색, 삽입, 삭제가 가능한 해시테이블을 사용하여 구현.
계산결과를 기억하기 위한 변수 memo. 검색해서 없으면 저장하고 있으면 저장된 값을 리턴.

재귀함수로 구현한 피보나치 함수는 O(n^2)의 성능.
메모이제이션을 활용한 피보나치2 함수는 O(n)의 성능.

그러나, 메모이제이션은 속도를 위해서 메모리(공간)을 사용.

💡요약💡
장점: 속도가 빠름.

단점: 메모리 공간을 많이 차지함.

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

function fibonacci2(n, memo){
    if(n == 0 || n == 1) return n;

    if(memo[n] == null){
        memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    }

    return memo[n];
}

let start = new Date();
console.log(fibonacci1(40));
let end = new Date();
console.log(`fibonacci1 함수 실행시간: ${end - start}ms`);


start = new Date();
console.log(fibonacci2(40, {}));
end = new Date();
console.log(`fibonacci2 함수 실행시간: ${end - start}ms`);

타뷸레이션(Tabulation)

타뷸레이션이란?
상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해둠.

메모이제이션은 재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결. 중복 계산을 하지 않아서 속도가 빠름. 그러나 여전히 재귀를 사용하기 때문에 함수 하나를 호출하는 것보다 오버헤드가 더 큼.

반면, 타뷸레이션은 메모이제이션과 비교 시 메모리 공간을 덜 차지함.

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

function fibonacci2(n, memo){
    if(n == 0 || n == 1) return n;

    if(memo[n] == null){
        memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    }

    return memo[n];
}

function fibonacci3(n){
    if(n <= 1) return n;

    let table = [0, 1];

    for(let i = 2; i <= n; i++){
        table[i] = table[i - 2] + table[i - 1];
    }

    return table[n];
}

let start = new Date();
console.log(fibonacci1(40));
let end = new Date();
console.log(`fibonacci1 함수 실행시간: ${end - start}ms`);


start = new Date();
console.log(fibonacci2(40, {}));
end = new Date();
console.log(`fibonacci2 함수 실행시간: ${end - start}ms`);

start = new Date();
console.log(fibonacci3(40));
end = new Date();
console.log(`fibonacci3 함수 실행시간: ${end - start}ms`);