08: 다이나믹 프로그래밍

다이나믹 프로그래밍

메모리를 적절하게 사용하여 수행 시간의 효율을 비약적으로 향상시킨다.

이미 계산된 결과는 별도 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

프로그래밍(알고리즘)에서의 다이나믹은 자료구조에서의 다이나믹과는 다른 무게를 가진다.

 

구현

탑 다운, 보텀 업

 

조건

1. 최적 부분 구조 - 큰 문제를 작은 문제들로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결해야 합니다.

 

피보나치 수열

다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.

피보나치 수열의 시간 복잡도(지수)를 고려해 봤을 때 다이나믹 프로그래밍으로 효율적인 해결이 가능하다.

 

피보나치 수열: 단순 재귀 함수

#include <iostream>
using namespace std;

int fibo(int x) {
	if (x == 1 || x == 2) {
		return 1;
	}
	return fibo(x - 1) + fibo(x - 2);
}
int main() {
	cout << fibo(4) << "\n";
	return 0;
}

 

메모이제이션

다이나믹 프로그래밍을 구현하는 방법 중 하나.

한 번 계산한 결과를 메모리 공간에 메모한다. (같은 문제를 호출하면 메모했던 결과를 가져온다)

값을 기록한다는 점에서 Caching이라고도 한다.

 

탑다운과 보텀업

탑다운(메모이제이션)은 하향식, 보텀업은 상향식.

다이나믹 프로그래밍의 전형적인 방식은 보텀업이다. 결과 저장용 리스트는 DP 테이블이라고 부른다.

메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.

 

피보나치 수열: 보텀업 다이나믹 프로그래밍 코드

#include <iostream>
using namespace std;

long long d[100];

int main() {
	d[1] = 1;
	d[2] = 1;
	int n = 50;

	for (int i = 3; i < n; i++) {
		d[n] = d[n - 1] + d[n - 2];
	}
	cout << d[n] << "\n";

	return 0;
}

 

피보나치 수열: 메모제이션 동작 분석

메모이제이션을 사용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)이다. 이미 계산된 결과는 상수 시간이 걸린다.

 

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

둘 다 최적 부분 구조를 가질 때 사용할 수 있다.

차이점은 부분 문제의 중복이다. 다이나믹 프로그래밍은 부분 문제들이 서로 영향을 미치며 중복되는데, 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않는다.

분할 정복의 대표적인 예시인 퀵 정렬을 보자. pivot이 한 번 자리를 변경하면 그 기준 원소의 위치는 바뀌지 않는다. 분할 이후 해당 피벗을 처리하는 부분 문제는 호출되지 않는다.

 

다이나믹 프로그래밍: 접근 방법

주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 중요.

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 해결할 수 있는지 검토해 보고 떠오르지 않는다면 다이나믹 프로그래밍을 고려.

일반 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.

 

문제 8-5. 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

아이디어 및 코드

피보나치 수열 문제를 도식화했던 것처럼 함수 호출 과정을 그림으로 그려 보면 이해하는 데 도움이 된다.

문제에서 요구하는 내용을 점화식으로 표현해 본다. 그리고 이 점화식을 토대로 보텀업 다이나믹 프로그래밍으로 코드를 작성해 본다.

#include <iostream>
#include <stdlib.h>
using namespace std;

int x;
int dp[30000];

int main() {
	cin >> x;
	
	
	for (int i = 2; i <= x; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0) {
			dp[i] = __min(dp[i / 2] + 1, dp[i]);
		}
		if (i % 3 == 0) {
			dp[i] = __min(dp[i / 3] + 1, dp[i]);
		}
		if (i % 5 == 0) {
			dp[i] = __min(dp[i / 5] + 1, dp[i]);
		}
	}

	cout << dp[x] << "\n";
}

 

피드백

이해하는 데 정말 오래 걸린 문제이다. 물론 풀지도 못 했다. 문제에서 요구하는 점화식을 세울 수 있도록 많은 문제를 풀어 봐야겠다.

 

문제 8-6. 개미 전사

내 코드

// 8-6. 개미 전사
// 다시 풀기 (4/3 다시 풀었으나 틀림, ** 확인)

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;

int dp[100];
int n;
vector<int> arr;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}

	// dynamic programming (bottom up)
	dp[0] = arr[0];
	// dp[1] = arr[1]; // ** 틀렸어!!!!!!!!!!!!!
	dp[1] = max(arr[0], arr[1]);

	for (int i = 2; i < n; i++) {
		if (dp[i - 1] < dp[i - 2] + arr[i]) {
			dp[i] = dp[i - 2] + arr[i];
		}
		else {
			dp[i] = dp[i - 1];
		}
	}
	
	cout << dp[n - 1] << "\n";
}

피드백

점화식을 직접 세워 보았더니 얼추 맞았다. 처음에 d[1] 값을 넣을 때 d[0], d[1]을 비교해서 큰 것을 넣지 않고 a[1]을 넣어 버리는 실수를 했다.