[Python - 알고리즘] 분할정복

분할정복(Divide and Conquer) 완벽 정리

---

1. 분할정복이란?

분할정복은 문제를 작은 문제로 나누고, 각각을 해결한 뒤, 그 결과를 합쳐서 원래 문제를 해결하는 알고리즘 설계 방법입니다.

• 분할(Divide): 문제를 여러 개의 작은 하위 문제로 나눈다.
• 정복(Conquer): 하위 문제를 재귀적으로 해결한다.
• 병합(Combine): 하위 문제들의 답을 모아서 원래 문제의 답을 구한다.

---

2. 왜 쓰는가?

• 큰 문제를 작은 문제로 나눠서 쉽게 해결할 수 있다.
• 재귀를 활용해 코드가 간결해진다.
• 많은 효율적인 알고리즘들이 분할정복 원리를 따른다.

---

3. 대표 예시: 병합 정렬 (Merge Sort)

정렬되지 않은 배열을 반으로 쪼갠다.
각 반을 재귀적으로 정렬한다.
정렬된 두 배열을 합쳐서 전체 정렬된 배열을 만든다.

병합 정렬 작동 과정

[38, 27, 43, 3, 9, 82, 10]
   ↓ Divide
[38, 27, 43, 3]       [9, 82, 10]
   ↓ Divide
[38, 27]   [43, 3]    [9, 82]   [10]
   ↓ Sort and Merge
[27, 38]   [3, 43]    [9, 82]   [10]
   ↓ Merge
[3, 27, 38, 43]       [9, 10, 82]
   ↓ Final Merge
[3, 9, 10, 27, 38, 43, 82]

---

4. 병합 정렬 파이썬 코드

def merge_sort(arr):
    # 배열이 1개 이하이면 이미 정렬된 상태
    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 = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

---

5. 시간복잡도

• 분할을 할 때마다 문제 크기가 절반으로 줄어듦 → log N 단계
• 각 단계마다 전체 배열을 한 번씩 병합 → O(N) 작업
• 따라서 전체 시간복잡도는 O(N log N) 입니다.

---

6. 분할정복의 응용

• 퀵 정렬 (Quick Sort): 피벗을 기준으로 분할하여 정렬하는 방법. 평균적으로 빠른 정렬법.
• 이진 탐색 (Binary Search): 정렬된 배열에서 중간값과 비교하며 범위를 반씩 줄여가며 탐색.
• 최대 부분 배열 합 (Maximum Subarray Problem): 배열을 반씩 나누어 최대 연속합을 구하는 문제.
• 행렬 곱셈 최적화: 큰 행렬을 작은 행렬로 나누어 효율적으로 곱셈.

---

7. 정리

알고리즘	방법	시간복잡도	설명
이진탐색	정렬된 리스트 반씩 범위 축소 탐색	O(log N)	빠른 탐색
병합 정렬	반으로 쪼개서 정렬 후 병합	O(N log N)	안정적, 대표 정렬 알고리즘
퀵 정렬	피벗 기준 작/큰값 분할 후 재귀 정렬	평균 O(N log N)	실제로 매우 빠름, 불안정 정렬

---