Divide and Conquer vs. Dynamic Programming

Divide and Conquer와 Dynamic Programming은 둘 다 문제를 작은 하위 문제로 나누어 해결하는 방식이지만, 근본적으로 해결 방식과 적용 상황에서 차이가 있습니다.

1. Divide and Conquer (분할 정복)

핵심 아이디어:

• 문제를 더 작은 하위 문제로 나누어 각각을 재귀적으로 해결한 다음, 결과를 결합하여 원래 문제를 해결하는 방식입니다.
• 각 하위 문제는 독립적으로 해결됩니다.

특징:

• 문제를 재귀적으로 쪼개고, 각 하위 문제를 해결한 후 결합하여 최종 결과를 얻습니다.
• 하위 문제들이 서로 중복되지 않음. 즉, 같은 하위 문제를 여러 번 계산하지 않음.
• 대표적인 예: Merge Sort (O(n log n)), Quick Sort (O(n log n)), Binary Search (O(log n)).

예시 (Merge Sort):

• 배열을 반으로 나누어 각각을 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬합니다.

단계:

1. 문제를 하위 문제로 나눔.
2. 하위 문제를 독립적으로 해결.
3. 하위 문제들의 해를 결합하여 전체 문제 해결.

장점:

• 문제를 나눔으로써 큰 문제를 쉽게 해결 가능.

단점:

• 일부 경우에는 중복된 계산이 많아 비효율적일 수 있음.

2. Dynamic Programming (동적 계획법)

핵심 아이디어:

• 큰 문제를 작은 하위 문제로 나누되, 중복되는 하위 문제를 반복 계산하지 않고 메모이제이션(결과 저장)을 통해 효율적으로 해결하는 방식입니다.

특징:

• 하위 문제들이 중복될 수 있어, 한 번 계산한 하위 문제의 결과를 저장해두고 재사용하여 성능을 향상시킴.
• 두 가지 주요 기법이 있음:
  1. 탑다운 (Top-Down) 방식: 재귀적 접근, 메모이제이션(Memoization) 사용.
  2. 바텀업 (Bottom-Up) 방식: 작은 문제부터 해결하여 점차 큰 문제로 확장.
• 대표적인 예: 피보나치 수열 계산 (O(n)), 최장 공통 부분 수열(LCS), 최단 경로 알고리즘 (다익스트라).

예시 (피보나치 수열):

• 일반적으로 피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의됩니다. 단순 재귀를 사용하면 F(n-1)과 F(n-2)를 반복해서 계산하므로, 동적 계획법을 사용해 계산된 값을 저장하고 재사용합니다.

단계:

1. 문제를 작은 하위 문제로 나눔.
2. 각 하위 문제의 해를 저장.
3. 저장된 값을 활용해 최종 문제를 해결.

장점:

• 중복된 계산을 피함으로써 성능이 크게 향상됨.

단점:

• 모든 하위 문제의 결과를 저장해야 하므로 메모리 사용이 증가할 수 있음.

Divide and Conquer vs Dynamic Programming 차이점

구분	Divide and Conquer	Dynamic Programming
하위 문제의 중복	하위 문제들이 중복되지 않음	하위 문제들이 중복될 수 있음, 이를 메모이제이션으로 해결
문제 해결 방식	문제를 독립적인 하위 문제로 나눠 해결	하위 문제의 결과를 저장하고 재사용
문제 합치는 방식	각 하위 문제의 결과를 합쳐서 해결	하위 문제들의 결과를 이용해 큰 문제를 해결
적용되는 문제의 유형	독립적인 하위 문제로 나눌 수 있는 문제	중복된 하위 문제가 발생하는 문제
대표적인 알고리즘	Merge Sort, Quick Sort, Binary Search	피보나치 수열, LCS, Knapsack Problem, 다익스트라
시간 복잡도	보통 O(n log n) 또는 그 이상	메모이제이션 덕분에 중복 계산을 피할 수 있어 O(n) 수준으로 낮출 수 있음

예시로 보는 차이

1. 피보나치 수열 문제

• Divide and Conquer 방식으로 풀면 F(n) = F(n-1) + F(n-2)로 재귀적으로 나누어 해결하는데, 중복 계산이 발생해 비효율적입니다.

// Divide and Conquer 방식의 피보나치 수열
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 중복된 계산이 많음
}

• Dynamic Programming으로 해결하면 한 번 계산한 값을 저장해 두고 재사용하여 훨씬 더 효율적입니다.

// Dynamic Programming 방식의 피보나치 수열
int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // 저장된 값을 재사용
    }
    return dp[n];
}

2. 최대 부분 배열 합 문제 (Maximum Subarray Sum)

• Divide and Conquer 방식: 배열을 중간에서 나누어 좌우로 최대 부분 배열을 찾고, 중간을 가로지르는 부분도 고려합니다. 시간 복잡도는 O(n log n)입니다.

• Dynamic Programming (Kadane's Algorithm): 배열을 한 번 순회하며 최대 부분 배열 합을 계산하는 O(n) 알고리즘입니다.

// Dynamic Programming 방식의 최대 부분 배열 합 (Kadane's Algorithm)
int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

결론:

• Divide and Conquer는 독립적인 하위 문제로 문제를 나누어 해결하는 방식으로, 주로 하위 문제들이 중복되지 않는 경우에 사용됩니다.
• Dynamic Programming은 중복되는 하위 문제를 해결하고 그 결과를 재사용하는 방식으로, 중복 계산을 피하는 것이 중요한 문제에 사용됩니다.