[동적 계획법] DP 개요

1. 동적 계획법

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

1.1. 동적 계획법의 핵심 이론

1.1.1. 동적 계획법의 원리와 구현 방식

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

 

1.1.2. 동적 계획법 대표 예시 피보나치

D[N] = D[N-1] + D[N-2]

1. 동적 계획법으로 풀수 있는지 확인하기

   D[1] = 1
   D[2] = 1
   D[3] = 2
   D[4] = 3
   D[5] = 5

D[5] 는 D[4] + D[3] -> 5 = 2+3

5번째 피보나치수열을 구하는 방법은 4번째와 3번째를 구하는 방법으로 작게 나눌 수 있고,

수열의 값은 항상 같으므로 동적 계획법 사용 가능

2. 점화식 세우기

이 부분이 경험과 사고..? 많이 해봐야 늘어나는 부분이므로 꾸준히 DP를 풀어주는 것이 중요하다고 봅니다.

논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악

 

3. 메모이제이션 원리 이해하기
4. 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말합니다.
   이런 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있습니다.
5. top-down 방식 이해하기 -> 재귀

   static int[] D;
   public static void main(String[] args){
	   Scanner scan = new Scanner(System.in);
	   int n = scan.nextInt();
	   D = new int[n+1]; 
	   for(int i =0; i<=n; i++){
		   D[i] = -1; //초기화 안하면 값이 이상해짐
	   }
   }
   D[0] = 0;
   D[1] = 1;
   fibonacci(n);
   sout(D[n]);
   }

	static int fibonacci(int n){
		if(D[n]!= -1) return D[n];
		return D[n] = fibonacci(n-1) + fibonacci(n-2);
	}

5. bottom-up 방식 이해하기 -> loop
   
   

      static int[] D;
   public static void main(String[] args){
	   Scanner scan = new Scanner(System.in);
	   int n = scan.nextInt();
	   D = new int[n+1]; 
	   for(int i =0; i<=n; i++){
		   D[i] = -1; //초기화 안하면 값이 이상해짐
	   }
   }
   D[0] = 0;
   D[1] = 1;
   for(int i = 2; i <= n; i++){
	   D[i] = D[i-1] + D[i-2];
   }
   sout(D[n]);
   }

 

 

 

1.2. 자주 나오는 문제

1.2.1. 단순 점화식

D[i] = D[i-1] + D[i-2];
D[i] = D[i-1]

e.g)

• 2xn 타일링 / 타일링 류
• 1,2,3 더하기 / 경우의 수 류
• 이친수

1.2.2. D[i] 와 D[?] 비교

D[i] = Math.max ~
D[i] = Math.min ~

e.g)

• 카드 구매하기
• 가장 긴 증가하는 부분 수열 (부분집합 부분수열 류)

1.2.3. 2차원 배열 + 다차원 배열

D[i][J] = D[i-1][0] + D[i-2][1];
D[i][2] = Math.max ~
D[i][2] = Math.min ~

e.g)

• 쉬운 계단 수