분할 정복(Divide and Conquer)

1. 분할 정복(Divide and Conquer)

큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘

문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.

대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다.

 

2. 동작 방식

1. 문제를 작은 부분 문제들로 분할한다.
2. 분할된 부분 문제들을 각각 재귀적으로 해결한다.
3. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다.

 

3.  시간 복잡도

시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다.

대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 시간 복잡도가 결정된다.

분할된 문제들의 크기가 일정하다면, 재귀 호출의 깊이는 로그 시간 복잡도에 비례한다.

 

분할된 문제의 개수가 N이라면, 시간 복잡도는 O(N*logN)

 

그러나 분할된 문제의 개수가 지수적으로 증가하거나 분할된 문제들이 크기가 일정하지 않은 경우, 시간 복잡도가 지수적으로 증가할 수 있다.

이 경우에는 다른 알고리즘을 고려해야 한다.

 

4. 병합 정렬(Merge Sort)

분할과 정복을 모두 사용하여 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 두 개의 부분 리스트를 합쳐 전체 리스트를 정렬하는 방식

1. 동작 과정

1. 분할: 입력 리스트를 반으로 나눕니다.
2. 정복: 각각의 부분 리스트를 재귀적으로 병합 정렬합니다.
3. 결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬합니다.

 

2. 파이썬 구현 코드

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Divide
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Conquer
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # Combine
    return merge(left_sorted, right_sorted)
    
    
def merge(left, right):
    result = []
    i, j = 0, 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 += left[i:]
    result += right[j:]
    
    return result

 

• merge_sort 함수 :
  • 입력 리스트를 반으로 나누고 재귀적으로 호출하여 각각을 정렬
  • 마지막으로 merge 함수를 사용하여 두 정렬된 리스트를 합병하여 전체 리스트를 정렬
• merge 함수 :
  • 두 개의 정렬된 리스트를 인수로 받아, 두 리스트를 비교하여 작은 순서대로 result 리스트에 삽입하고, 남은 요소를 추가하여 반환

 

5. 퀵 정렬(Quick Sort)

분할과 정복을 사용하여 리스트를 분할하고, 각각을 재귀적으로 정렬한 다음, 전체 리스트를 합치지 않고 원래 위치에 놓여있는 것을 기준으로 정렬

 

특히, 정렬을 위해 별도의 저장 공간을 필요로 하지 않아 메모리 사용량이 적다는 특징이 있다.

1. 동작과정

1. 기준점(pivot) 선택: 리스트에서 하나의 원소를 기준점으로 선택한다.
2. 분할: 기준점을 기준으로 리스트를 두 개로 분할한다. 분할된 두 개의 리스트는 각각 기준점보다 작은 값과 큰 값으로 이루어져 있다.
3. 정복: 각각의 부분 리스트를 재귀적으로 퀵 정렬한다.
4. 결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬한다.

 

2. 파이썬 구현 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # Divide
    pivot = arr[0]
    left = []
    right = []
    
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    
    # Conquer
    left_sorted = quick_sort(left)
    right_sorted = quick_sort(right)
    
    # Combine
    return left_sorted + [pivot] + right_sorted

 

• quick_sort 함수 :
  • 입력 리스트의 첫 번째 요소를 기준으로 왼쪽과 오른쪽 부분 리스트를 나눔
  • 재귀적으로 각각을 정렬하여 마지막으로 합쳐서 반환

 

입력 리스트의 첫 번째 요소를 기준으로 나누기 때문에, 최악의 경우(이미 정렬된 리스트, 피벗이 가장 작거나 큰 수 등)에는 분할이 제대로 이루어지지 않아 시간 복잡도가 O(n^2)에 근접해질 수 있다.

이를 방지하기 위해서는 피벗을 무작위로 선택하거나, 미리 섞어서 평균적인 경우를 대응하는 방법 등이 있다.