동적 계획법(Dynamic Programming)

2023. 5. 11. 22:52

동적 계획법(Dynamic Programming)

동적계획법, 흔히 DP라고 부르며

큰 문제를 더 작은 서브문제들로 쪼갠 뒤 서브문제들의 답을 구해서 저장해두고
서브문제들의 답들을 이용해 큰 문제의 답을 계한하는 알고리즘

핵심 개념
1) 문제를 서브문제로 쪼갠다
2) 하나의 문제는 한번만 풀도록 답을 저장해둔다

DP 사용 예시

문제를 더 작은 sub문제로 나누어 해결한 후 그 결과들로 원래의 문제를 해결하는 대표적인 예시로는 피보나치 수열이 있다.

일반적으로 피보나치수열을 C++로 작성한다면 아래와 같이 재귀적으로 구현할 수 있다.

#include <iostream>

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


int main() {
	std::cout << fibonacci(5);

	return 0;
}

위 코드가 실행되는 함수스택을 그림으로 표현한다면 아래와 같다.

하지만 위처럼 재귀적으로 피보나치 수열을 구한다면 Fibo(0)이나 Fibo(1)같은 함수들이 쓸데없이 여러번 호출되는 문제가 발생한다.
Fibo(5)가 아닌 Fibo(100000)같은 큰 수로 호출한다면 Fibo(0)이나 Fibo(1)같은 서브함수들은 쓸데없이 어마어마한 횟수가 호출될 것이다.
또한 함수 스택이 너무 깊어져서 프로그램이 오버플로우되어 죽게될 수도 있다.

DP를 사용해서 해결하는 방법

DP는 서브함수들을 쓸데없이 계속 호출해서 계산하지 않기위해 한번 계산한 값을 저장해두는
메모이제이션(memoization)기법을 사용한다.
이를통해 쓸데없는 반복을 제거하고 실행속도를 높일 수 있다.

즉 sub문제들의 답을 배열에 저장한다.
fibonacci 배열을 만들고 { 0, 1 }상태로 시작해서 값을 계산할때마다 재귀호출하는 것이 아니라 배열에 값을 계속 추가해주는 방법이다.
만약 fibo(1)이 필요하다면 fibo(1)함수를 호출하는게 아니라 그냥 배열에서 `fibo[1]`을 O(1)로 접근해서 가져오면 된다.

#include <iostream>

int arr[10001];

int fibonacci(int n)
{
	if (n <= 1) { // 초기조건인 fibo(0) = 0, fibo(1) = 1
		arr[n] = n;
		return arr[n];
	}

	if (arr[n] != 0) { // 이미 저장되어 있는 값이라면 그냥 return
		return arr[n];
	}
	else { // 아직 계산한적 없는 값이라면
		arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
		return arr[n];
	}
}

int main() {
	std::cout << fibonacci(5);

	return 0;
}

이렇게 사용하면 같은 함수를 여러번 반복하지 않고, N까지 배열을 채워나가면 끝이니 시간복잡도는 O(N)이라고 할 수 있다.

DP 사용 조건

세가지 조건이 충족되어야 함

1) Problem이 더 작은 Sub Problem으로 쪼개질 때
2) Sub Problem의 솔루션으로 더 큰 Problem의 솔루션을 구할 수 있을 때

=> 즉 점화식을 세울 수 있어야 한다.
3) Sub Problem이 겹칠 때

=> 메모이제이션으로 필요한 계산 수를 많이 줄일 수 있음

여기서 Problem과 Sub Problem을 정의하는 과정이 제일 어려워서 이 부분은 많은 경험을 통해 해결해야 함

언제 DP를 사용하는가?

1) 위의 세가지 조건을 충족할때
2) "몇가지 방법이 있는가?" 라고 물어볼때는 DP문제일 확률이 높음

DP 사용 방법

DP를 이용하려면 먼저 점화식을 세워야 한다.

점화식이란 어떤 수열의 일반항을 이전 항들을 이용해 정의한 식이며 피보나치 수열의 점화식은 아래와 같다.

DP의 두가지 방식

1) Top-Down : 큰 문제를 쪼개나가면서 진행하고, 재귀로 구현한다. 점화식을 이해하기 쉬운 장점이 있다.
2) Bottom-Up : 작은 문제부터 올라가면서 진행하고, 반복문으로 구현한다. 시간과 메모리 사용량을 줄일 수 있는 장점

모든 DP문제는 두 방식 모두 풀이가 가능하다.
둘 중 더 편하게 느껴지는 방식을 사용해도 되지만 일반적으로는 Top-Down보다는 Bottom-Up방식이 더 좋다고 할 수 있다.

하지만 어떤 문제들은 두 방식의 구현 난이도가 심하게 차이나는 상황이 있기도 하므로 두 방식 모두 사용할 수 있게 연습해야 한다.

int fibonacci(int n) // Bottom-Up 방식
{
	std::vector<int> f(n + 1);
	f[1] = f[2] = 1;
	for (int i = 3; i <= n; i++) {
		f[i] = f[i - 1] + f[i - 2];
	}

	return f[n];
}

/***************************************/

int arr[10001];

int fibonacci(int n) // Top-Down 방식
{
	if (n <= 1) {
		arr[n] = n;
		return arr[n];
	}

	if (arr[n] != 0) {
		return arr[n];
	}
	else {
		arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
		return arr[n];
	}
}

※ Bottom-Up이 더 좋은 이유

시간복잡도와 공간복잡도 모두 Bottom-Up방식이 유리하고,

일반적으로 반복문으로 해결이 가능한 문제는 재귀보다는 반복문으로 해결하는것이 좋다.

예를들어 Top-Down방식은 피보나치 수열을 Fib(100000)하면 함수 콜 스택이 100000개 쌓여서 오버플로우 될 수 있다.
그래서 이런 상황에선 좋은 방식이 아니다. 생각의 방식은 더 자연스럽지만 코드면에서 좋지 않은 케이스
반면 Bottom up 방식이라면 가장 작은 sub problem인 fib(0)부터 시작해서 fib(1), fib(2), ....순으로 값을 저장하며 올라간다면 함수스택으로 고민할일은 없다.

대표적인 예시 문제

DP사용의 대표적인 예시는 냅색문제가 있다.

https://smallpants.tistory.com/240

※ 참고문헌

https://sectumsempra.tistory.com/86

저작자표시

batsalee의 작은바지