C++ 알고리즘 - 다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.

두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다!!

1. Overlapping Subproblem : 겹치는 부분이 있는 문제 (작은 문제)

2. Optimal Substructure : 최적 부분 구조

 

피보나치수열을 예로 들어 위 두 가지를 설명해보겠다.

피보나치수열은

피보나치 수열

이렇게 생긴 친구이다!!

N번째 피보나치 수를 구하는 문제인데 이 문제는 N-1번째와 N-2번째 피보나치 수를 구하는 작은 문제들이 있다.

여기서 큰 문제/ 작은 문제는 상대적인 것이다.

여기서 N번째 피보나치 수를 구하기 위해 N-1번째 피보나치 수를 구해야 하는데

이 N-1번째 피보나치 수를 구하는 문제는 또 N-2번째 피보나치 수와 N-3번째 피보나치 수를 구하는 작은 문제들로 이루어져 있다. 이런 문제들이 Overlapping Subproblem이다.

큰 문제와 작은 문제를 같은 방법으로 풀 수 있고 문제는 작은 문제로 쪼갤 수 있다!!

 

Optimal Substructure은 문제의 정답을 작은 문제의 정답에서 구할 수 있는 것이다.

서울에서 부산을 가는 가장 빠른 길이 서울 -> 대전 -> 대구 -> 부산이라면

대전에서 부산을 가는 가장 빠른 길은 대전 -> 대구 -> 부산 이어야 한다.

이 속성을 다시 피보나치수열에 적용시켜보면

문제 : N번째 피보나치 수를 구하는 문제

작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

 

Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

예를 들어

10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 == 9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 == 8번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 ==... 5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수 == 4번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

이므로 4번째 피보나치 수는 항상 같다.

 

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.

Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다. 따라서 정답을 한번 구했으면 정답을 어딘가에 메모해놓으면 시간이 더 단축될 것이다!!

이런 메모하는 것을 코드의 구현에서는 배열을 저장하는 것으로 할 수 있다. 영어로 Memoization이라고 한다.

 

이것을 한번 적용시켜보자!!

 

일반적인 피보나치 수를 구하는 함수 코드는

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

이다.

이 코드를 이용해서 fibonacci(5)를 호출하면

이렇게 겹치는 호출이 생기게 된다.

그래서 한번 답을 구할 때 어디에 메모를 해놓고 중복 호출이면 메모해놓은 값을 리턴하면 된다.

그래서 피보나치 수를 메모를 이용해 구현해보면

int memo[100];
int fibonacci(int n) {
	if (n <= 1) {
    	return n;
    }
    else {
    	if (memo[n] > 0) {
        	return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}    

다이나믹 프로그래밍 구현 방식에는 두 가지 방법이 있다.

1. Top-down (재귀)

2. Bottom-up (반복)

 

Top-down은

1. 문제를 풀어야 한다.

2. 문제를 작은 문제로 나눈다.

3. 작은 문제를 푼다.

4. 작은 문제를 풀었으니, 이제 문제를 푼다.

 

Bottom-up은

1. 문제를 크기가 작은 문제부터 차례대로 푼다.

2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

4. 반복하다 보면 가장 큰 문제를 풀 수 있다.

 

이 Top-down이랑 Bottom-up에 관해서는 나중에 더 자세히 다루겠다!!!