[Algorithm] Dynamic Programming 1

Dynamic Programming

• 기존에 계산된 값을 버리지 않고 가지고 있다가
• 필요할때 다시 사용한다
• 중복계산을 줄일때 사용한다.

 

 

Memoization(Top-Down)

• 큰문제를 먼저 시도한뒤 안풀린 문제면 다시 작은 문제를 푼다.
• 재귀로 구현한다.
• 가독성이 증가한다
• 어렵다.
• 실재로 팔요한 문제 들만 푼다.

 

Dynamic Programmig(Bottom-Up)

• 작은문제를 먼저 풀어 나가는 방식이다.
• 반복문으로 구현한다.
• 가독성이 떨어진다.
• 비교적 쉽다.
• 모든 작은 문제들을 전부 구해야 한다.

 

 

Memoization 과 Dynamic Programmig 차이점?

• 사실 둘다 비슷하다 중간 결과를 저장해 다시 사용한다면 Memoization
• 하위문제를 풀어나가면서 큰 문제를 해결하면 DP

 

 

대표예제

• Fibonacci numbers 가 DP 의 가장 기초예제이다.
• Fibonacci numbers 는 1번째 와 2번째가 1 이고
• 나머지 수(n) 은 n-1 + n-2 값이 된다.

 

 

 

일반적인 피보나치 함수

코드

• 시간이 오래걸린다.
• 중복 계산이 들어가기 때문이다.

    public static int count = 0;

    public static int fibo(int n) {
        count++;
        if (n<=1) {
            return 1;
        }
        return fibo(n-1)+fibo(n-2);
    }

 

결과

재귀 함수가  15번 불러졌다.

fibo number: 8
Call Count: 15

 

 

어떻게 중복 계산이 발생 하는가?

• index 의 5번째 값 8을 구하기 위해 필요한 연산을 보자
• 색갈별로 칠한 부분이 다 중복으로 호춯된다.

 

 

Dynamic Programmig(Bottom-Up)

• 작은 문제 부터 풀어 나간다.

    public static int fiboDP(int n) {
        for(int i = 2; i<=n; i++) {
            count++;
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

 

 

 

Memoization(Top-Down) 적용

• 내가 제일 선호하는 방식이다.
• 가장큰 n 번째를 구한다.
• 답이 없으면 큰문제를 작은 문제로 나눠 해결한다.

 

코드

public static int count = 0;

public static int fiboMemo(int n) {
    count++;
    if (n <= 1) {
        return f[n];
    }

    if (f[n] != -1) {
        return f[n];
    }

    f[n] = fiboMemo(n-1) +fiboMemo(n-2);
    return f[n];
}

 

결과

재귀 함수가 9번 불러졌다.

fibo number: 8
Call Count: 9

 

 

생각해보기

험수 호출 횟수가 차이가 안난다고 생각이 들지도 모르겠다.

작은 수로 테스트를 해봐서 그렇다. 더 큰 문제로 비교를 해보자.

 

20번째 피보나치를 구해보자.

DP 적용 전

fibo number: 10946
Call Count: 21891

 

DP 적용 후 

fibo number: 10946
Call Count: 39

 

어마어마한 차이가 난다.

 

 

전체코드

package algorithm.dp;

import java.util.Arrays;

public class DynamicProgramming {

    public static int f[] = new int[256];
    public static int count = 0;

    public static int fibo(int n) {
        count++;
        if (n<=1) {
            return 1;
        }
        return fibo(n-1)+fibo(n-2);
    }

    public static int fiboMemo(int n) {
        count++;
        if (n <= 1) {
            return f[n];
        }

        if (f[n] != -1) {
            return f[n];
        }


        f[n] = fiboMemo(n-1) +fiboMemo(n-2);
        return f[n];
    }

    public static int fiboDP(int n) {
        for(int i = 2; i<=n; i++) {
            count++;
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

    public static void main(String[] args) {
        Arrays.fill(f,-1);
        f[0] = f[1] = 1;

        int result = fiboMemo(20);
        System.out.println("fibo number: " + result);
        System.out.println("Call Count: " + count);
    }
}