[알고리즘] 다이나믹 프로그래밍

taeeeeun·2022년 4월 1일

다이나믹 프로그래밍 알고리즘

알고리즘

목록 보기

2/4

알고리즘 공부를 시작하면서 가장 어려웠던 곳이 바로 다이나믹 프로그래밍, DP이다. 고등학생일 때도 점화식 세우는 걸 제일 못했는데.. 아직도 너무 어렵다.

다이나믹 프로그래밍이란?

특정 범위의 값을 구하기 위해 이전 범위의 값을 활용하는 방법
큰 문제를 작은 문제로 나누어서 풀 수 있는 문제에서 사용
Memoization - 이전에 구해둔 값을 저장해서 중복되는 계산 방지

피보나치 수열 재귀함수 vs 동적 계획법

단순 재귀함수

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

동적 계획법 활용

int fibonacci(int n){
	if (n<=1) return n;
	if (dp[n]) return dp[n];
	return dp[n]=fiboancci(n-1)+fibonacci(n-2)

동적 계획법은 n이 커도 시간 초과가 나지 않음

Top-down vs Bottom-up

위에 작성했던 코드 방식은 n부터 탐색하는 Top-Down 방식이다.
Bottom-up은 0부터 탐색하며 이미 알고 있는 작은 문제부터 원하는 곳까지 탐색한다. (Top-down보다 속도가 더 빠르다)

Bottom-up

dp[0]=1;
dp[1]=1;
for (int i=2; i<=N; i++) {
	dp[i]=dp[i-1]+dp[i-2];

풀이 과정

이전 값과 현재 값이 어떻게 관련되어있는지 파악하자 (표 사용)
점화식 세우기

예제

백준 11053 가장 긴 증가하는 부분 수열

접근 💡

현재 인덱스에서는 이전 인덱스까지의 가장 긴 길이를 참조할 수 있음
해당 인덱스로 끝나는 증가하는 배열 중 가장 긴 길이 탐색

코드 💻

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
  //dp 배열을 1로 초기화 (최소 길이가 1이므로)
	vector<int> dp(N+1,1);
	vector<int> A(N+1);
	int answer = 1;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
  //현재 인덱스부터 그 이전 인덱스와 비교해서 dp값 갱신
	for (int i = 2; i <= N; i++) {
		for (int j = i-1; j >= 1; j--) {
			if (A[i] > A[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		answer = max(answer, dp[i]);
	}
	cout << answer;
}

과제문제

백준 11727: 2xn 타일링2

접근 💡

세로 길이는 고정이고 가로 길이는 변동
채우는 타일의 종류는 12, 21, 2*2이므로 지금까지 만들어진 타일에 어떤 타일을 붙여서 가로를 완성할지 생각하면 됨

이 문제를 풀 때 직접 사각형을 다 그려서 개수를 셌다.. dp는 풀 때마다 어떻게 풀지는 알거 같은데 점화식으로 세우는게 가장 어려운 느낌 ㅜ

사각형을 계속 그리면서 생각해보니 옆에 붙일 수 있는 건 가로 길이가 1, 2이기 때문에 n-1인 가로+1*2 타일 1개인 경우와 n-2가로와 가로 2를 완성하는 경우를 합하면 된다. 이 때 두번째 경우는 2가지가 있기 때문에 점화식을 세우면

dp[n]=dp[n-1]+ 2*dp[n-2]

코드 💻

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int>dp(N + 1);
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + 2 * dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[N];
}