DP(Dynamic Programming) - 동적 계획법

요새 알고리즘을 공부하다보니 전략(?)에 대해 접근 방법이 있는 걸 조금씩 알게되고 있어서

 

잊지 않게 포스팅을 하려고한다.

(다들 파보나치로만 나는 바보라서 더 헷갈렸다... 하지만 파보나치만큼 DP에 딱 맞는 예시는 없는거 같다.)

 

다른분들의 포스팅에서 매우 상세하게 되어있기 때문에 내가 이해한 내용만 적고 넘어가려한다.(난 정말 쉽고 정확하게 이해하지 않으면 안되기에 매우 허접한 용어로...)

 

동적 계획법을 풀기위해 필요한것! 1. 점화식 2. 큰 문제를 작은문제로 쪼개 풀기 or 작은문제부터 쭉 해결해나가기 3. 메모이제이션(똑같은 계산 결과는 저장하자)

 

1. 점화식

"점화식을 만족하는 수열을 점화식의 해"라고 한다.(그래서 최적해 찾기라는 말이 있나보다)

 -> 쉽게 생각하면 아래 int GooGooDan(int a, int b)가 점화식 함수라고 보면 될것 같다.

 

//! 구구단이라는 반복문의 결과를 얻기위한 함수(점화식, 수열의 해)
int GooGooDan(int a, int b)
{
	return a * b;
}

int main()
{
	//! 9 * 9 구구단 계산 소스코드
	for (size_t i = 1; i <= 9; i++)
	{
		for (size_t j = 1; j <= 9; j++)
		{
			GooGooDan(i, j);
		}
	}
}

 

2. 큰 문제를 작은문제로 쪼개 풀기 or 작은문제부터 쭉 해결해나가기

큰 문제를 작은문제로 쪼개 풀기 -> 재귀함수 만들기

-> ex)구구단의 3단을 재귀로 만들어 풀기(3단이라는 큰 문제로 들어가서 다 끝날때까지 돌면서 작은 문제를 해결한다. 

작은문제부터 쭉 해결해나가기 -> 반복문으로 만들기

-> ex)그냥 보이는 작은 문제를 전부 해결하는 반복문(이해가 될지 모르겠다...)

 

 

3. 메모이제이션(똑같은 계산 결과는 저장하자)

예를 들어서 1탄부터 10탄까지 게임이 있는데 한번 죽었다고 1탄부터 돌아가면 너무 힘들기 때문에 깰 때마다 세이브를 해놓는 개념!!

-> ex) 6탄을 클리어하기 위해 미리 클리어한 5탄의 결과를 불러와서 처리해준다. 

 

 

 

참고 :

medium.com/@wooder2050/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0

namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming