[알고리즘] 문제 해결 패턴 - 기본: Divied and Conquer

3. Divied and Conquer

분할 정복(Divide and Conquer)"은 어려운 문제를 해결하기 위해 문제를 더 작은 부분으로 나누고, 나눠진 부분을 각각(재귀적으로) 해결하여 원래 문제의 해답을 얻는 알고리즘 디자인 패러다임입니다. 이 패러다임은 문제를 작은 부분으로 쪼개서 해결하는 것을 강조

가장 대표적인 예로 “Binary Search”가 있습니다. 이 외에도 Merge Sort(병합 정렬), Quick Sort(퀵 정렬), Binary Search(이진 검색) 등이 있습니다.

 

일반적으로 "분할", "정복", "결합" 단계로 구성됩니다.

 

• 분할(Divide): 복잡한 문제를 해결하기 쉬운 작은 부분으로 나눕니다. 이 단계에서는 문제를 더 작은 부분으로 분해하고, 각 부분에 대한 해법을 찾습니다.
• 정복(Conquer): 나눈 작은 부분 문제들을 각각 해결합니다. 이 단계에서는 작은 부분 문제들을 재귀적으로 해결하거나 다른 알고리즘을 사용하여 해결합니다.
• 결합(Combine): 작은 부분 문제들의 해답을 결합하여 원래 문제의 해답을 얻습니다. 이 단계에서는 작은 부분 문제들의 결과를 합치거나 조합하여 원래 문제의 해답을 얻습니다.

 

대표적인 문제 예시

LeetCode - Maximum Subarray

: 주어진 정수 배열에서 연속된 부분 배열 중 가장 큰 합을 구하는 문제입니다.

data example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] 

data example 2
Input: nums = [1]
Output: 1

data example 3
Input: nums = [5,4,-1,7,8]
Output: 23

data example 4
Input: nums = [-1]
Output: -1

 

Bad Solution : O(n^2)

하나의 접근 방법은 모든 가능한 부분 배열의 합을 구하고, 그 중 가장 큰 값을 찾는 것입니다. 하지만 이렇게 하면 시간 복잡도가 O(n^2)가 됩니다.

function maxSubArrayBad(nums) {
    let maxSum = -Infinity;
    for (let start = 0; start < nums.length; start++) {
        let sum = 0;
        for (let end = start; end < nums.length; end++) {
            sum += nums[end];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

 

알고리즘 적용 : O(n logn)

분할 정복 알고리즘을 활용하여 문제를 효율적으로 풀 수 있습니다. 배열을 반으로 나누어 왼쪽, 오른쪽, 중앙을 고려하여 부분 배열의 최대 합을 구하고 이를 합쳐서 전체 최대 합을 찾습니다

function maxSubArray(nums) {
    if (nums.length === 1) {
        return nums[0];
    }

    const mid = Math.floor(nums.length / 2);
    const leftMax = maxSubArray(nums.slice(0, mid));
    const rightMax = maxSubArray(nums.slice(mid));
    const crossMax = maxCrossingSubArray(nums, mid);

    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSubArray(nums, mid) {
    let leftSum = -Infinity;
    let sum = 0;
    for (let i = mid - 1; i >= 0; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    let rightSum = -Infinity;
    sum = 0;
    for (let i = mid; i < nums.length; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}