다이나믹 프로그래밍 (2)

다이나믹 프로그래밍은 쉽게 말해 점화식이용하는 알고리즘이다.

점화식을 구하는 방법은 2가지가 있는데

탑다운 방식과 보텀업 방식이 있다.

 

탑다운 : 

-> 큰 문제를 해결하기 위해 작은 문제를 호출 한다.

public class Top_Down {
    static long d[] = new long[100];

    static long fibo(int x) {
        System.out.print("f(" + x + ')' + " ");
        if (x == 1 || x == 2) {
            return 1;
        }

        if (d[x] != 0) {
            return d[x];
        }

        d[x] = fibo(x-1) + fibo(x-2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(6));
    }
}

탑 다운 방식은 위 코드 처럼 동작한다.

탑 다운 방식은 다른 말로 메모이제이션이라고 부른다.

코드를 읽어 보면 일반적인 재귀와 비슷한 모습이 보인다.

하지만... 메모이제이션... 즉, 값이 저장 되는 부분이 존재한다.

현재 d[]라는 변수에 값들이 전달되고 있다.
만약, 아직 아무것도 들어 있지 않는다면, 피보나치 수열을 이용하여 값을 d[x]에 저장 시킨다. 
하지만, 이미 d[x]값에 값이 존재한다면...
그 값을 리턴해주는 방식이다.

즉, 배열안에 값이 존재하지 않는다면, 값을 넣어주고, 있다면 무시해주는 방식이 바로 탑다운
메모이제이션 방식이다.

 

바텀 업 방식 : 
 ->  작은 문제 부터 차근차근 답을 도출한다.

사실 처음에 말한 점화식과 유사한 방법이 바로 바텀 업과 더 가까운 것 같다.

public class Bottom_Up {
    static long d[] = new long[100];


    public static void main(String[] args) {
        d[1] = 1;
        d[2] = 1;
        int n = 99;

        for(int i = 3; i<=n;i++) {
            d[i] = d[i-1] + d[i-2];
        }
        System.out.println(d[n]);
    }
}

위 탑 다운과 달리, 반복문안에서 모든 것을 해결하려고 하고 있다.

피보나치가 전전 값과 전 값을 서로 더하는 방식으로 되어있다.

1 -> 1 ->  2 ->  3 ->  5 ->  8 -> 13 ... 이런식으로 진행된다.

 이걸 자세히 보면 3번째 부터 계산이 되는게 보여진다.

이런식으로 값을 계속 계산해주는 방식이 바텀업 방식이다.

또 바텀 업 방식에서 d는 dp테이블이라고 부른다.

 

사실 메모이제이션과 다이나믹 프로그래밍은 엄밀히 말하면 다르다고 한다.

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 개념이라고 한다.