DP 공부

1. DP(동적계획 알고리즘)

 🍀 그리디 알고리즘과 같이, 최적화 문제를 해결하는 알고리즘.

    ✏️ 최적화 문제 : 여러 해 중에서 최적(최대나 최소같은) 값을 구하는 문제

    ✏️ 최적 부분문제 구조

      📌 동적 계획법이 최적화에 대한 어느 문제나 적용될 수 있는 것은 아님!!

           ✔ 최적화의 원칙이 성립해야만 적용이 가능.

               ▪ 최적화의 원칙이란, 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들도 해가 최적이어야 함.

    ✏️ 중복 부분문제 구조

      📌 DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고, 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결함.

           ✔ 순환적인 성질로 인해, 이전에 계산되었던 작은 문제의 해가 다른 곳에서 필요하게 되는데 DP는 이미 해결된 작은 문제들의 해를 어떤 저장 공간(table)에 저장하면서 중복 계산을 피할 수 있게 함.

 

 

+2022.02.16 추가

 

2. DP(동적계획 알고리즘) vs 분할정복

 🍀 DP (상향식 - 의존적 관계) 

    ✔ 부분문제들이 연관이 없으면 적용할 수 없음. (부분문제들은 더 작은 부분문제들을 공유한다.)

    ✔ 모든 부분문제를 한번만 계산하고 결과를 저장하고 재사용.

    ✔ 분할 정복은 같은 부분문제가 나타나는 경우 다시 계산.

 

 🍀 분할정복 (하향식)

    ✔ 연관이 없는 부분문제로 분할.

    ✔ 부분문제를 독립적, 재귀적으로 해결.

    ✔ 부분문제의 해를 결합.

    ✔ ex) 병합정렬, 퀵정렬.

 

  📌 DP의 의존적 관계들은 문제에 따라 다르고, 대부분 뚜렷하게 보이지 않아 함축적인 순서라 함.

  📌 재귀 DP가 구현이 더 쉽기 때문에 하향식도 많이 사용함.

 

 

 

3. DP 적용 접근

• 최적해 구조의 특성을 파악

     ✔ 문제를 부분문제로 나눔.

• 최적해의 값을 재귀적으로 정의

     ✔ 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의.

• 상향식 방법으로 최적해의 값을 계산

     ✔ 가장 작은 부분문제부터 해를 구하고 테이블에 저장.

     ✔ 테이블에 저장되어있는 부분 문제의 해를 이용하여 점차적으로 상위 부분문제의 최적해를 구함.

 

 

 

4. DP 적용

 🍀 피보나치 수 DP적용

 

   ✔ DP알고리즘이 수행속도가 더 빠름.

      - 재귀 알고리즘과는 달리 중복 계산이 없음.

      - 반복문을 사용하기 때문에 함수 호출이 발생하지 않음.

 

   ✔ 계산하는 항의 총 개수

      - T(n) = n + 1

      - 단 한번씩만 계산.

 

 🐣 간단히 보는 코드 🐣

 

   ✔ DP 피보나치

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

 

   ✔ memo를 이용한 재귀 피보나치

memo[] = {-1,};
memo[0] = 0;
memo[1] = 1;


fibo(n)
{
	if((n>2) && (memo[n] == -1))
		memo[n] = fibo(n-1) + fibo(n-2);
	return memo[n];
}