Algorithm - Dynamic Programming

 

Dynamic Programming

 

Dynamic Programming(동적계획법)이란?

하나의 큰 문제를 여러개의 작은 문제로 나누어 그 결과를 저장 후 다시 큰 문제를 해결할 때 사용하는 방법이다.

쉽게 말하면 "기억하며 풀기"이다.

재귀와 유사하지만 일반적인 재귀방식으로 연산할시 동일한 작은 문제들이 여러번 호출되어 비효율적이다.

 

재귀 - 피보나치 수열

재귀의 예시로 피보나치 수열에 대해 살펴보자

//재귀 방식으로 구현한 피보나치 수열
public class fibo {
    static int count=0;
    private static int fibona(int n){
        int result = 0;
        count++;
        if(n==0) return 0;
        if(n==1) return 1;
        return fibona(n-2) + fibona(n-1);
    }
    public static void main(String[] args) {
        System.out.println(fibona(6));
        System.out.println(count);
    }
}

/* 출력 결과
8
25
*/

이 경우 fibona(6)을 호출시 8의 결과를 얻기 위해 총 15번 메소드의 호출이 이루어졌다.

파라미터의 수가 6이었기에 25번 호출이 되었지만 파라미터가 커질수록 메소드의 호출횟수는 급격하게 늘어날 것이다

그 이유는 fibona 메소드의 시간복잡도는 n이 1증가할 때마다 2배씩 늘어나므로 O(2^n)이 된다.

 

Dynamic Programming 조건

DP를 적용하기 위해서는 조건이 필요하다

1.동일한 작은 문제들이 반복해서 나타나는 경우 사용 가능

2.부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

 

구현 방식

• Bottom-Up 방식 (Tabulation)
  • 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 (반복문)
  • 함수를 별도로 호출하지 않아 시간과 메모리를 더 절약할 수 있다.
• Top-Down 방식 (Memoization)
  • 위에서부터 바로 호출을 시작하여 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
  • 가독성이 좋으며 점화식을 이해하기 쉬움
  • DP는 기억하며 풀기이기 때문에 이 케이스에 해당한다

 

 

1. Memoization과 recursive를 성능,가독성 면에서 비교 분석해주세요
   그리고 피보나치 수를 구하는 함수를 DP와 recurve를 이용해서 각각 구현하고 아래를 테스트 해주세요
   => f(1),  f(100) f(10000)
     * 특이사항이 있다면 원인을 분석해주세요
     
public class fibo {
    static int count=0;
    static int[] dp = new int[100];
    private static int fibona(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        return fibona(n-2) + fibona(n-1);
    }

    private static int dpfibo(int n){
        if(n==1||n==2) return 1;
        if(dp[n]!=0) return dp[n];
        return dp[n] = dpfibo(n-1)+dpfibo(n-2);
    }
    public static void main(String[] args) {
        
        long beforeTime = System.currentTimeMillis();
        System.out.println(fibona(30));
        long afterTime = System.currentTimeMillis();
        System.out.println("시간차이: " +(afterTime - beforeTime));
        long before_Time = System.currentTimeMillis();
        System.out.println(dpfibo(30));
        long after_Time = System.currentTimeMillis();
        System.out.println("시간차이: " +(after_Time - before_Time));
    }
}