동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)

1. 정의

• 동적계획법 (DP)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함
    • Memoization : 프로그램 실행 시 이전 계산 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현한다.
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다.
    • 예 : 병합정렬, 퀵 정렬 등

 

2. 공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용 안함

 

3. 동적 계획법 알고리즘 이해 : 피보나치 수열

 

fib(4) 를 구할 경우, fib(3), fib(2)로 쪼개지고 최하위까지 계속 쪼개진다.

분할정복과 다른 점은 fib(0), fib(1), fib(2) 가 중복이 된다.

즉, 여러가지 부분 문제들이 중복된다.

 

• Recursive Call

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

 

• DP

public static int fibo_dp(int num) {

    // Memoization
    int[] cache = new int[num + 1];
    cache[0] = 0;
    cache[1] = 1;

    for (int index = 2; index < cache.length; index++) {
        cache[index] = cache[index - 1] + cache[index - 2];
    }
    return cache[num];
}

 

4. DP 풀이 전략

1. 빈 리스트 만들기 (입력값에 따른)

2. 초기값을 설정

3. 점화식 기반으로 계산값 적용하기

4. 특정 입력값에 따른 계산값을 리스트에서 추출하기

 

• 코드 (백준 11726. 2xn 타일링)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 1. 빈 리스트 만들기 (입력값이 최대 1000이므로 1001개의 크기의 배열을 생성)
        int[] dp = new int[1001];

        // 2. 초기값 설정 -> 직접 구해보면 쉽게 찾을 수 있음.
        dp[1] = 1;
        dp[2] = 2;

        // 3. 점화식 기반 계산값 적용
        for (int index = 3; index < 1001; index++) {
            dp[index] = dp[index - 1] + dp[index - 2];
        }

        // 4. 특정 입력값에 따른 계산값을 리스트에서 추출
        System.out.println(dp[n] % 10007);
    }
}