분할 정복 기법 (Divide and Conquer)

Divide and Conquer
큰 문제를 여러 개의 작은 부분 문제로 분할(Divide)하고,
각 부분 문제를 독립적으로 해결(Conquer)한 후
그 결과를 결합(Combine)하여 원래 문제의 해가 되도록 만듬

 

특성

• 재귀적 접근 :
  문제를 계속해서 작은 단위로 분할하며, 각 단계마다 동일한 전략을 반복해서 적용
• 문제 단순화 :
  복잡한 문제를 여러 개의 간단한 문제로 나누어, 각 부분 문제에 대해 쉽게 해결
• 병렬 처리 가능성 :
  하위 문제들이 서로 독립적일 경우, 병렬 처리하여 전체 수행시간을 줄일 수 있음
• 분할 및 합병 오버헤드 :
  재귀를 활용하기 때문에, 분할하고 결합하는 과정에서 추가적인 연산과 메모리 사용이 발생할 수 있음

흐름

1. 분할(Divide)
   해결할 문제를 여러 개의 하위 문제로 나눔. 이 때 하위 문제는 동일한 구조를 가지고, 일반적으로는 크기가 작아짐
2. 정복(Conquer)
   분할된 각 하위 문제를 독립적으로 해결. 문제가 충분히 작으면 직접 해결하고, 그렇지 않으면 다시 기법을 재귀적으로 적용
3. 결합(Combine)
   각 과정은 문제에 따라 다르나, 각 하위 문제의 해답을 하나로 합쳐서 원래 문제의 해답을 생성함.
   (예: 정렬 문제에서는 두 정렬된 리스트를 하나로 병합)

기법 활용 예

병합 정렬 (Merge Sort)

균등 분할과 O(n)의 결합 과정을 통해 O(n log n)의 시간복잡도를 가지며
기법의 기본적인 흐름은 다음과 같다

• (분할단계) 배열을 반씩 나누면서 재귀적으로 호출하여 더 이상 나뉠 수 없을 때 까지 나눠준다.
  (base case : 배열 길이가 1이 될 때)
• (정복단계) 배열을 재귀적으로 분할하여, base case에 도달하면 이미 배열이 결합단계 merge 함수를 호출하여 정렬함으로써, 정렬된 상태로 반환된다.
  • 실제 이 단계에서 정렬이 진행되지는 않고, 결합단계에서 정렬이 완료된 후 돌아옴
• (결합단계) 정렬된 하위 배열들을 받아서, 두 개의 정렬된 배열을 하나로 병합하여 전체 정렬을 완성.
  두 배열의 요소들을 비교하면서 올바른 순서대로 결합하여 최종정렬을 반환

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):
    """
    두 정렬된 배열(left, right)을 하나의 정렬된 배열로 합칩니다.
    """
    result = []  # 병합된 결과를 저장할 리스트
    i, j = 0, 0  # left와 right 배열의 인덱스 초기화

    # 두 배열의 요소들을 비교하면서 작은 값을 결과 배열에 추가합니다.
    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

    # left 배열에 남은 요소들을 결과 배열에 추가합니다.
    if i < len(left):
        result.extend(left[i:])
    # right 배열에 남은 요소들을 결과 배열에 추가합니다.
    if j < len(right):
        result.extend(right[j:])

    return result