LRU,동적계획법,메모이제이션

LRU(Least Recently Used)

가장 오랫동안 참조되지 않은 페이지를 교체하는 방식

 

동적계획법(Dynamic Programming)

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

Top-down:상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여  하위 문제를 해결함으로써 상위 문제를 해결하는 방식

bottom-up:하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식

 

메모이제이션(Memoization)

기존의 정보를 저장함으로써 같은 입력값에 대해 함수가 한번만 실행하게 됨

 

static int fibo(int x) {
    if( x ==1 || x==2) return 1;
    return fibo(x-1) + fibo(x-2);
}

 재귀함수를 이용한 피보나치 수열

static int fibo(int x) {
    if( x ==1 || x==2) return 1;
    if(dp[x] != 0) return dp[x];
    dp[x] = fibo(x-1) + fibo(x-2);
    return dp[x];
}

동적계획법을 이용한 피노나치 수열(Top down)

static int fibo(int x) {
    dp[1] =1;
    dp[2] =1;
    for(int i=3; i<x+1; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[x];
}

동적계획법을 이용한 피노나치 수열(bottom up)