[Algorithm] DP(Dynamic Programming) / 동적 프로그래밍이란?

DP(Dynamic Programming) 이란?

동적 프로그래밍이라고도 불리는 동적 계획법은 분할 정복 기법과 굉장히 유사하다.

 

분할 정복 기법이란, 알고리즘을 짤 때 큰 문제를 한 번에 해결하지 않고 작은 여러 개의 문제로 나누어서 푸는 기법이다. 이렇게 풀다보면 같은 문제를 반복적으로 풀게되는데, 이를 매번 재계산하지 않고, 값을 저장해두었다가 재사용하는 기법이 바로 동적 계획법이다.

 

동적 계획법의 종류

Top-down 

- 하향식 계산법

- 큰문제부터 시작해 작은 문제로 분할

- 메모제이션 : 동일한 계산을 반복해야 할 경우, 한 번 계산한 결과를 메모리에 저장해두었다가 꺼내씀으롰 중복계산방지를 할 수 있게 하는 기법으로, 동적 계획법의 핵심 기술이다. 즉, 메모리라는 공간비용을 늘림으로써 계산에 소요되는 시간비용)시간복잡도 O(N))을 낮춘다.

Bottom-up

- 상향식 계산법

- 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰문제를 품

- 성능이 더 좋은 경우가 많음

 

 

예를 들어 백준 1463번, 1로 만들기 문제를 위의 두 가지 방식으로 각각 풀어본다면, 저장된 값, 즉 구한적이 없을 때 큰 문제를 작은 문제로 분할하는 방식이 Top-down 방식이고,  작은 문제부터 시작해서 차례대로 구하는 방식이 bottom-up 방식이다.

import java.util.Scanner;

public class bj1463 {
	static int[] C; // 최소연산횟수 저장해놓는 배열 
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(); // 정수입력받음
		
		C = new int[n+1]; // 배열크기 지정
		
		System.out.println(Topdown(n));
        System.out.println(Bottomup(n));
		s.close();
		
	}
    
    // 1. Top-down
	public static int Topdown(int n){
		if (n==1) return 0;
		if (C[n]!=0) return C[n]; // 메모리에 저장된 값 있으면 그 값 리턴
        // 없을 시 작은 문제로 분할
		C[n] = Topdown(n-1)+1;
		if(n%2==0) C[n] = Math.min(C[n], Topdown(n/2)+1);
		if(n%3==0) C[n] = Math.min(C[n], Topdown(n/3)+1);
		return C[n];
	}
    
     // 2. Bottom-up
 	 public static int Bottomup(int n){
		if (n==1) return 0;
		if (C[n]!=0) return C[n]; // 전에 구한 적 있을 때
        // 없다면 작은 문제부터 시작해서 구함
		for(int i=2; i<=n;i++) {
			C[i] = Bottomup(i-1)+1;
			if(n%2==0) C[i] = Math.min(C[i], Bottomup(i/2)+1);
			if(n%3==0) C[i] = Math.min(C[i], Bottomup(i/3)+1);
		}
		return C[n];
	}
}