분할 정복(Divide and Conquer)

분할 정복

"큰 문제를 작은 문제로 나누고, 각각을 해결한 후 결합하여 최종 해답을 도출하는 알고리즘 기법"

• 재귀(Recursion)를 사용하여 문제를 반복적으로 쪼개어 해결
• 각 부분 문제가 동일한 방식으로 해결 가능해야 함 (재귀적 구조)
• 대표적인 예제: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search), 행렬 곱셈(Strassen Algorithm)

---

분할 정복(Divide and Conquer) 동작 원리

1. 분할(Divide): 문제를 더 작은 부분 문제(subproblem)로 나눈다.
2. 정복(Conquer): 부분 문제를 해결한다. (대부분 재귀적으로 해결)
3. 결합(Combine): 부분 문제의 답을 결합하여 전체 문제의 답을 만든다.

# Pseudo Code
FUNCTION MergeSort(arr):
    IF 길이(arr) == 1 THEN RETURN arr
    
    중간값 = 길이(arr) // 2
    LEFT = MergeSort(arr[:중간값])
    RIGHT = MergeSort(arr[중간값:])
    
    RETURN Merge(LEFT, RIGHT)


# Full Code_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):
    sorted_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

arr = [6, 3, 8, 5, 2, 7, 4, 1]
print(merge_sort(arr))  # [1, 2, 3, 4, 5, 6, 7, 8]


# Full Code_Binary Search
def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 찾을 수 없음

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid  # 목표값 찾음
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 오른쪽 탐색
    else:
        return binary_search(arr, target, left, mid - 1)  # 왼쪽 탐색

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(arr, 5, 0, len(arr) - 1))  # 4 (인덱스 위치)

---

분할 정복(Divide and Conquer)의 시간복잡도

알고리즘	시간복잡도
병합 정렬(Merge Sort)	O(n log n)
퀵 정렬(Quick Sort, 평균적)	O(n log n)
이진 탐색(Binary Search)	O(log n)
행렬 곱셈(Strassen Algorithm)	O(n².⁸ⁱ)

 

✅ 대부분 O(n log n) 또는 O(log n)으로 빠른 성능을 보장!
✅ 퀵 정렬의 최악의 경우는 O(n²) (피벗 선택이 나쁘면)

---

분할 정복 vs 동적 계획법(DP) 비교

알고리즘	특징	시간복잡도	적용 사례
분할 정복	문제를 작은 부분으로 나누어 해결 후 합침	O(n log n), O(log n)	병합 정렬, 퀵 정렬, 이진 탐색
DP (동적 계획법)	부분 문제를 저장하여 중복 계산 방지	O(n), O(n²), O(n³) 가능	피보나치, 배낭 문제, 최장 공통 부분 수열

 

 

✅ 문제를 반으로 나누어서 해결할 수 있는 경우 사용

✅ 부분 문제를 독립적으로 해결하고 결합할 수 있는 경우 사용

 

---

분할 정복의 장단점

장점

 

• 문제를 작은 부분으로 나누어 쉽게 해결 가능
• 병렬 처리(Parallel Processing)가 가능 (부분 문제를 동시에 해결 가능)
• 이진 탐색처럼 매우 빠른 탐색 알고리즘을 만들 수 있음

단점

 

• 재귀 호출이 많아지면 함수 호출 오버헤드 발생 가능
• 병합 정렬처럼 추가적인 메모리 사용이 필요한 경우가 있음(O(n) 공간복잡도)

결론

분할 정복(Divide and Conquer)은 문제를 작은 부분으로 나누고, 각 부분을 해결한 후 결합하는 방식이며, 정렬(병합 정렬, 퀵 정렬), 탐색(이진 탐색) 등 다양한 알고리즘에서 사용된다.