[알고리즘] 메모이제이션

메모이제이션(memoinzation)

- 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해서 프로그램 실행 속도를 빠르게 하는 기술이다.

- 동적 계획법에서 사용되는 기술이다.

- 피보나치 재귀에서 모든 값을 DFS 함수를 거치게 되면, 중복되는 값들도 계산하게 되어 스택 메모리 낭비가 되는 문제점과 시간이 오래 걸린다.

 

 

배열에 DFS(n) 값들을 저장해서 개선하는 방법

public class Solution {
    static int[] fibo; // 배열에 저장해서 개선하는 방법
    public static int DFS(int n){
        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]=1;
        else return fibo[n] = DFS(n-2)+DFS(n-1);
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int n = 15;
        fibo = new int[n+1]; // 0번 인덱스 필요없이 1~10번
        T.DFS(n); // 한 번 돌리고 값들을 배열에 저장해준다.
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" "); // fibo만 출력
    }
}

 

메모제이션을 사용해서 개선하는 방법

- if(fibo[n]>0) return fibo[n] 을 추가해줘서 바로 return

public class Solution {
    static int[] fibo; // 배열에 저장해서 개선하는 방법
    public static int DFS(int n){
        if(fibo[n]>0) return fibo[n]; // 0보다 크다는건 그 값이 이미 있다는 뜻
        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]=1;
        else return fibo[n] = DFS(n-2)+DFS(n-1);
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int n = 45;
        fibo = new int[n+1]; // 0번 인덱스 필요없이 1~10번
        T.DFS(n); // 한 번 돌리고 값들을 배열에 저장해준다.
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" "); // fibo만 출력
    }
}