동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

• 한 번 계산한 문제는 다시 계산하지 않게 하는 방식으로, 같은 계산을 여러 번 하는 상황을 개선하여 효율을 높이는 알고리즘이다. 
• 이 때, 한 번 계산한 문제의 답을 저장해두는 메모이제이션(Memoization) 기법이 사용된다.
• Top-Down 방식은 재귀, Bottom-Up방식은 반복문을 사용한다.

동적 계획법 사용 조건

1. 동일한 작은 문제들이 반복하여 나타나야 한다.
2. 동일한 문제는 항상 답이 동일해야 한다.

동적계획법을 이용하는 백준 문제 (피보나치 함수)

1003번: 피보나치 함수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] count = new int[41][2];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        count[0][0] = 1;
        count[1][1] = 1;

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(bf.readLine());
            System.out.print(fibonacci(num)[0] + " " + fibonacci(num)[1] + "\n");
        }
    }

    public static int[] fibonacci(int n) {
        if (count[n][0] == 0 && count[n][1] == 0) {
            count[n][0] = fibonacci(n-1)[0] + fibonacci(n-2)[0];
            count[n][1] = fibonacci(n-1)[1] + fibonacci(n-2)[1];
        }

        return count[n];
    }
}

피보나치 수열은 같은 계산을 여러 번 하는 대표적인 문제이다.

5번째 피보나치 수열을 구하는 과정은 다음과 같다.

 

f(5)

= f(4) + f(3)

= f(3) + f(2) + f(2) + f(1)

= f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + 1

= f(1) + f(0) + 1 + 1 + 0 + 1 + 0 + 1

= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

= 5

 

똑같은 계산이 몇 번이나 수행되는 것을 알 수 있다.

따라서, 문제에 대한 정답을 저장해 둘 배열(Memoization)을 미리 만들고, 계산할 때 배열에 정답이 있다면 그대로 가져다 쓰고, 정답이 없다면 새로 계산하여 저장하는 방식으로 구현한다.

위 코드에서는 count배열이 정답을 저장해두는 배열(Memoization)이다.

해당 문제에서는 n이 40이하의 수로만 주어진다고 했기 때문에 배열의 크기를 41로 정하였다.