동적계획법(DP; Dynamic Programming)

동적계획법의 개념

 

그리지 알고리즘과 같이 최적화 문제를 해결하는 방법으로서 먼저 작은 부분의 문제들의 해를 구하고 이들을 이용하여 보다 큰 부분 문제를 해결한다. 이러한 방식으로 최종적으로 원래 주어진 문제를 해결하는 방법

 

 

동적계획법의 특징

 

1) 상향식 방법으로 접근한다. 

2) (중복 부분문제 구조) 부분 문제 간 연관이 있어야만 적용 가능하다. 

3) (중복 부분문제 구조) 모든 부분 문제는 한번만 계산한 뒤 결과를 저장하여 그 결과값만 재사용한다. (재계산 아님)

4) (최적화의 원칙) 전체 문제의 해가 최적이려면 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

5) 수행 속도가 빠름 => 재귀와 달리 중복 계산이 없고, 반복문 사용으로 함수 호출없다.

 

=> 이 '중복 부분문제 구조 Overlapping Subproblems'와 '최적화의 원칙 Optimal Substructure'을 충족해야 DP를 적용할 수 있다.

 

동적계획법 접근 방법

 

1) 최적해 구조의 특성 파악 => 작은 부분 문제로 나누기

2) 최적해의 값을 재귀적으로 정의 => 점화식 구하기

3) 상향식 방법으로 최적해 값 계산
  - 가장 작은 문제의 해를 찾고 테이블에 저장 => 이 저장된 부분문제의 해를 이용해 점차적으로 상위 문제 해결

 

 

동적계획법의 시간 복잡도: O(f(n))

 

package 동적계획법;

import java.util.Arrays;
import java.util.Scanner;

public class 피보나치 {
	static long callFibo1, callFibo2, callFibo3;
	static long[] memo, dp;
//	static {
//		memo = new long[10000];
//		memo[0] = 0;
//		memo[1] = 1;
//		미리 계산해서 한 번만 연산해놓을 수 있다. 	
//	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		memo = new long[n + 1];
		memo[1] = 1;
		dp = new long[n + 1];
		dp[1] = 1;

//		Arrays.fill(memo, -1);	//**** 이 코드를 이용했다면
//		memo[0] = 0;
//		memo[1] = 1;

		System.out.println(fibo1(n));
		System.out.println(callFibo1);
		System.out.println(fibo2(n));
		System.out.println(callFibo2);
		System.out.println(fibo3(n));
		System.out.println(callFibo3);

	}

	// 재귀함수를 이용한 피보나치
	public static long fibo1(int n) {
		callFibo1++; // -> 무수히 많은 중복 호출 존재
		if (n < 2)
			return n;
		return fibo1(n - 1) + fibo1(n - 2);
	}

	// 메모이제이션을 이용한 피보나치
	public static long fibo2(int n) {
		callFibo2++;
		if (n >= 2 && memo[n] == 0) {
			// if(memo[n]==-1) // **** 이렇게 조건문을 간략하게 가능
			memo[n] = fibo2(n - 1) + fibo2(n - 2);
		}
		return memo[n];
	}

	// 동적계획법 활용
	public static long fibo3(int n) {
		callFibo3++;
		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
}