[Python] 알고리즘 개념18 - 분할 정복(Divide and Conquer)

 

 

🚀 1. 분할 정복(Divide and Conquer)이란?

**분할 정복(Divide and Conquer)**은 문제를 작은 문제로 나누어 해결한 후, 결과를 합쳐 최종 해결하는 알고리즘 기법이에요.

 

💡 쉽게 이해하기

• 🎂 큰 케이크를 자를 때, 한 번에 자르기 어려우면 조각을 내서 먹는 것!
• 📚 두꺼운 책을 한 번에 다 읽지 않고, 챕터별로 나눠서 읽는 것!
• 🏗 건물을 짓기 전에 층별로 구조를 나누어 설계하는 것!

 

📌 분할 정복의 핵심 원리

1. 분할(Divide): 문제를 더 작은 문제로 나눕니다.
2. 정복(Conquer): 작은 문제들을 해결합니다.
3. 병합(Combine): 해결한 결과들을 합쳐서 최종 답을 구합니다.

➡ 즉, 문제를 작게 나누고 각각을 해결한 후, 합치는 방식이에요!

---

 

 

🚀 2. 분할 정복이 적용되는 대표적인 알고리즘

 

📌 분할 정복이 자주 사용되는 문제 유형

알고리즘 설명

병합 정렬(Merge Sort)	배열을 반으로 나누고 정렬 후 병합
퀵 정렬(Quick Sort)	기준점(Pivot)을 정하고 정렬
이진 탐색(Binary Search)	배열을 반씩 나누어 탐색
행렬 곱셈(Matrix Multiplication)	행렬을 나누어 곱셈 수행
최근접 쌍 문제(Closest Pair)	점들의 거리를 나누어 계산

➡ 분할 정복은 정렬, 탐색, 최적화 문제에서 매우 많이 사용돼요!

---

 

 

🚀 3. 분할 정복 구현 예제

 

 

✅ 1) 이진 탐색(Binary Search)

 

💡 문제:

정렬된 배열에서 특정 값을 빠르게 찾는 방법을 구현하세요.

 

📌 분할 정복을 이용한 해결 방법

1. 배열의 가운데 값을 기준으로 찾는 값과 비교합니다.
2. 값이 작으면 왼쪽, 크면 오른쪽 부분을 탐색합니다.
3. 찾을 때까지 반복합니다.

 

💡 Python 코드 구현

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, 3, 5, 7, 9, 11]
target = 7
print(binary_search(arr, target, 0, len(arr) - 1))  # 출력: 3 (인덱스)

➡ 이진 탐색은 O(log n)의 시간복잡도를 가지며, 매우 효율적인 탐색 방법이에요!

---

 

 

✅ 2) 병합 정렬(Merge Sort)

 

💡 문제:

주어진 배열을 정렬하는 프로그램을 작성하세요.

 

📌 분할 정복을 이용한 해결 방법

1. 배열을 반으로 나눈다.
2. 각각을 정렬한 후 합친다.

 

💡 Python 코드 구현

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 = [5, 2, 9, 1, 5, 6]
print(merge_sort(arr))  # 출력: [1, 2, 5, 5, 6, 9]

➡ 병합 정렬은 O(n log n)의 시간복잡도를 가지며, 안정적인 정렬 알고리즘이에요!

---

 

 

🚀 4. 분할 정복의 시간복잡도 분석

 

📌 분할 정복의 시간복잡도는?

알고리즘 시간복잡도

병합 정렬(Merge Sort)	O(n log n)
퀵 정렬(Quick Sort)	O(n log n) (최악 O(n²))
이진 탐색(Binary Search)	O(log n)

 

💡 왜 O(log n)이 나올까요?

• 한 번 탐색할 때마다 문제를 절반으로 줄이기 때문이에요!
• 예를 들어, 1024개의 데이터를 탐색하면 10번(log₂1024)만에 찾을 수 있어요!

➡ 분할 정복은 큰 문제를 작은 문제로 나누기 때문에 매우 효율적이에요!

---

 

 

✅ 마무리 정리

• 분할 정복은 문제를 작은 문제로 나누어 해결한 후, 결과를 합치는 방식이에요.
• 병합 정렬, 퀵 정렬, 이진 탐색 등에서 많이 사용돼요.
• 시간복잡도가 O(n log n) 또는 O(log n)으로 최적화된 경우가 많아요.
• 탐색, 정렬, 최적화 문제에서 강력한 기법이에요!