[2022 겨울학기] 5주차 - 다이나믹 프로그래밍

1. DP(Dynamic Programming)이란?

하나의 큰 문제를 여러개의 작은 문제로 분할하여 푸는 방법

이미 계산된 작은 문제의 결과값을 별도의 메모리 영억에 저장해두고 활용한다

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킬 수 있다

방법: top-down(재귀), bottom-up(반복문)

대표예: 피보나치 수열

 

 

2. 동작 원리

-사용 조건

큰 문제를 작은 문제로 나눌 수 있다

작은 문제에서 구한 값은 그것을 포함하는 큰 문제에서도 동일한 값으로 사용된다.

 

-사용 방법

완전 탐색으로 접근한다.

반복되는 부분 문제를 찾는다.

기저단계를 설정한다. (점화식으로 더이상 계산하지 못하는 부분)

점화식을 설정한다

중복된 문제를 한번만 계산하기 위해 메모이제이션을 이용한다(이전에 계산한 값을 메모리에 저장하는 것)

 

 

3. 코드

int dp[50];
//bottom-up
int fibo(int n) {
	dp[0] = 1;
	dp[1] = 1;

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


//top-down
int fibo(int n) {
	if (n == 0 || n == 1)
		return 1;

	if (dp[n] == 0)
		return dp[n] = fibo(n - 1) + fibo(n - 2);
	else if (dp[n] != 0)
		return dp[n];
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!