다이나믹 프로그래밍

다이나믹 프로그래밍?

최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 연산 속도에 한계가 있고, 메모리 공간을 최대한 활용 할 수 있는 효율적인 알고리즘을 작성해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 시킬 수 있는 방법이 있는데 해당 방법 중에 하나가 다이나믹 프로그래밍이다. 

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열을 해석하면 다음과 같다.

• n번째 피보나치 수 = ( n - 1 )번째 피보나치 수 + ( n - 2 )번째 피보나치 수 
• 단, 1번째 피보나치 수 = 1 , 2번째 피보나치 수 = 1

public int fibo(int x){
 	if(x==1 || x==2)
      return 1;
  return fibo(x-1) + fibo(x-2)
}

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 이러한 점화식을 표현하면서 반복해서 메서드 호출을 하는데 f(1), f(2) 이면 재귀 종료 조건을 성립하여 재귀를 하지 않는다. 하지만 해당 코드를 작성하면 문제가 생긴다. n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.

그림을 보면 동일 함수가 반복 호출되는 것을 확인할 수 있다. 이미 계산을 했지만 호출할 때마다 계산하는 것을 볼 수 있다. n이 커질 수록 반복해서 호출하는 경우는 늘어난다. 점화식을 재귀 함수를 사용해 만들 수는 있지만, 효율적으로 해결할 수는 없다. 이러한 것을 해결하기 위해 다이나믹 프로그래밍을 사용하지만 다음 조건을 만족할 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있는 경우
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일한 경우

피보나치 수열에서는 메모이제이션이라는 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 실제 메모이제이션의 구현은 이미 구한 답을 배열이나 리스트에서 가져오면 된다. 다음과 같이 구현할 수 있다.

import java.util.*;

public class 피보나치_DP {
    static int[] arr = new int[100];
    static int cnt = 0;
    public static void main(String[] args) {
        Arrays.fill(arr, 0);
        arr[0] = 1;
        arr[1] = 1;
        fibo(30);
        System.out.println(cnt);
    }

    private static int fibo(int x) {
        if (x == 1 || x == 2) return arr[x];
//      	if (arr[x] != 0) return arr[x];

        cnt += 1;
        arr[x] = fibo(x - 1) + fibo(x - 2);
        return arr[x];
    }
}

일반 재귀의 경우 cnt 값은 832039이 된다. 하지만 주석 처리된 부분을 풀면 cnt 값은 28이 된다. 엄청난 차이 이다. 정리하면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 즉, 이미 해결한 문제는 다시 해결할 필요가 없다는 것을 알려주는 것이다. 

다이나믹 프로그래밍을 적용했을 때 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다. 한 번 구한 결과는 다시 구해지지 않기 때문에 위와 같은 결과를 나타낼 수 있다. 

이러한 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 한다. 반면 단순 반복문을 이용해 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출 한다고 하여 바텀 업 방식이라고도 한다.