알고리즘 / DP(Dynamic programming) 동적계획법

DP(Dynamic programming) 동적 계획법

동적 계획법(DP)은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. state의 값을 메모리에 저장하여 반복적인 연산을 피해 시간 복잡도를 낮추고 메모리 낭비를 막는다. 

코딩 테스트에 dp는 자주 나오는 문제이다. 하지만 나는 dp 푸는 것이 두려워 계속 미뤄뒀지만.. 이제는 진짜 풀어볼 때가 되었다...

 

DP를 푸는 방법

1. DP를 사용하여 푸는 문제인지 확인
2. 어떻게 상태를 표현할지 정함
3. 상태 관계를 수식화
4. top-down or bottom-up 방식으로 풀지 정함

 

1. DP를 사용하는 푸는 문제인지 확인

특정 수량의 최대 최소를 구하는 문제들, 특정 조건을 만족하는 배열 개수를 세는 문제 등 DP로 풀 수 있다. 중복되는 함수들을 생각하면서 풀 수 있다. 예를 들어 피보나치수열 문제에서 f(n) = f(n-1) + f(n-2) 같이 나타낼 수 있으므로 DP를 사용하여 풀 수 있다.

 

2. 어떻게 상태를 표현할지 정함

DP 문제들은 상태에 대한 문제들이다. 주어진 문제에서 특정 위치나 현 상태를 나타낼 수 있는 것들을 개별적으로 표현할 수 있는 어떤 묶어져 있는 매개변수를 말한다. 공간을 절약하기 위해 매개변수 묶음은 최대한 줄어들어야 한다. 피보나치수열 문제에서는 매개변수 n(수)로 상태를 표현할 수 있다. 

 

3. 상태 관계를 수식화

피보나치 수열 문제에서 f(n) = f(n-1) + f(n-2) 같이 수식화한 거처럼 상태 관계를 수식화 해야 한다. DP에서 가장 중요하고 어려운 부분이다. 작은 수부터 구해보면서 규칙을 찾고 어떤 규칙이 있고 상태를 표현할 수 있는지 찾아야 한다. 많은 문제를 풀어보며 식을 세울 수 있어야 한다. 

 

4. top-down or bottom-up 방식

DP를 구현할 때 top-down, bottom-up 두 가지 방식이 있다. top-down 방식은 재귀 함수로 구현하는 방식이고 bottom-up 방식은 반복문으로 구현하는 방식이다. 

 

예) 피보나치수열

Top-down 방식(재귀 호출)

int dp[100000];

int fivo(int n) {
	if (n == 1 || n == 2)
		return 1;

	if (dp[n] != 0)
		return dp[n];

	return dp[n] = fivo(n - 1) + fivo(n - 2);
}

Bottom-up 방식(반복문)

int dp[100000];

int fivo_(int n) {
	dp[1] = 1;
	dp[2] = 1;
	
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return dp[n];
}

n이 6일 때

 

프로그래머스 - DP문제

https://programmers.co.kr/learn/courses/30/parts/12263

프로그래머스