동적 계획법 (DP)

1. 중복이 많은 완전 탐색

• 피보나치 수열 : 첫재 및 둘쨰 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열
  • 점화식 : f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)
• 만약 완전 탐색(백트레킹)으로 해결한다면?
  • f(5)가 필요하다면 ? → f(4) + f(3) 이 필요해
  • f(4)가 필요하면 → f(3)과 f(2)가 필요해
  • f(3)이 필요하면 → f(2)와 f(1)이 필요해
  • 탑 다운 방식으로 해결하려고 한다면 너무 비효율적이고 중복으로 구해야 하는 부분이 많다.

→ 시간 복잡도 : 약 O(2^n)…. 너무 오래 걸리고 비효율적이다.

• 그렇다면 먼저 계산한 값들을 저장해놓고 필요할 때 사용하면 편하겠는데??? → 메모이제이션

 

2. 메모이제이션

• 메모이제이션 : 작은 문제의 결과값을 저장해놓고, 추후 필요하면 O(1)의 시간으로 찾아서 다시 사용하는 것

2-1. 메모이제이션 구현

• 피보나치 수열 점화식 : f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)

<백트레킹> → 시간이 오래 걸려서 입력의 수가 조금만 커도 시간 초과가 발생한다.

// 백트레킹 구현
#include <iostream>
using namespace std;

long long fibo(int x){
	if(x <= 1)
		return 1;
	else
		return fibo(x-1) + fibo(x-2);
}

int main() {
	int n;
	cin >> n;
	
	cout << fibo(n);
	return 0;	
}

<백트레킹 + 메모이제이션> → 탑다운 DP

#include <iostream>
using namespace std;

long long dp[110];

long long fibo(int x){
	if(x <= 1)
		return 1;
	// dp[x] 에 이미 값이 정해져 잇다면 구하기 전에 dp[x]이 값을 return
	if(dp[x] != -1)
		return dp[x];
	// fibo(x-1) + fibo(x-2) 값을 구하면서 dp[x]에 저장(메모이제이션)	
	return dp[x] = fibo(x-1) + fibo(x-2);
}

int main() {
	int n;
	cin >> n;
	
	// 반드시 필요한 초기화 과정
	for(int i=0; i<110; i++)
		dp[i] = -1;
	
	cout << fibo(n);
	return 0;	
}

즉, 1 + 2 개념을 합치면 → 재귀를 활용한 백트레킹 + 메모이제이션 → 탑다운 DP

 

3. 바텀업 DP → 보통 점화식을 활용한 DP

• 바텀업 DP : 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식(주로, 반복문을 사용하고 보통 생각하는 DP다)
• 피보나치 수열 점화식 : f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)

#include <iostream>
using namespace std;

int dp[110];

int main(){
	int n;
	
	cin >> n;
	
	dp[0] = 1;
	dp[1] = 1;
	
	// 이전 정보(dp[i-1], dp[i-2]) 이용
	for(int i=2; i<=n; i++)
	{
		dp[i] = dp[i-1] + dp[i-2];
	}
	
	cout << dp[n];
}

 

 

4. 동적 계획법의 2가지 접근 비교

1. 탑다운 DP

• 백트레킹(재귀) 코드 작성, 중복이 많음
• 많은 중복을 메모이제이션을 통해 중복을 제거할 수 있다.
• 한번 깨우치면 쉽지만, 진입장벽이 높다고 생각

2. 바텀업 DP

• dp[입력] = 출력 → 테이블 정의, 경험, 아이디어가 많이 필요하다.
• dp[i] : i를 입력 받았을 때 경우의 수
• 점화식을 반드시 찾아야 풀 수 있다(점화식을 기본으로 반복문을 수행하기 때문)
• dp[1] 부터 dp[i-1] 까지 모두 구해놓고 dp[i]를 구하는 상황
• 점화식을 찾는 부분에서 어려움이 있지만, 진입장벽이 낮다.

→ 결론적으로 모든 DP 문제를 하나의 방식으로 풀 수 없기 때문에 두 방식 모두 익숙해야 한다.

 

5. 예제

https://www.acmicpc.net/problem/1463

https://www.acmicpc.net/problem/11049