[ALGORITHM] Dynamic programming / 동적 계획법

👌 동적 계획법. 

 

핵심은 top down / bottom up 방식에서 중복되는 연산을 피하는 것.

-> O(2^n)의 시간복잡도를 가지게 될 경우 ( 재귀 함수 )

-> 연산의 횟수가 늘어난다.

-> 콜 스택이 많이 늘어나므로 성능이 안좋아진다.

 

성능뿐만이 아닌 한계점까지 갈 경우 에러도 발생한다. 

 

https://loosie.tistory.com/150

 

이미 연산을 한 과정을 다시 연산하는 부분이 생겨난다.

 

 

 

 

😔 피보나치 수열로 예시를 많이 든다. 

 

앞 + 앞의 앞 = 다음 항을 결정

 

public class pbnc {

    public static void main(String[] args) {

        int n = 10;

    }

    // 반복되는 연산을 고려하지 않음.
    static int ffibo1( int x ) {
        if (x == 1 || x== 2) {
            return 1;
        }

        return ffibo1(x-1) + ffibo1(x -2);
    }
}

 

 

 

 

 

 

반복되는 연산을 피하고 싶다면, 한번 연산한 값은 연산없이 쓸 수 있게 기억하고 있으면 된다. 

 

따라서, 이미 앞서 연산한 과정은 메모이제이션을 통해 연산을 생략 할 수 있다. 

 

🤢 메모이 제이션 ==> 연산한 결과 ( 한 번 계산한 결과 ) 를 메모리 공간에 메모 하는 것.

 

 

static int memoFibo(int x) {
    if (x == 1 || x == 2) {
        return 1;
    }

    // 배열 dp[x]가 연산한 적이 있다면,
    if (dp[x] != 0) {
        return dp[x]; // 연산 했던 값 (메모제이션 값) 을 리턴한다.
    }

    // 연산 한 적이 없다면 연산해서 메모제이션 처리.
    dp[x] = memoFibo(x-1) + memoFibo(x-2);
    return dp[x];
}

 

 

위 방식은 다음과 같은 그림에 해당한다.

 

 

https://loosie.tistory.com/150

 

 

 

 

 

 

이런 메모제이션을 구현해서 동적 계획법을 구상하는 방법은 크게 top down(재귀)  / bottom up(for-loop) 방식이  있다.

 

재귀는 위의 방식과 동일하므로 생략하고 bottom up 방식은 다음과 같다. 

 

    static int bottomUpForLoop(int j ) {

        // 10번 연산하고 싶다면,
        int n = 10;

        dp[0] = 1;
        dp[1] = 1;

        int k = n;

        for (int i=0; i<n; i++) {
            if (dp[i]==null) { //배열 값이 없을 경우만 연산.
                dp[i]=dp[i-1]+dp[i-2];
            }
        }
       return dp[n];
    }

 

 

끝.

 

 

 

 

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수