다이나믹 프로그래밍(Dynamic Programming) : 동적계획법

이번에 배워볼 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)이다. 다이나믹 프로그래밍은 알고리즘이라기보다는 문제 해결 패러다임에 가깝다고 할 수 있다.

이게 무슨 말이 나면 이전에 배운 다익스트라를 생각해 보자. 다익스트라는 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다. 다익스트라에서 최단 경로를 어떤 식으로 갱신했는지 기억해보자.

우리는 다익스트라에서 이미 저장된 현재의 최소 비용과 간선을 통한 새로운 비용을 비교해서 최소 비용을 갱신하였다. 이미 구한 값과 비교하는 방법이 바로 다이나믹 프로그래밍이다.

​다이나믹 프로그래밍이란 어떤 문제에서 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 간단하게 말해서 이전에 구한 답을 재활용하여 하나의 문제를 한 번만 풀도록 하는 것이다.

 

​다이나믹 프로그래밍을 아무 데서나 사용할 수 있는 것은 아니고 사용하기 위한 조건이 존재한다.

• 최적 부분 구조(Optimal Substructure)​ : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다.

​

위의 두 조건을 만족하는 문제에서만 다이나믹 프로그래밍 기법을 적용할 수 있음을 명심해라.

​

다이나믹 프로그래밍은 문제를 분할하여 푼다는 점에서 분할 정복(Divide and Conquer) 기법과 비슷하다고 생각할 수 있다. 하지만 둘 사이에는 결정적인 차이가 하나 존재한다.

분할 정복 기법은 단순히 큰 문제를 작은 문제로 나눠서 해결하는 방법이기 때문에 동일한 문제가 발생하여도 매번 새롭게 문제를 푼다. 이에 반해 다이나믹 프로그래밍은 동일한 문제가 발생하여도 이미 구해놓은 값을 통해 새롭게 문제를 풀지 않아도 되는 장점이 있다.

작은 문제들을 해결한 값들을 큰 문제를 해결할 때 사용하기 위해 따로 저장해놓는데 이를 메모이제이션(Memoization)이라고 한다.

​

다이나믹 프로그래밍을 이해하고 분할 정복 기법과의 차이점을 알기 위해 흔히 사용하는 예시가 피보나치수열이다. 우리도 피보나치수열을 통해 이해해 보자.

​피보나치수열은 첫 번째, 두 번째 항은 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미한다. 피보나치수열의 점화식을 표현하면 다음과 같다.

Fibonacci[1] = Fibonacci[2] = 1
Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2] // i >= 3

 

예를 들어 10번째 피보나치수열을 분할 정복 기법으로 구해보자.

 

10번째의 피보나치수열을 구하기 위해선 9번째, 8번째 피보나치수열을 알아야 한다. 또한, 9번째 피보나치수열을 알기 위해선 8번째, 7번째 수열을 알아야 한다. 이런 식으로 분할해나가면서 1번째, 2번째 수열까지 도달해야 겨우 하나의 값을 알 수 있을 것이다.

이 방법은 트리의 높이만큼 연산 횟수가 2배가 되기 때문에 O(2^n)의 시간 복잡도를 가지는 굉장히 비효율적인 방법이다. 또한, 매번 피보나치수열을 구하기 위해선 위의 과정을 반복해야 한다. 피보나치수열을 이보다 효율적으로 구할 수는 없을까?

바로 다이나믹 프로그래밍을 사용하는 것이다. 위 그림을 자세히 보면 8번과 7번 피보나치수열이 2번씩 나온 것을 확인할 수 있다. 만약 왼쪽 8의 값을 구한 후 저장해놨다면 이후에 오른쪽 8의 값을 구할 때 저장된 값을 통해 새롭게 구할 필요가 없어진다.

따라서 10, 9, 8, ... , 3, 2, 1까지 한 번만 구한다면 이후에는 다시 구할 필요가 없기 때문에 O(n)의 시간 복잡도를 가지게 된다. O(n)과 O(2^n)의 차이는 굉장히 크다.

또한, 10번째 피보나치수열을 구한 후 10번째 이하의 피보나치수열을 다시 구할 때도 저장된 값을 통해 단번에 구할 수 있으므로 굉장히 효율적으로 피보나치수열을 구할 수 있게 된다.

​

다음은 피보나치수열을 분할 정복 기법 & 다이나믹 프로그래밍으로 구하는 Java 코드이다.

public class Blog {

	static long count_DaC, count_DP;
	static long[] fibonacci = new long[100];
	
	public static void main(String[] args) {
		System.out.println(fibonacci_DivideAndConquer(30));
		System.out.println(fibonacci_DynamicPrograming(30));
		System.out.println(count_DaC + " vs " + count_DP);
	}
	
	public static long fibonacci_DivideAndConquer(int n) {
		count_DaC++;
		
		if (n <= 2) return 1;
		return fibonacci_DivideAndConquer(n - 1) + fibonacci_DivideAndConquer(n - 2); 
	}
	
	public static long fibonacci_DynamicPrograming(int n) {
		count_DP++;

		//이미 n번째 피보나치수열을 구했다면 
		if (fibonacci[n] != 0) return fibonacci[n];
	
		if (n <= 2) return 1;
		
		//재귀적으로 호출하면서 구해지는 피보나치수열값을 매번 저장해줌
		return fibonacci[n] = fibonacci_DynamicPrograming(n - 1) + fibonacci_DynamicPrograming(n - 2);
	}
}

 

30번째 피보나치수열을 구하는데 분할 정복 기법은 1664079번의 연산을 수행하는 반면 다이나믹 프로그래밍은 57번의 연산만으로 구해낸다. 두 방법의 성능 차이가 굉장히 크다는 것을 알 수 있다.