분할 정복(Divide and Conquer)

분할 정복은 말 그대로
"큰 문제를 잘게 쪼개서 각 부분을 풀고, 그 결과를 합쳐서 전체 문제를 푸는 방법" 이다.

즉,

• Divide (분할) : 문제를 여러 개의 하위 문제로 나눔
• Conquer (정복) : 하위 문제를 재귀적으로 해결
• Combine (결합) : 하위 문제의 해답을 모아서 원래 문제의 해답을 만듬

예시 코드

병합 정렬(Merge Sort)

• 분할: 배열을 반으로 나눔
• 정복: 각각 정렬
• 결합: 정렬된 두 배열을 합침

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

이 외에도 이분 탐색도 분할 정복의 일종이라고 볼 수 있다

• 분할: 배열을 반으로 나눠서, 정답이 있을 수 있는 절반만 봄
• 정복: 절반에서 다시 탐색
• 결합: 없음 (단순히 결과를 리턴만 하면 됨)

분할 정복이 중요한 이유 !

대표적인 분할 정복 알고리즘