[알고리즘] 분할 정복 알고리즘과 재귀

분할 정복 알고리즘 개요

분할 정복 알고리즘은 큰 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 다음 그 결과를 결합하여 원래 문제를 해결하는 알고리즘 기법입니다. 이러한 방식으로 문제를 해결함으로써 복잡한 문제를 간단한 부분 문제로 나누어 해결할 수 있습니다.

---

분할 정복 알고리즘의 구성 요소

분할 정복 알고리즘은 일반적으로 세 가지 단계로 구성됩니다.

• 분할(Divide): 문제를 더 작은 부분 문제로 분할합니다.
• 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다.
• 결합(Combine): 작은 부분 문제의 해를 결합하여 원래 문제의 해를 얻습니다.

---

분할 정복 알고리즘의 예시

분할 정복 알고리즘을 이해하기 위해 두 가지 예시를 살펴보겠습니다.

 

병합 정렬(Merge Sort)

병합 정렬은 분할 정복 알고리즘의 대표적인 예시입니다. 주어진 배열을 반으로 나눈 뒤 각 부분 배열을 정렬하고 병합하여 전체 배열을 정렬하는 방식입니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_index, right_index = 0, 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    result.extend(left[left_index:])
    result.extend(right[right_index:])
    return result

 

퀵 정렬(Quick Sort)

퀵 정렬은 다른 분할 정복 알고리즘으로, 배열을 분할하는 과정에서 피벗(pivot)을 기준으로 작은 값과 큰 값으로 나누어 정렬하는 방식입니다.

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)

 

이와 같이 분할 정복 알고리즘은 큰 문제를 작은 부분 문제로 분할하고 각각을 해결하여 전체 문제를 효율적으로 해결하는 데 사용됩니다.