Dynamic Programming (동적 계획법)

Dp란?

 

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

 

(코딩테스트 단골 문제이며, 숫자의 범위가 크거나 경우의 수가 엄청 많은 문제들이 나올 때,

써야 하는 방법이다.)

 

 

Dp를 사용하는 이유

 

Dp는 재귀의 업그레이드 버전이라고 볼 수 있다.

동일한 함수를 다시 불러서 사용하는 건데, 다만 점화식 형태처럼 계산이 복잡하다.

그래서 수행해야 할 명령들이 기하급수적으로 늘어날 수 있다.

 

(ex. 피보나치 수를 계산하는 방법은 return f(n)=f(n-1)+f(n-2)이다. n이 100일 때를 구한다면

함수 호출 횟수는 엄청나게 많을 것이고, 약 90만년 정도가 소요된다.)

 

요약하면, 재귀를 응용하는 것보다 시간 복잡도를 낮출 좋은 방법이 Dp이다.

 

 

Dp의 조건

Dp가 적용되는 문제는 다음 두 특징을 가지고 있다.

 

1. 부분 반복 문제 (Overlapping Subproblem)

=> 동일한 작은 문제들이 나타나는 경우를 말한다. (ex. 피보나치 수열)

     피보나치 수열의 점화식은 f(n)=f(n-1)+f(n-2)이다.

     이와 같이 큰 문제를 쪼개서(함수 + 함수) 같은 형식(위에선 f라는 함수)의 부분 문제를 만들 수 있는 것을 말한다.

 

요약하자면, 문제를 쪼개서 같은 형식의 부분 문제를 .만들 수 있는 것.

 

2. 최적 부분 구조 (Optimal Substructure)

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

     큰 문제를 두 개로 쪼개서 각각 최적의 결과 값을 구했다고 가정하자.

     그러면 큰 문제를 해결할 때도 다른 결과 값이 아닌 두 문제의 최적의 결과값을 이용하여

     큰 문제의 최적의 결과 값을 나타낼 수 있어야 한다.

 

요약하자면, 쪼갠 거의 결과들 사용하여 큰 문제를 해결함.

 

 

Dp의 방법

1. 큰 문제를 작은 문제로 쪼갠다.

2. 작은 문제들의 답을 어딘가에 저장한다.

3. 점점 큰 문제를 풀어나가며 큰 문제들을 풀 때 저장했던 작은 문제의 답들을 불러 사용한다.

 

 

구현하는 방법은 크게 두 가지이다.

 

1. Bottom-Up 방식

아래에서 위로 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

기저 상태에서 시작한다. (기저 상태란 바닥 상태)

여기서 초깃값들은 미리 배열에다가 저장해준다.

뒤의 결과값들을 배열에다가 저장하고, 다음값을 구하는 데 사용한다.

 

    // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
    public static int bottomUp(int n){
        // 기저 상태의 경우 사전에 미리 저장
        bottomup_table[0] = 0; bottomup_table[1] = 1;
        
        // 반복문을 사용하고 있음!
        for(int i=2; i<=n; i++){
            // Table을 채워나감!
            bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
        }
        return bottomup_table[n];
    }

 

2. Top-Down 방식

Bottom-Up 방식과 달리, 위에서부터 아래로 가는 방식이다.

가장 아래 상태(기저 상태) 도달 시, 초기화해주는 명령을 짜준다.

재귀를 사용하데, 저장된 값이 있으면 바로 반환할 수 있도록 짜준다.

 

    // DP Top-Down을 사용해 Fibonacci를 구하는 경우
    public static int topDown(int n){
        // 기저 상태 도달 시, 0, 1로 초기화
        if(n < 2) return topDown_memo[n] = n;
        
        // 메모에 계산된 값이 있으면 바로 반환!
        if(topDown_memo[n] > 0) return topDown_memo[n];
        
        // 재귀를 사용하고 있음!
        topDown_memo[n] = topDown(n-1) + topDown(n-2);
        
        return topDown_memo[n];
    }

 

코드 출처 : https://hongjw1938.tistory.com/47