동적계획법 (Dynamic Programming)

1. 정의

 - 복잡한 문제를 여러 개의 작은 부분 문제(Sub-Problem)로 나누어 해결하는 방법

 - 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위

 문제를 풀어가는 방식

 

2. Top-down

 - 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 

 하는 기술

 - 여러 개의 하위 문제(sub-problem) 나눴을시에 하위 문제를 결합하여 최종적으로 최적해를 구한다

 - 같은 하위 문제를 가지고 있는 경우가 존재한다. 그 최적해를 저장해서 사용하는 경우 하위 문제수가 기하급수적으로 증가할 때 유용하다. 위 방법을 memoization 이라고 한다.

 

3. bottom-up

 - 하위 문제들로 상위 문제의 최적해를 구한다.

 

 

EX) (백준 1003번 피보나치 문제 풀이)

package recursion;

import java.util.Scanner;

public class Fibonacci2_1 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt(); //테스트 케이스의 개수
		int[][] f = new int[41][2];
		f[0][0] = 1;
		f[1][1] = 1;
		for (int i = 2; i <41; i++) {
			for(int j = 0; j < 2; j++) {
				f[i][j] = f[i-1][j] + f[i -2][j];
			}
		}
		
		for(int i = 0; i < num; i++) {
			int a = sc.nextInt(); //테스트 하고 싶은 n번째 수 
			System.out.println(f[a][0]+" " +f[a][1]);
		}
		
		sc.close();
	}
}

 

 

* 참고

동적계획법 정리https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Algorithm#%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%A5%BC-%EC%9C%84%ED%95%9C-tip