동적계획법(DP)

동적계획법(Dynamic Programming)

Dynamic Programming(DP)는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결하는 방법을 의미한다.

DP를 적용할 수 있는 조건은 무엇일까?

부분 반복 문제이며, 최적 부분 구조일 때 DP를 적용할 수 있다.

1) 부분 반복 문제(Overlapping Subproblems)

DP는 큰 문제를 여러 개의 부분 문제로 나누고 그 문제의 결과 값을 재활용하여 전체의 답을 구한다.
따라서 부분 문제가 반복적으로 나타나지 않으면 재사용이 불가하여 DP를 사용할 수 없다.

Memoization(메모이제이션)
Memoization은 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장해 계산 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 것을 의미한다.
DP는 중복 연산을 반복하지 않기 위해 부분 문제의 결과 값을 저장하여 사용한다.

2) 최적 부분 구조(Optimal Substructure)

DP는 부분 문제의 최적의 결과 값으로 전체 문제의 최적의 결과를 나타내므로 특정 문제의 정답은 문제의 크기와 상관없이 항상 동일하다.
부분 문제의 결과 값이 젠체 문제에도 동일하게 적용되어 정답이 변하지 않는 경우에만 DP를 사용할 수 있다.

DP를 구현하는 방식에는 무엇이 있을까?

DP는 Bottom-Up 방식 또는 Top-Down 방식을 사용하여 구현할 수 있다.

1) Bottom-Up(상향식) - 반복문

아래에서 위로 접근하는 방식으로 부분 문제를 해결하여 큰 문제를 풀어가는 방식이다.
반복문(for문)을 이용하여 구현한다. 다음은 피보나치 함수를 Bottom-Up 방식으로 구현한 예제이다.

public class BottomUp {
	static int[] dp;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		dp = new int[N+1];
		System.out.println(fibo(N));
	}
	
	static int fibo(int N) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<N+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[N];
	}
}

2) Top-Down(하향식) - 재귀

위에서 아래로 접근하는 방법으로 큰 문제를 부분 문제로 쪼개가면서 문제를 풀어가는 방식이다.
재귀 호출을 통해 구현한다. 다음은 피보나치 함수를 Top-Down 방식으로 구현한 예제이다.

public class TopDown {
	static int[] dp;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		dp = new int[N+1];
		System.out.println(fibo(N));
	}
	
	static int fibo(int N) {
		if(x ==1 || x==2) return 1;
		if(dp[N] != 0) return dp[N];
		return fibo(N-1) + fibo(N-2);
	}
}

---

분할정복과의 차이점은 무엇일까?

분할정복과 DP는 부분 문제를 해결하여 큰 문제를 해결한다는 점은 같다.
하지만 분할정복은 부분 문제가 모두 독립적이며, 동일한 부분을 중복하지 않는 다는 점에서 DP와 차이가 있다.