Dynamic Programming

Dynamic Programming

큰 문제를 작은 문제로 나누어 푸는 문제

 

 

Divide and Conquer ( 분할정복 ) 과 차이점

작은 문제가 중복되어 일어나는지 안일어나는지입니다.

 - 분할 정복 : 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법 ( 작은 문제에서 반복은 없음 )

 - 동적 프로그래밍 : 작은 문제들이 반복되는 것 ( 답은 바뀌지 않음 )

 

 

Dynamic Programming 방법

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

정답을 구한 작은 문제를 어딘가에 메모해놓고, 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면

메모한 작은 문제의 결과값을 이용합니다.

 

 

Dynamic Programming 조건

1) 작은 문제가 반복일 일어날 경우

2) 같은 문제는 구할 때마다 정답이 같음

 

 

Memoization ( 메모이제이션 )

작은 문제들이 반복되고, 이 작은 문제들의 결과값은 항상 같다는 점을 이용해 한번 계산한 작은 문제를 저장해놓고 다시 사용하는 것을 의미합니다. 피보나치로 예를 들 수 있습니다.

 

 

[ 피보나치 수열 예제 ]

피보나치는 1, 1, 2, 3, 5, 8 .. 의 수를 이루게 됩니다. 재귀로 풀게 될 경우 했던 작업을 또 해야하므로 일정 수 이상의 순열을 구하기가 어렵습니다.

 - 점화식 : [이전 수열] +  [두 단계 전 수열의 합]

 - DP 조건이 해당되는지 확인
     1) 작은 문제들이 반복된다.
         : F(5) = F(4) + F(3) , F(4) = F(3) + F(2) 로 F(3) 이라는 수열이 F(4), F(5) 에서 반복됩니다.
      2) 같은 문제를 구할때 마다 정답이 같다.
         : 첫번째, 두번째 수열은 각각 1로 고정되어 있습니다. 즉, 3번째 수열은 항상 결과가 2입니다. 그리고 4번째 수열은 3번째와 2번째 

           수열을 이용해 구하므로 언제나 정답이 같습니다.

 

public class fibonacci { 
    static long[] memo;
    public static int fibonacci_rec(int n) { // 재귀
        if (n <= 1) {
            return n;
        } else {
            return fibonacci_rec(n-1) + fibonacci_rec(n-2);
        }
    }

    public static long fibonacci_memoization(int n) { // 메모이제이션
        if (n <= 1) {
            return n;
        }
        else if(memo[n] != 0){
            return memo[n];
        }
        else {
            return memo[n] = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2);
        }
    }
    public static void main(String[] args) {
        memo = new long[10];
        System.out.println(fibonacci_rec(10));
        System.out.println(fibonacci_memoization(10));

    }
}

 

 

[ 재귀와의 차이점 ]

기존 재귀함수와는 다르게 이미 계산된 값을 Memo 라는 배열에 저장하여 사용한다는 차이점이 있습니다.

 

 

 

Bottom-up , Top-down

 

 1. Bottom-up

작은 문제부터 구해가는 방법입니다.

    public static int bottomUp(int n){
        int[] arr = new int[n];
        arr[0] = 0;
        arr[1] = 1;
        if(n==0) return arr[0];
        else if(n==1) return arr[1];
        else{
            for(int i=2; i<=n; i++){
                arr[i] = arr[i - 1] + arr[i - 2];
            }
            return arr[n];
        }
    }

 

 2. Top-down

 재귀함수로 구현하는 경우 대부분이 top-down이라고 생각하면 됩니다. 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게 됩니다.

 

 

* Top-down / Bottom-up 의 장점

 - Top-down : 소스의 가독성이 증대

 - Bottom-up : 풀기는 쉽지만 소스의 가독성이 안좋음