[알고리즘] 동적 계획법, 분할정복

동적 계획법 (DP)

• 입력 크기가 작은 부분 문제들을 해결하고, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘이다.
• 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과를 이용해서 상위 문제를 풀어나감
• Memoization 기법을 사용해서 이전에 계산한 값을 저장, 재활용해서 실행 속도를 빠르게 한다.

public static int fibonacci(int n) {
    Integer[] memoization = new Integer[n + 1];
    memoization[0] = 0;
    memoization[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        memoization[i] = memoization[i - 1] + memoization[i - 2];
    }
    return memoization[n];
}

---

분할 정복

• 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀고 다시 합병해서 문제를 해결
• 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구함 (재귀)
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다.

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