알고리즘 4주차 - 분할 정복 알고리즘

Keywords : 분할, 정복, 합병 정렬

 

분할 정복 알고리즘

• 주어진 문제의 입력을 분할
• 분할한 입력을 계산
• 각 해를 취합해 해를 얻음
• 부분문제는 더 이상 분할할 수 없을 때까지 분할
• 입력 크기가 n일 때 분할 횟수는 log2n
• 부분문제 수, 부분문제 크기에 따른 분류
  • 부분문제 a개, 부분문제 크기 1/b로 감소 : 합병 정렬
  • 부분문제 2개, 부분문제 크기 일정하지 않음 : 퀵 정렬
  • 부분문제 2개이지만 하나는 버림, 부분문제 크기 1/2로 감소 : 이진탐색*
  • 부분문제 2개이지만 하나는 버림, 부분문제 크기 일정하지 않음 : 선택 문제 알고리즘
  • 부분문제 크기 1,2개씩 감소 : 삽입 정렬*

# 분할 정복 알고리즘 구현
def merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    result = []
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else:
            result.append(g2.pop(0))
    
    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))
    
    return result

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(merge_sort(d))

 

합병 정렬

• 부분문제 2개, 부분문제 크기 1/2로 감소
• 2개로 정렬된 숫자 배열을 하나의 배열로 합치는 것
• 합병 별 비교 횟수 : O(n)
• 합병 정렬의 시간 복잡도 : 층수 * O(n) = log2n * O(n) = O(nlogn)
• 장점 : 삽입 정렬 복잡도보다 낮아 자료 개수 많을 수록 유리
• 단점 : 입력을 위한 메모리 공간 외 추가로 입력과 공간과 같은 크기의 공간이 별도로 필요

<코드>