[알고리즘] 동적 계획법 (Dynamic Programming)

• 동적 계획법이란?

복잡한 문제를 풀기 위해서 여러 개의 하위 문제로 분해하여 결과를 저장한 후,

그것을 결합하여 최종적인 목적에 도달하는 알고리즘 최적화 기법이다.

 

Dynamic Programming 이라는 다소 과하다 싶은 명칭의 어원은

1950년대 수학자 Richard Bellman에 의해 고안되었다.

당시 ”Programming”이라는 말은 실제로 컴퓨터의 코딩처럼 프로그래밍을 의미하는 것은 아니었다.

이때 프로그래밍이 의미하는 것은 "계획"과 "결정"이었다.

”Dynamic” 이라는 단어는 벨먼이 문제의 시가변적이며 다단계적인 특성을 포착하기 위함으로써 선택했고,

”Programming” 은 훈련이나 군수 물자 운송을 위한 최적의 프로그램을 찾기 위해

특정 방법을 사용하는 것을 가리키는 용어였다.

결론은 반복적인 계산을 피하기 위해 결과를 저장하면서 작은 문제를 사용하여 더 큰 문제를 해결하는 개념으로

다단계 계획, 즉 흔히 말해 ”메모” 의 거창한 표현일 수 도 있겠다.

 

• DP 의 사용 의의

문제를 하위문제로 분할하여 단계적으로 해결한다는 점에서 분할 정복은 DP와 접근방식에서는 유사하다고 볼 수 있다.

그러나 분할 정복은 구조상 정렬을 제외한 상당 수 경우에선 동일한 문제를 다시 풀어야 한다는 단점이 있다.

 

이때 특정 문제, 대표적으로 피보나치 수같이 점화식 f(n) = f(n-1) + f(n-2) 에서 n값이 증가함에 따라 하위 문제에서 호출되는 중복되는 문제가 기하급수적으로 증가하게 되며 이는 분할정복을 사용 시 심각한 비효율을 초래한다.

 

이에 비해 DP는 중복되는 계산의 결과값을 따로 배열이나 변수에 저장하여 나중에 동일한 계산이 필요할 때

해당 값을 반환하면 되므로 훨씬 효율적으로 알고리즘 구현이 가능하다.

중복 부분문제

예시로 위의 피보나치 함수 호출 트리에서 녹색노드와 적색노드와 같이 

항상 결과값이 같은 중복되는 부분문제를 따로 캐싱 (Caching) 하여 상위 문제를 해결할 때 사용한다면

이러한 비효율을 줄일 수 있으며 이러한 작업을 메모이제이션 (Memoization) 이라고 명칭한다.

 

• DP 의 사용 조건

DP를 적용하기 위해서는 문제가 아래의 두 가지 조건을 만족해야한다.

 

1) Overlapping Subproblems (중복되는 부분 문제)

큰 문제 안의 동일한 부분 문제가 반복적으로 발생하는 경우.

부분문제가 반복적으로 발생하지 않는다면 저장한 부분문제의 결과 값을 재사용할 필요가 없으므로 의미가 없다.

 

2) Optimal Substructure (최적 부분 구조)

큰 문제의 최적해에 작은 문제의 최적해가 포함되는 것.

즉 부분 문제의 최적해를 사용해 전체 문제의 최적해를 도출할 수 있는 경우를 의미한다.

 

이러한 조건을 만족하는 대표적인 문제로 피보나치 수, 행렬 경로 문제, 최장 공통 부분순서(LCS) 등이 있다.

 

• 탑다운 (Top-down), 바텀업 (Bottom-up)

구현 방식으로는 크게 두 가지 방식이 있는데 각각 dp배열을 사용해 피보나치 수를 구하는 코드에서 예시를 들었다.

 

탑다운은 주로 재귀 함수를 사용하며 가장 먼저 호출하는 문제가 가장 큰 문제이기에 하향식의 의미로써 명칭한다.

장점으로는 가독성이 좋고, 본래의 점화식을 이해하기 쉽다는 점이 있다.

public class Main {

	static long[] dp = new long[1000];
    
	static long fib(int n) {
		if (n == 0) return 0;
		if (n == 1) return 1;
		if (dp[n] != 0) return dp[n];
		
		dp[n] = fib(n - 1) + fib(n - 2);
		return dp[n];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		System.out.println(fib(n));
	}
    
}

 

 

바텀업은 반복문을 사용하며 가장 작은 문제들로부터 단계적으로 답을 쌓아 올린다는 상향식의 의미로써 명칭한다.

장점으로는 별개의 재귀 함수를 호출하지 않아 시간과 메모리 사용량 면에서 이점이 있다.

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		long[] dp = new long[n + 1];
		dp[0] = 0;
		dp[1] = 1;

		for (int i = 2; i <= n; i++)
			dp[i] = dp[i - 1] + dp[i - 2];
		
		System.out.println(dp[n]);
	}
    
}

 

문제에 따라 어떤 문제는 두 방식 모두 단순히 구현 방식의 기호의 차이에 그칠 수 있고,

어떤 문제는 두 방식의 구현 난이도가 심하게 차이가 나는 경우가 있을 수 있으며

드물지만 어떤 문제는 둘 중 한 가지 방식만 사용해야 하는 경우도 있을 수 있다.

 

따라서 두 방식 모두 숙지함과 동시에 어떤 방식이 해당 문제에 최적일 지 판단하는 능력을 기르는 것이 중요하겠다.