동적계획법(Dynamic Programming, DP)

 

1. Dynamic Programming(동적계획법)이란?

큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말,

작은 부분문제들이 반복되는 것(답이 바뀌지 않음)을 이용해 풀어나가는 방법

 

1-2. DP 방법

: 모든 작은 문제들은 한번만 풀어야 한다.

정답을 구한 작은 문제를 어디엔가 메모해놓는다.

다시 그 보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

 

1-3. DP의 조건

•  최적 부분 구조(Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
• 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다.

 

1-4. Memoization 

: 다이나믹프로그래밍에서는 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다. 이 점을 이용하여 한번 계산한 작은 문제 결과값을 저장해놓고 다시 사용한다. 이 것을 Memoization 이라 한다.

 

ex) 피보나치 수열

1, 1, 2, 3, 5, 8, ...

: 다음 수열 = 이전 수열 + 두단계 전 수열의 합

p(a) = p(a-1)+p(a-2)

 

* 재귀함수로 구현

- 메모이제이션을 사용하지 않음

- 같은 함수를 계속해서 중복 호출

=> 시간복잡도 O(2^n) => 효율 떨어짐

public class Simple {

	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 x) {
		if( x ==1 || x==2) return 1;
		return fibo(x-1) + fibo(x-2);
	}
}

 

 

* Memoization(DP) 로 구현

• Top-down(하향식) : 상위문제를 해결하기 위해 하위 문제를 재귀적으로 호출하여 하위 문제를 해결함으로써 상위문제를 해결하는 방식, 이 때 해결해놓은 하위 문제를 저장해 놓기 위해 memoization 이 사용된다.

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));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		if(dp[x] != 0) return dp[x];
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

 

* Bottom-up(상향식) : 하위부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식, DP의 전형적인 형태, 여기서 사용되는 문제결과 값 저장 리스트는 DP 테이블이라 부른다. 

- 반복문을 사용해서 구현한다.

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));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}
}