[JAVA]동적 계획법

개념

동적 계획법이란 같은 계산을 여러 번 하지 않기 위해 사용하는 방법이다.

그러기 위해 이미 계산된 값의 결과를 저장해 두고, 해당 계산을 또 해야 할 경우 계산하지 않고 결과를 가져다 쓰는 방법이다.

 

동적 계획법을 사용하면 좋은 예시로 피보나치 수열이 있다.

피보나치 수열이란, 첫째 항과 둘째 항이 1이고, 셋째 항부터는 앞의 두 항의 합을 값으로 갖는 수열이다.

ex) 1 1 2 3 5 8 13 21 34 55...

 

따라서, 피보나치수열의 n번째 항을 구하는 식은 다음과 같다. * fib(n) : 피보나치수열의 n번째 항

 

fib(n) = fib(n - 2) + fib(n - 1)

 

위 식을 이용하여 n번째 항을 구할 때, 같은 계산을 여러 번 해야 하는 문제가 발생한다.

 

Ex) 피보나치수열의 5번째 항 구하기

1. fib(5) = fib(3) + fib(4) 이므로, 3번째 항과 4번째 항을 구해야 한다.

2-1. 3번째 항 구하기 : fib(3) = fib(1) + fib(2) = 1 + 1 = 2

2-2. 4번째 항 구하기 : fib(4) = fib(2) + fib(3) = 1 + fib(1) + fib(2) = 1 + 1 + 1 = 3

따라서 fib(5) = 2 + 3 = 5이다.

 

위 방법에서 fib(1)은 2번, fib(2)는 3번, fib(3)은 2번, fib(4)는 1번 이용되었다.

100번째 항을 구한다고 하면 같은 계산을 기하급수적으로 많이 하게 될 것이다.

 

이를 방지하기 위해 각 항의 값이 계산될 때 그 값을 저장해 놓고, 필요할 때 가져다 쓰는 것이 동적 계획법이다.

 

예시 코드

실행 후 숫자 1개(N)를 입력하면 피보나치수열의 N번째 항을 계산한다.

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

public class Main {
    static int[] val;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        val = new int[N + 1];
        val[1] = val[2] = 1; // 1번째, 2번째 항의 값을 1로 설정

        int result = fib(N);
        System.out.println(result);
    }
    public static int fib(int N) {
        if(val[N] != 0) return val[N]; // N번째 항의 값을 이미 계산했을 경우, 저장되어있던 값을 리턴
        else {
            val[N] = fib(N - 2) + fib(N - 1); // 계산이 안되어있을 경우, 계산
            return val[N];
        }
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
제가 이해한 내용을 간단히 요약하여 기록해 두고, 기억이 나지 않을 때마다 찾아보려는 목적으로 작성하는 글입니다.
따라서 설명이 부족할 수 있으니 양해 부탁드리고, 궁금한 부분이 있으시면 자유롭게 댓글 남겨주세요!