[WEEK02] 분할 정복

📌 분할 정복이란?

분할 정복(Divide and Conquer)은 문제를 작은 하위 문제로 나누고(Divide), 각 하위 문제를 해결한 뒤(Conquer), 그것들을 합쳐서(Merge) 최종적인 결과를 도출하는 알고리즘 설계 기법이다. 주로 재귀를 사용하여 구현된다.

🔥 분할 정복의 핵심 원리

1. 분할(Divide): 문제를 더 작은 하위 문제로 나눈다.
2. 정복(Conquer): 각 하위 문제를 재귀적으로 해결한다.
3. 병합(Merge): 하위 문제의 결과를 결합하여 원래 문제의 해답을 구한다.

📚 대표적인 예제

1. 병합 정렬(Merge Sort)

• 배열을 절반씩 나누어 정렬한 후, 병합하면서 정렬하는 방식
• 시간 복잡도: O(n log n)

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

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

2. 퀵 정렬(Quick Sort)

• 피벗(Pivot)을 설정하고, 피벗을 기준으로 작은 값과 큰 값을 분할하여 정렬하는 방식
• 평균 시간 복잡도: O(n log n), 최악의 경우 O(n^2)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

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

3. 이진 탐색(Binary Search)

• 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘
• 시간 복잡도: O(log n)

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, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 2, 3, 4, 5, 6, 7, 8]
target = 5
print(binary_search(arr, target, 0, len(arr) - 1))

💡 분할 정복 알고리즘의 장점과 단점

✅ 장점

• 문제를 작은 단위로 쪼개어 해결하므로 효율적인 알고리즘 설계 가능
• 정렬, 탐색 등 다양한 문제에 적용 가능
• 병렬 처리에 유리하여 멀티코어 환경에서 성능 향상 가능

❌ 단점

• 재귀 호출이 많아지면 스택 오버플로우(Stack Overflow) 위험
• 하위 문제의 병합 과정에서 추가적인 메모리 사용 가능 (예: 병합 정렬)
• 일부 경우(예: 퀵 정렬에서 피벗을 잘못 선택한 경우) 최악의 시간 복잡도 발생

🎯 정리

분할 정복 알고리즘은 다양한 문제를 해결하는 데 강력한 도구가 될 수 있다. 특히 정렬, 탐색, 행렬 곱셈, 최근접 점 문제 등 여러 분야에서 사용된다. 적절한 알고리즘을 선택하여 효율적인 문제 해결을 해보자.