[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 11장 동적 계획법

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 :  https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

11.1 동적 계획법 (Dynamic Programming)

1) 정의 

- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로 최종적으로 복잡한 문제의 답을 구하는 방법
 

2) 핵심 이론

(1) 동적 계획법의 원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은문제들이 반복되어 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 메모이제이션(memoization) 기법 : 모든 작은 문제들은 한 번만 계산해 dp 테이블에 저장하며 추후 재사용할 때는 dp 테이블을 이용한다. 
4. 동적 계획법은 톱-다운 방식(top-dowm)과 바텀-업(bottom-up) 방식으로 구현할 수 있다.

 
(2) 예시 : 피보나치 수열
- 피보나치 수열 공식 : D[N] = D[N-1] + D[N-2]
① 동적 계획법으로 풀 수 있는지 확인한다. 

• N번째 피보나치 수열을 구하기 위해 N-1번째 피보나치 수열, N-2번째 피보나치 수열을 구해야 한다.
• 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.

② 점화식 세우기

• 피보나치 수열 공식 : D[N] = D[N-1] + D[N-2]

③ 메모이제이션 원리 이해하기

• 부분 문제를 풀었을 때 DP 테이블에 문제를 저장하고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용한다.
• 불필요한 탐색과 연산이 줄어들어 시간복잡도에 이점이 있다.

④ 톱-다운 방식 이해하기

• 위에서부터 문제를 파악해 내려온다.
• 재귀 함수 형태로 주로 구현한다. → 재귀의 깊이가 매우 깊어지면 런타임 에러 발생 가능
• 코드의 가독성이 좋고 이해하기 쉽다.

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> dp;

int fibo(int n) {
	if (dp[n] != -1) // 이미 계산함.
		return dp[n];
	return dp[n] = dp[n - 1] + dp[n - 2];
}

int main()
{
	cin >> n;
	dp.resize(n+1);

	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) 
		dp[i] = -1; // 초기화

	fibo(n);
	cout << dp[n];
	return 0;
}

⑤ 바텀-업 방식 이해하기

• 가장 작은 부분 문제부터 문제를 해결하며 점점 큰문제로 확장해나가는 방식
• 반복문의 형태로 주로 구현한다.
• 톱-다운 방식보다 안전하다.

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> dp;

int main()
{
	cin >> n;
	dp.resize(n+1);

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

	cout << dp[n];
	return 0;
}