[알고리즘] 분할정복

1. 분할정복(Divide & Conquer) 알고리즘

문제 해결에 있어서 어떤 문제를 더이상 쪼갤 수 없을 때까지 분할(Divide)한 후 하위 문제들을 해결(Conquer)하고 합치(Combine)면서 문제의 답을 도출하는 알고리즘을 분할정복 알고리즘이라고 한다.

대표적인 분할정복의 예시인 병합정렬(Merge Sort)과 퀵정렬(Quick Sort)을 살펴보자.

---

2. 병합정렬(Merge Sort)

2-1. 병합정렬 알고리즘

병합정렬 알고리즘
1) 정렬할 리스트를 더 이상 나눌 수 없을 때까지 2개의 부분 리스트로 분할(Divide)
2) 더 이상 나눌 수 없는 부분 리스트를 다시 합치면서 정렬 수행(Conquer, Combine)

2-2. 병합정렬 과정

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

2-3. 병합정렬의 시간복잡도

병합정렬은 n개의 데이터로 logn 의 단계를 거치기 때문에 최악의 상황에도 O(nlogn) 을 보장한다는 장점이 있다.

2-4. 병합정렬 파이썬 코드

def merge_sort(arr):
	# arr의 길이가 1이면, 즉 리스트를 1의 길이로 다 쪼갰다면
    if len(arr) <= 1:
        return arr
    
    # 길이의 반을 기준으로 왼쪽 범위의 리스트는 left, 오른쪽 범위의 리스트는 right로 할당
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
	
    # left, right 리스트를 이용하여 재귀호출
    left = merge_sort(left)
    right = merge_sort(right)
	
    # left, right 리스트를 매개변수로 하는 merge 함수 호출
    result = merge(left, right)

    return result

def merge(left, right):
	# i는 left의 인덱스로 사용, j는 right의 인덱스로 사용
    # i, j를 0으로 초기화
    i = j = 0
    result = [] # 정렬된 수를 저장할 리스트 정의
	
    # i, j 각각 left, right 리스트의 길이보다 짧을 때
    while i < len(left) and j < len(right):
    	# left 리스트의 i 인덱스 값이 더 작다면
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        # right 리스트의 j 인덱스 값이 더 작다면
        else:
            result.append(right[j])
            j += 1
    
    # right 리스트를 전부 소진한 후, left 리스트의 나머지 원소 추가
    while i < len(left):
        result.append(left[i])
        i += 1
    
    # left 리스트를 전부 소진한 후, right 리스트의 나머지 원소 추가
    while j < len(right):
        result.append(right[j])
        j += 1

    return result

res = merge_sort(arr)

 

재귀호출이 헷갈린다면 아래 예시를 확인한다면 이해될 것이다.

# 예시 입력
arr = [5, 3, 6, 4]

# 함수 호출 순서
merge_sort([5, 3, 6, 4])
    merge_sort([5, 3])
        merge_sort([5])
        merge_sort([3])
        merge([5], [3]) -> result = [3, 5]
    merge_sort([6, 4])
        merge_sort([6])
        merge_sort([4])
        merge([6], [4]) -> result = [4, 6]
    merge([3, 5], [4, 6]) -> result = [3, 4, 5, 6]

---

3. 퀵정렬(Quick Sort)

3-1. 퀵정렬 알고리즘

퀵정렬 알고리즘
1) 리스트에서 임의의 값을 기준으로 하고 이것을 pivot이라고 함
2) pivot을 기준으로 pivot보다 작은 값들을 왼쪽에 큰 값들을 오른쪽에 둠
3) pivot을 제외한 리스트에 대해서 위와 같은 작업 반복(Divide)
4) 더 이상 나눌 수 없는 부분 리스트를 다시 합침(Conquer, Combine)

 

3-2. 퀵정렬 과정

https://morioh.com/p/b0deaa623ac4

3-3. 퀵정렬의 시간복잡도

퀵정렬은 평균적으로 O(nlogn)의 시간복잡도로 준수한 속도를 가지지만, 만약 pivot 값이 최소, 최대값으로 지정되어 있을 때 O(n^2)의 시간 복잡도를 가진다.