동적계획법 (Dynamic Programing) 알고리즘

동적계획법 (Dynamic Programing) 알고리즘 - DP

 

 

동적계획법 (Dynamic Programing) 알고리즘 - DP

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

 

메모제이션 기법

모든 작은 문제들은 한번만 계산해 DP 테이블에 저장하여 추후 재사용할 때는 이 DP테이블을 이용한다.

 

동적계획법의 가장 대표적인 문제 -> 피보나치 수열

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

 

예를들어

 

F(2) = F(0) + F(1) = 0 + 1 = 1

F(3) = F(1) + F(2) = 1 + 1 = 2

F(4) = F(2) + F(3) = 1 + 2 = 3

F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

 

대표사진 삭제

※ 출처 인프런 강의 (Do it! 알고리즘 코딩테스트 with JAVA)

F[5]를 구해야한다면 F[4]와 F[3]이 필요하다.

F[4]를 구해야한다면 F[3]와 F[2]이 필요하다.

F[3]를 구해야한다면 F[2]와 F[1]이 필요하다.

F[2]를 구해야한다면 F[1]와 F[0]이 필요하다.

 

동적계획법 구현하는 첫번째 방식 : 톱-다운 방식

public class P2747_TopDown {
static int[] D;
public static void main(String[] args) {
// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	D = new int[n + 1];
	for (int i = 0; i <= n; i++) {
	D[i] = -1;

	D[0] = 0;
	D[1] = 1;
	fibo(n);
	System.out.println(D[n]);

static int fibo(int n) {
	if (D[n] != -1) // 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴
	return D[n];
	return D[n] = fibo(n - 2) + fibo(n - 1);
	// 메모이제이션: 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴하도록 로직을 구현

 

 

동적계획법 구현는 두번째 방식 : 바텀-업 방식

public class P2747_TopDown {
static int[] D;
public static void main(String[] args) {
// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	int n = sc.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];

	System.out.printin(D[n]);
 }
}

 

 

톱-다운 방식은 재귀함수의 형태로 되어 있기 때문에 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.

따라서 톱-다운 방식보다는 바텀-업 방식이 좀 더 안전하다고 볼 수 있다.