Dynamic Programming (동적 계획법)

Dynamic Progamming 이란?

• 알고리즘에서의 '동적'은 별 의미가 없다. '기억하기'로 생각하면 편하다.
• '프로그래밍'은 '테이블을 만든다'는 뜻이라고 생각하면 됨.

중복되는 문제

• 피보나치 수열 코딩 시, F(n) = F(n-1) + F(n-2) 이기 때문에 단순 재귀 함수로 구현하면..

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);
	}
}

• 위 코드와 같이 메모이제이션을 사용하지 않으면, 같은 함수를 중복 호출하기 때문에
  재귀 함수로 구현하면 시간 복잡도 O(2^N)을 갖는다.
• 중복되는 호출로 인해 굉장히 좋지 않은 효율을 갖는다.

DP 문제가 성립할 조건

1. 최적 부분 구조 (Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다! ( 겨수님 : "작은 문제의 답들 사이의 관계.. ")
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

피보나치 수열은 DP 사용 조건에 만족한다.

 

DP 알고리즘 기법은 무엇인가?

• DP 알고리즘 기법은 이미 계산된 (하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써, 
  메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
• DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.

 

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));
        }
        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 BottodmUp {
	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));
		
	}
    
    
    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];
    }
}

 

 

Memoization

• 메모이제이션은 DP 구현 방법 중의 하나로, 한번 계산된 결과를 메모리 공간에 메모하는 기법이다.
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록한다는 부분에서 캐싱이라고도 함.
• DP에만 국한된 개념이 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP 가 아닌 다른 방식으로 사용될 수 있다.

 

[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)