6강. 동적 계획법과 분할 정복

6. 동적 계획법과 분할 정복

---

6.1 동적 계획법의 기초

동적 계획법(Dynamic Programming)
동적 계획법은 1950년대에 리처드 벨먼(Richard Bellman)이 개발한 알고리즘 기법으로, 복잡한 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. 하위 문제의 해결 결과를 저장하여 같은 문제를 반복해서 풀지 않도록 하여 효율성을 높입니다.

동적 계획법의 시간 복잡도:
- 동적 계획법의 시간 복잡도는 일반적으로 문제의 크기와 하위 문제의 수에 따라 다르며, 중복 계산을 피하기 때문에 재귀적인 접근 방식보다 효율적입니다.

동적 계획법은 주로 최적화 문제에서 사용되며, 예제 문제로는 피보나치 수열, 배낭 문제 등이 있습니다. 이 기법은 "한 번 계산한 것은 다시 계산하지 않는다"는 원칙을 따릅니다.

// 피보나치 수열 - 동적 계획법 예시
public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n <= 1) // 기본 조건: n이 0 또는 1이면 n 반환
            return n;

        int[] fib = new int[n + 1]; // 결과 저장을 위한 배열 선언
        fib[0] = 0; // 피보나치 수열의 첫 번째 값
        fib[1] = 1; // 피보나치 수열의 두 번째 값

        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2]; // 이전 두 값을 더하여 현재 값을 계산
        }

        return fib[n]; // n번째 피보나치 수 반환
    }

    public static void main(String[] args) {
        int n = 10; // 예제 입력
        System.out.println("Fibonacci number is " + fibonacci(n));
    }
}

이 코드에서 우리는 피보나치 수열의 값을 계산하기 위해 동적 계획법을 사용합니다. 배열 `fib`는 중간 결과를 저장하여 동일한 계산을 반복하지 않도록 합니다.

 

6.2 메모이제이션 기법

메모이제이션(Memoization)
메모이제이션은 동적 계획법의 한 기법으로, 이미 계산한 하위 문제의 결과를 메모리(배열, 해시맵 등)에 저장하여 동일한 계산을 반복하지 않도록 하는 방법입니다. 이 기법은 주로 재귀적인 접근 방식에서 사용됩니다.

메모이제이션의 시간 복잡도:
- 메모이제이션의 시간 복잡도는 일반적으로 \(O(n)\)으로, 각 하위 문제를 한 번만 계산하기 때문에 효율적입니다.

메모이제이션은 주로 재귀적인 접근 방식에서 사용되며, 예제 문제로는 피보나치 수열, 최단 경로 문제 등이 있습니다. 메모이제이션은 동적 계획법의 "톱다운" 접근 방식으로 간주됩니다.

// 피보나치 수열 - 메모이제이션 예시
import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoization {
    private static Map<Integer, Integer> memo = new HashMap<>(); // 중간 결과를 저장할 해시맵

    public static int fibonacci(int n) {
        if (n <= 1) // 기본 조건: n이 0 또는 1이면 n 반환
            return n;

        if (memo.containsKey(n)) // 이미 계산된 값이 있으면 반환
            return memo.get(n);

        int result = fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출로 피보나치 계산
        memo.put(n, result); // 결과를 해시맵에 저장

        return result; // n번째 피보나치 수 반환
    }

    public static void main(String[] args) {
        int n = 10; // 예제 입력
        System.out.println("Fibonacci number is " + fibonacci(n));
    }
}

이 코드에서 우리는 재귀 호출을 사용하여 피보나치 수열을 계산하고, 중간 결과를 해시맵 `memo`에 저장하여 동일한 계산을 반복하지 않도록 합니다.

 

6.3 대표적인 동적 계획법 문제

대표적인 동적 계획법 문제
동적 계획법은 여러 문제에 적용될 수 있습니다. 대표적인 문제로는 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS), 최소 편집 거리 등이 있습니다.
아래는 배낭 문제의 예시입니다. 배낭 문제는 제한된 무게 내에서 최대의 가치를 얻을 수 있도록 물건을 선택하는 문제입니다.

// 배낭 문제 예시
public class Knapsack {
    public static int knapsack(int W, int[] weights, int[] values, int n) {
        int[][] K = new int[n + 1][W + 1]; // 결과 저장을 위한 2차원 배열 선언

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0; // 기본 조건: 물건이 없거나 배낭의 무게가 0이면 가치도 0
                else if (weights[i - 1] <= w)
                    K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]); // 물건을 넣는 경우와 넣지 않는 경우 중 최대값 선택
                else
                    K[i][w] = K[i - 1][w]; // 물건을 넣을 수 없는 경우
            }
        }

        return K[n][W]; // 최대 가치 반환
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120}; // 물건의 가치
        int[] weights = {10, 20, 30}; // 물건의 무게
        int W = 50; // 배낭의 최대 무게
        int n = values.length; // 물건의 개수
        System.out.println("Maximum value in Knapsack = " + knapsack(W, weights, values, n));
    }
}

이 코드에서 우리는 배낭 문제를 해결하기 위해 동적 계획법을 사용합니다. 2차원 배열 `K`는 중간 결과를 저장하여 동일한 계산을 반복하지 않도록 합니다.

6.4 분할 정복 기법

분할 정복(Divide and Conquer)
분할 정복은 문제를 작은 하위 문제로 분할하고, 각각을 독립적으로 해결한 후, 결과를 합쳐서 원래 문제를 해결하는 기법입니다. 이 기법은 문제를 재귀적으로 해결하는 방식으로 많이 사용됩니다.

분할 정복의 시간 복잡도:
- 분할 정복의 시간 복잡도는 문제의 분할과 병합 단계의 복잡도에 따라 다르며, 일반적으로 로그 스케일의 시간 복잡도를 가집니다.

대표적인 분할 정복 알고리즘으로는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 검색(Binary Search) 등이 있습니다. 이 기법은 "큰 문제를 작은 문제로 나누어 푼다"는 원칙을 따릅니다.

// 병합 정렬 - 분할 정복 예시
import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2; // 중간 인덱스 계산
            mergeSort(arr, left, middle); // 왼쪽 절반 정렬
            mergeSort(arr, middle + 1, right); // 오른쪽 절반 정렬
            merge(arr, left, middle, right); // 정렬된 두 부분 병합
        }
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] L = new int[n1]; // 왼쪽 부분 배열
        int[] R = new int[n2]; // 오른쪽 부분 배열

        for (int i = 0; i < n1; ++i)
                        L[i] = arr[left + i]; // 왼쪽 부분 배열에 값 저장
        for (int j = 0; j < n2; ++j)
            R[j] = arr[middle + 1 + j]; // 오른쪽 부분 배열에 값 저장

        int i = 0, j = 0; // 두 배열의 시작 인덱스 초기화
        int k = left; // 병합된 배열의 시작 인덱스 초기화
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i]; // 작은 값을 병합된 배열에 저장
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i]; // 왼쪽 배열의 나머지 값 저장
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j]; // 오른쪽 배열의 나머지 값 저장
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7}; // 예제 배열
        System.out.println("Given Array");
        System.out.println(Arrays.toString(arr));

        mergeSort(arr, 0, arr.length - 1); // 병합 정렬 수행

        System.out.println("\nSorted array");
        System.out.println(Arrays.toString(arr));
    }
}

이 코드에서 우리는 병합 정렬을 사용하여 배열을 정렬합니다. 병합 정렬은 배열을 재귀적으로 분할한 후, 정렬된 두 부분 배열을 병합하여 원래 배열을 정렬합니다.