종만북 7장 [w/ Python]

분할 정복 

 

 - 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

 

 - 분할 정복의 세가지 구성 요소

 

1. 문제를 더 작은 문제로 분할하는 과정 (divide)

2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)

3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

 

- sum(range(n)) 을 구할 경우 1+2+3+..+n을 구하는 연산은 O(N)의 시간 복잡도를 가진다.

분할 정복으로 해당 문제를 분리할 경우 1+2+...+n = 1+2+..+(n//2)+ ((n//2)+1)+..+((n//2)+(n//2)) 이므로 뒤의 연산을 정리하면 (n//2)*(n//2)*sum(range(n//2+1)이 된다. 

이 때, n이 홀수라면 sum(n) = sum(n-1) + n 으로 문제를 분할하게 되는데 이 때 sum(n//2)+sum(n//2+1)처럼 거의 크기가 같게 분할하는 것은 비효율적이다. 왜냐하면 이런식의 연산은 sum(n)을 찾기위해 계산해야할 부분 문제의 수가 늘어나기 때문이다. 이를 해결하기위해 동적계획법이 필요하다.

 

 

- 병합 정렬(Merge Sort)

 

# 병합 정렬(Merge Sort)
# 2로 나누고 1개의 요소가 남을 때 까지 재귀적으로 conquer
# 그 후 요소를 2개씩 병합해나간다.
def mergeSort(unsorted_list):
    # 기저조건 : 요소가 1개
    if len(unsorted_list) <= 1:
        # 요소가 아니라 리스트를 반환
        return unsorted_list
    # 가운데를 기준으로 나누기 위해 가운데 항목 찾기
    mid = len(unsorted_list)//2
    # 중간값을 기준으로 왼쪽 요소 
    left = unsorted_list[:mid]
    # 중간값을 기준으로 오른쪽 요소
    right = unsorted_list[mid:]
    # 재귀를 이용해 왼쪽값과 오른쪽값을 다시 나눈다.
    splited_left = mergeSort(left)
    splited_right = mergeSort(right)
    # 분리된 두 부분을 병합한 결과를 반환
    return merge(splited_left, splited_right)
# 병합하는 함수
def merge(left, right):
    # 시작점
    i,j = 0, 0
    sorted_list = []
    
    while i < len(left) and j < len(right):
        # 양 리스트를 앞부터 비교해가며 더 작은 것을 먼저 넣는다.
        if left[i] < right[j]:
            sorted_list.append(left[i])
            # i번째 요소를 넣었으므로 다음 것으로 갱신
            i += 1
        else :
            sorted_list.append(right[j])
            # j번째 요소를 넣었으므로 다음 것으로 갱신
            j += 1
    
    # 남은 요소가 존재할 경우 넣어준다.
    # while i < len(left):
    #     sorted_list.append(left[i])
    #     i += 1
 
    # while j < len(right):
    #     sorted_list.append(right[j])
    #     j += 1
    
    # 나의 풀이 
    if len(left) != i:
        sorted_list.extend(left[i:])
        i = len(left)
    else :
        sorted_list.extend(right[j:])
        j = len(right)
    return sorted_list
 
print(mergeSort([1,3,2,5,6,8,4,2]))

 

- 퀵소트(Quick Sort)

 

# 퀵소트(Quick Sort)
# pivot을 기준으로 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다.
# 리스트 arr을 퀵소트 하는 함수
def quick_sort(arr):
    # 재귀 함수이며 정렬 범위를 시작 인덱스와 끝 인덱스로 받는다.(both inclusive)
    def sort(low, high):
        # 종료 조건(인덱스 역전)
        if high <= low :
            return 
        # 정렬 기준점을 mid에 넣는다
        mid = partition(low, high)
        # 정렬 기준점을 중심으로 왼쪽, 오른쪽을 각각 정렬한다.
        sort(low, mid-1)
        sort(mid,high)
    # 정렬 범위를 인자로 받으며 좌, 우측의 값들을 정렬하고 분할기준점의 인덱스를 리턴한다.
    def partition(low, high):
        # 중간값을 피봇으로
        pivot = arr[(low+high)//2]
        while low <= high:
            # 피봇값보다 피봇 왼쪽 값이 더 작다면 아무 작업을 안해도 되므로 변경이 필요할 때까지 다음 것으로 넘기기
            while arr[low] < pivot:
                low += 1
            # 피봇값보다 피봇 오른쪽 값이 더 크다면 아무 작업을 안해도 되므로 변경이 필요할 때까지 이전 것으로 당기기
            while arr[high] > pivot:
                high -= 1
            # 피봇 기준으로 변경이 필요
            if low <= high:
                # 두 값을 바꿔준다.
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high -1 
        # ?
        return low
 
    return sort(0, len(arr)-1)

 

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략