[다이나믹 프로그래밍] Dynamic programming

1. 다이나믹 프로그래밍이란?

 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생할 수 있기 때문에 재귀적 중복을 해결하는 방법이다.

 

 간단하게 말하면 작은 문제들의 값을 저장하여 재사용하는 것이다. 다이나믹 프로그래밍이라는 표기를 보면 큰 연관이 없어보이는데, 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 기억하며 풀기로 번역하였다고 한다.

---

2. 다이나믹 프로그래밍의 예

 다이나믹 프로그래밍의 예로는 피보나치 수열이 있다. 피보나치 수는 다음과 같이 정의할 수 있다.

 

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

 

 n의 피보나치 수에는 n - 1과 n - 2의 피보나치 수를 포함하는 것을 알 수 있다. 이렇게 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 것을 최적 부분 구조 (Optional Substructure)를 가졌다고 말한다. 다이나믹 프로그래밍을 적용하기 위해서는 우선 최적 부분 구조인지 판단해야 한다.

 

 최적 부분 구조를 가진 문제는 재귀호출을 사용하여 문제를 풀 수 있다. 피보나치 수 문제의 경우 재귀호출을 적용한 코드 예 이다.

 

public class Fibonacci {

    public static void main(String[] args) {

        for (int i = 1; i <= 100; i++) {
            System.out.println(fibonacci(i));
        }
    }

    private static int fibonacci(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

 

 최적 부부 구조는 문제의 핵답을 구하기 위해 재귀적인 알고리즘을 사용하는 것이 자연스럽다. 하지만 재귀적 알고리즘은 지수 함수에 비례하는 수행시간이 걸린다. fibonacci(3) 을 구하기 위해서는 fibonacci(2), fibonacci(1)이 각각 한 번씩 나오고, fibonacci(4)의 경우 fibonacci(3), fibonacci(2), fibonacci(1) 이 각각 1번씩 나오게 된다. 문제의 크기가 커져갈 수록 중복 호출 또한 증가하게 된다. 간단한 예로 피보나치 메소드를 수행시킬 때 fibonacci(2)가 나오는 회수를 적어보았다.

 

수행되는 fibonacci(n)	fibonacci(2)가 중복 호출되는 수
fibonacci(2)	1
fibonacci(3)	1
fibonacci(4)	2
fibonacci(5)	3
fibonacci(6)	5
fibonacci(7)	8
fibonacci(8)	13

 

 피보나치 수를 구하기 위한 n 값이 커질수록 기하급수적으로 늘어나는 것을 알 수 있다. 고작 피보나치수 8을 구하기 위해서 중복되는 연산을 수행하는 것이다. 

 

 그렇기 때문에 이렇게 중복하여 호출되는 수들을 특정한 테이블에 저장하여 호출 시에 사용하는 방법, 즉 부분 결과를 저장하면서 해를 구해나가는 과정이 다이나믹 프로그래밍의 핵심이다.

 

 정리하면, 다이나믹 프로그래밍을 적용하기에 적합한 상황은 크게 두 가지이다.

  - 최적 부분 구조를 가진 문제를 해결할 때

  - 재귀적으로 구현했을 때 중복 호출로 인하여 심각한 비효율이 발생한 경우

 

 위 코드를 다이나믹 프로그래밍을 사용하여 작성하였다.

 

public class Fibonacci {

    static long[] dp = new long[51];

    public static void main(String[] args) {

        for (int i = 1; i <= 50; i++) {
            System.out.println(fibonacci(i));
        }
    }

    private static long fibonacci(int n) {

        if (n == 1 || n == 2) {
            dp[n] = 1;
        } else {
            dp[n] = dp[n - 1] + dp[n - 2];
        }

        return dp[n];
    }
}

 

 작은 것부터 차례차례 저장해가며 계산하고 있다. for 루프를 순환하는 것이 수행 시간을 좌우하기 때문에 선형 시간안에 문제가 해결된다.

---

Preferences.

namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

문병로 지음, 쉽게 배우는 알고리즘 개정판 - 한빛아카데미