[Algorithm] 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍이란?

동적 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘입니다.
일반적으로 분할정복 기법은 작은 여러 개의 문제로 나누어서 풀 때, 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고, 값을 저장해두었다가 다시 사용하는 기법이 동적 프로그래밍입니다.

대표적인 예시로는 피보나치 수열이 존재합니다.
예를 들어 fib(5)를 구한다고 가정하겠습니다.

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이렇게 fib(5)를 구하기 위한 과정 속에서 같은 숫자가 여러 번 중복되는 것을 확인할 수 있습니다. 위의 방식으로 구하게 된다면 시간 복잡도는 무려 $O(2^n)$이 나오게 됩니다.

만약 계산 과정 중에 중복되는 값은 다시 계산하지 않고, 하나하나 다 저장하게 된다면 우리는 시간복잡도를 $O(n)$ 만큼 줄일 수 있습니다.

코드

일반적인 피보나치 수열을 계산하는 코드 외에, 한 번 계산된 값은 저장할 수 있는 배열을 만들어주었습니다.

#include <iostream>

using namespace std;


// 일반적인 방식으로 짠 피보나치 수열
int fibo(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	return fibo(x - 1) + fibo(x - 2);
}

// 동적 프로그래밍으로 짠 피보나치 수열
int arr[100];
int dpFibo(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (arr[x] != 0) return arr[x];
	return arr[x] = dpFibo(x - 1) + dpFibo(x - 2);
}

int main() {
	printf("%d", fibo(10));
	printf("%d", dpFibo(10));

	return 0;
}

참고

블로그
블로그