메모이제이션과 타뷸레이션

📌 DP(Dynamic Programming, 동적 계획법)이란

 

문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘

 

🔎 풀이 방법

 

✔ 타뷸레이션(Tabulation)

 

작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법

 

예제: 피보나치 수열

 

import java.io.IOException;

public class Main {

    static int[] A;

    public static void main(String[] args) throws IOException {
        int N = readInt();
        A = new int[N + 1];

        fibonacci(N);
        for (int i = 1; i <= N; i++) System.out.print(A[i]+ " ");
    }

    static int fibonacci(int n) {
        if (n <= 2) return A[n] = 1; //첫 두 수는 1로 시작
        return A[n] = fibonacci(n - 1) + fibonacci(n - 2); //피보나치 생성
    }

    //입력
    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

위 코드처럼 앞에 생성된 결과를 이용하여 뒤에 생성될 피보나치 수를 만들어 간다.

 

수행 결과

 

만약, n을 45라는 큰 수로 하면 아래처럼 결과를 즉시 보기 힘들 정도로 시간이 소요되는 것을 볼 수 있다.

 

소요 시간: 6.419s (나머지 숫자 생략)

 

✔ 메모이제이션(Memoization)

 

재귀 과정에서 이미 계산된 값을 다시 계산해야 할 때, 이미 계산된 값을 재활용하는 방법

 

예제: 피보나치 수열

 

import java.io.IOException;

public class Main {

    static int[] A;

    public static void main(String[] args) throws IOException {
        int N = readInt();
        A = new int[N + 1];

        fibonacci(N); //단 1회 호출
        for (int i = 1; i <= N; i++) System.out.print(A[i]+ " ");
    }

    static int fibonacci(int n) {
        if (n <= 2) return A[n] = 1;
        if (A[n] > 0) return A[n]; //이미 계산된 값을 다시 계산하지 않음
        return A[n] = fibonacci(n - 1) + fibonacci(n - 2); //피보나치 생성
    }

    //입력
    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

위 코드처럼 배열의 값이 0이 아니라면 이미 계산된 상태이므로 다시 계산하지 않는다.

 

소요 시간: 0.009s (나머지 숫자 생략)

 

결과적으로 소요 시간이 크게 줄어든 것을 볼 수 있다.

 

Reference: