알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (1)

참고 영상: https://www.youtube.com/watch?v=5Lu34WIx2Us

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

메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법

이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 나중에 해당 결과가 필요할 때 기록된 결과를 그대로 사용한다.

다이나믹 프로그래밍의 구현은 탑다운(하향식)과 보텀업(상향식) 방식으로 구성된다.

 

다이나믹 프로그래밍을 사용하는 조건은 다음과 같다.

1. 최적 부분 구조 (Optimal Substrcture)

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

 

2. 중복되는 부분 문제 (Overlapping Subproblem)

동일한 작은 문제를 반복적으로 해결해야 한다. 

 

예를 들어 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있다. 프로그래밍에서는 배열이나 리스트를 이용해 표현한다.

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

단순 재귀 소스 코드를 사용하여 피보나치 수열을 구현할 수 있다.

 

f(4)를 구할 때 f(3)과 f(2)로 나누어지게 된다. 큰 문제 하나를 해결하기 위해 작은 문제 두개를 해결한 값을 가지고 있으면 된다. 이를 최적 부분 구조라고 할 수 있다.

최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.

 

단순 재귀 함수로 피보나치 수열을 구현하게 되면 지수 시간 복잡도(O(2^n))를 가지게 된다. f(2)가 여러 번 호출되는 것을 알 수 있는데 이것이 중복되는 부분 문제이다.

중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다.

 

 

메모이제이션 (Memoization)

한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

다이나믹 프로그래밍 구현 방식에는 탑다운 (하향식)과 보텀업 (상향식)이 있는데 전형적인 형태는 보텀업 방식이다.

 

탑다운 방식은 재귀함수를 이용한다. 큰 문제를 해결하기 위해서 작은 문제들은 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제에 대한 답까지 얻을 수 있도록 코드를 작성하고 이러한 과정에서 한 번 계산된 값을 기록하기 위해 메모이제이션을 사용한다.

 

보텀업 방식은 반복문을 활용한다. 아래 쪽부터 작은 문제를 하나씩 해결하면서 문제를 해결한다. 보텀업 방식에서 사용되는 결과 저장용 배열은 DP 테이블이라고 한다. 

 

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념으로 DP에 국한된 개념은 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP를 위해 활용하지 않을 수도 있다.

 

long long d[51];
long long fibo(long long x) {
	cout << "f(" << x << ") ";
	if (x == 1 || x == 2)
		return 1;
	if (d[x] != 0)
		return d[x];
	d[x] = fibo(x - 1) + fibo(x - 2);
	return d[x];
}

탑다운 방식으로 피보나치 수열을 구현하였다. 큰 문제부터 아래 문제를 호출하며 얻어나간다.

메모이제이션 기법을 사용하면서 색칠된 부분만 호출될 것임을 알 수 있다. 실행 결과는 f(6)일 경우 f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)이다. 피보나치 수열 함수의 시간 복잡도는 O(N)이 된다.

 

int main() {
	d[1] = 1;
	d[2] = 1;
	int n = 50;
	for (int i = 3; i <= n; i++)
	{
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << '\n';
	return 0;
}

보텀업 방식으로 피보나치 수열을 구현하였다. 작은 문제부터 큰 문제까지 해결하고 있다.

 

 

다이나믹 프로그래밍 vs 분할 정복

둘의 차이점은 부분 문제의 중복 여부이다.

DP 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. 하지만 분할 정복 문제에서는 동리한 부분 문제가 반복적으로 계산되지 않는다.

 

예를 들어 퀵 정렬의 경우를 살펴보면, Pivot이 자리를 잡으면 Pivot의 위치는 변하지 않는다. 분할 이후 해당 피벗을 처리하는 문제는 호출되지 않는다. 위 그림은 첫 번째 값을 Pivot으로 설정한 다음 분할을 수행한 결과이다. 5의 위치는 앞으로 쭉~ 바뀌지 않을 예정이다.

 

https://shine-slowly.tistory.com/37

알고리즘 : 정렬이란? (C++로 구현)

 

 

다이나믹 프로그래밍 문제 접근법

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다. 점화식을 만드는 과정이 어렵게 느껴질 것이다.