[Algorithm] Dynamic Programming - 동적 계획법

동적 계획법

 수학적 최적화 방법이자 알고리즘 패러다임입니다. 이 방법은 1950년대 Richard Bellman이 개발하였으며 항공 우주 공학에서 경제학에 이르기까지 수많은 분야에 적용되었습니다.

 두 맥락 모두 복잡한 문제를 재귀적으로 더 간단한 하위 문제로 나누어 단순화하는 것을 말합니다. 일부 결정 문제는 이런 식으로 분해할 수 없지만, 여러 시점에 걸친 결정은 종종 재귀적으로 분해됩니다. 마찬가지로 컴퓨터 과학에서 문제를 하위 문제로 나누고 하위 문제에 대한 최적 솔루션을 재귀적으로 찾는 방식으로 문제를 최적으로 해결할 수 있다면 최적 하위 구조가 있다고 합니다. (출처: 위키디피아)



 위키디피아에서 동적 프로그래밍, 통칭 동적 계획법(약칭 DP)을 위와 같이 설명하고 있다. 이것을 나만의 설명으로 바꿔보자면 하나의 문제를 더 작은 부분 문제로 분할하고, 분할한 더 작은 문제를 더욱 작게 계속 분할한다. 분할된 문제 중 가장 작은 문제를 해결하여 그 상위 문제를 해결하고,  이렇게 상위 문제를 계속 해결하며 결국에는 전체 문제를 해결하는 방식이 동적 계획법이다. 



가장 쉽게 동적 계획법을 알아볼 수 있는 문제를 해결해보자. 백준의 2748번 문제, 피보나치 수 2 문제를 해결해보자.

https://www.acmicpc.net/problem/2748

 

문제는 한번쯤은 들어봤을 피보나치 수에 대한 문제로, n을 입력받아 n번째 피보나치 수를 출력하는 문제이다.

바로 앞의 두 수를 더한 값이 다음 피보나치 수가 되는 것으로 피보나치 수를 나열하면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, ....

그렇다면 이것을 프로그래밍 언어로 어떻게 구현할 수 있을까? 재귀적 방식을 통해 구현해 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        System.out.println(fibo(n));
    }
    public static long fibo(int n) {
        if (n == 0) { return 0; }
        if (n == 1) { return 1; }
        else { return fibo(n-1) + fibo(n-2); }
    }
}

 

먼저 fibo 함수의 반환 타입이 long인데, 이것은 피보나치 수가 뒤로 갈수록 그 값이 매우 커져 int 범위로는 이 문제를 해결 할 수 없으므로 fibo 함수가 long을 반환하도록 하였다.

위와 같이 구현한 피보나치 함수는 n 값에 대해 내부적으로 계속 fibo 함수를 호출시켜 피보나치 수의 값을 구한다.

그런데 위와 같이 코드를 제출하면 시간 초과 결과가 나온다. 어떻게 된 것일까? 

위 코드에서 fibo 함수의 호출 횟수를 알기 위해 cnt 함수를 추가하여 fibo 함수가 얼마나 호출되는지 알아보자.

위와 같이 입력값이 증가할수록 재귀 함수의 호출 횟수가 엄청나게 증가한다.

fibo(5)를 계산하는 경우를 생각해보자. fibo(5) 내부에서는 fibo(3), fibo(4)가 호출되고 fibo(3)에서는 fibo(2), fibo(1)이 호출된다. 호출된 fibo(2)에서는 fibo(0), fibo(1)이 호출된다. fibo(4)에서는 fibo(2), fibo(3)이 호출되고 fibo(2)에서는 fibo(0), fibo(1)이 호출되며, fibo(3)에서는 위에서 호출한 것이 똑같이 호출된다.

 

위 예시에서 fibo(3)과 fibo(2) 함수는 여러 번 반복적으로 호출되고 있는데, 이 반복적인 호출을 없애면 과다한 함수 호출로 인한 성능 저하를 개선할 수 있지 않을까? 이제 아래의 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        long[] arr = new long [91];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i < 91; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        System.out.println(arr[n]);
    }
}

 

 이 코드는 동일 계산을 반복해야 할 때, 이미 계산한 결과를 따로 저장하여 그 값이 필요한 때에만 사용하는 메모이제이션 기법을 사용한 코드이다. 재귀 함수를 사용한 코드와의 차이점을 바로 이해할 수 있다면 좋겠지만 DP 개념이 결코 쉬운 개념이 아니므로 차차 알아가도 좋다. (필자는 PS를 하는 동안 DP와 그리디 개념이 제일 이해하기 어려웠습니다...)

어쨋든 위 코드에서는 재귀적 방식처럼 이미 알고있는 값을 반복적으로 호출하지 않고, 이미 저장해둔 값이 필요하면 그 값을 이용해 다음 피보나치 수를 계산한다.

여기서 동적 계획법의 개념이 사용되는데, 큰 문제(n번째 피보나치 수 구하기)를 작은 문제(이미 알고 있는 피보나치 수를 이용해 다음 피보나치 수 계산)로 쪼개어 해결하고 있다. 위 코드를 제출하면 재귀 함수를 이용한 코드와는 다르게 시간 초과 문제 없이 문제를 해결할 수 있다. 

 

앞에서도 말했듯이 개인적으로 정말 어렵다고 생각하는 개념이기에 다양한 문제를 풀어서 동적 계획법의 개념을 잘 이해하는 것을 추천한다. DP를 응용한 웰 노운 알고리즘 / 문제가 정말 많으므로 잘 알아놓으면 좋을 것이다.