[동적계획법] Top-down과 Bottom-up

Top-down과 Bottom-up의 공통적인 특징

- 다음 상태를 구하기 위해, 이전 상태를 저장하고 재사용합니다. (Memoization)

- 무엇을 어떻게 저장할지 정하는 것이 중요합니다. 만약, 2차원 배열이라고 한다면, x축과 y축, 배열에 저장되는 값 이렇게 3가지를 어떤 대상으로 정의할 것인지 파악해야 합니다.

- 이를 위해 정확한 문제 해석과 반복문에서 배열의 인덱스에 어떤 값을 입력해야 하는지 정해야 합니다.

 

적용 순서

1. 상태 정의: DP배열의 index가 의미하는 것과 문제의 초기상태 정의

2. 점화식 구하기: 다음 상태를 나타내기 위한 표현식

3. 시간복잡도 계산

 

 

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

Top-down

- 재귀함수와 Memoization 활용 (Python에서는 시간초과가 발생할 가능성이 있다고 합니다.)

- 큰 문제를 작은 문제로 나눠서 풀고, 마지막에 큰 문제를 풀어나가는 순서입니다.

 

public int top_down(int num) {
    if(num == 1) return 0;
 
    if(dp[num] > 0) return dp[num];

    
    dp[num] = top_down(num-1) + 1;
    if(num%3 == 0) {
    	int cnt = top_down(num/3) + 1;
        if(dp[num] > cnt) dp[num] = cnt;
    }
    
    if(num%2 == 0) {
    	int cnt = top_down(num/2) + 1;
        if(dp[num] > cnt) dp[num] = cnt;
    }
    
    return dp[num];
}

 해당 문제는 주어진 N값을 1로 만드는데 최소한의 연산 횟수를 구하는 것이다.

1. N이 3으로 나누어 떨어지면 N = N/3

2. N이 2로 나누어 떨어지면 N = N/2

3. 만약, 둘다 안돼면 N = N-1

 dp배열에 3개의 연산에 따른 재귀호출의 결과를 저장합니다. 또한, 조건문을 통해 매번 최소 연산 횟수를 찾아 dp 배열에 저장하는 형태입니다. 

 

 

Bottom-up

- 반복문과 Memoization 활용

- 문제를 크기가 작은 부분부터 차례대로 풀면서, 크기를 조금씩 키워나가는 형식.

 

public void bottom_up() {
    int cnt = 0;
    int[] dp = new int[N+1];

    for(int i=2; i<N+1; i++) {
        cnt = MAX;

        if(i%3 == 0) {
            cnt = dp[i/3];
        }

        if(i%2 == 0 && cnt > dp[i/2]) {
            cnt = dp[i/2];
        }

        if(cnt > dp[i-1]) {
            cnt = dp[i-1];
        }

        dp[i] = cnt+1;
    }
}

 반복문을 통해 i를 2부터 N까지 순회합니다. 매번 3개의 조건문이 참인 경우, 이전에 저장된 값을 cnt에 저장합니다. 대신, 2번째 조건문부터는 이전에 저장된 cnt와 dp[x]와 비교하며 최종적으로 최소 연산 횟수를 dp배열에 저장하게 됩니다.