[알고리즘 | 자료구조] 분할정복

분할정복

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

알고리즘 설계 유형

1)Divide : 문제가 분할이 가능한 경우 2개 이상의 문제로 나눈다.
2)Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
3)Combine : Conquer한 문제들을 퉁합하여 원래 문제의 답을 얻는다.

분할정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 재귀 호출을 여러번 실행한다.

사용정렬

퀵정렬

특정 원소 피봇을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식이다.

1)Divide
피봇 하나를 선택하여 피봇을 기준으로 2개의 부분 배열로 분할함.

2)Conquer
피봇을 기준으로 피봇보다 큰 값, 혹은 작은 값을 찾음.
왼쪽에서 부터 피봇보다 큰 값을 찾고 오른쪽에서 부터는 피봇보다 작은 값을 찾아서 두 원소를 교환.
분할된 배열의 크기가 0이나 1이 될때 까지 반복.

3)Combine
Conquer과정에서 값의 위치가 바뀌므로 따로 결합하지 않음.

arr = list(map(int, input().split()))


def quickSort(arr):
    if len(arr) <= 1:
        return arr

    pivot, tail = arr[0], arr[1:]

    leftSide = [x for x in tail if x <= pivot]
    rightSide = [x for x in tail if x > pivot]

    return quickSort(leftSide) + [pivot] + quickSort(rightSide)


print(quickSort(arr))

이진탐색

정렬된 데이터를 효과적으로 탐색할 수 있는 방법

1)Divide
배열의 가운데 원소를 기준으로 왼쪽, 오른쪽 부분 배열로 분할한다. 탐색키와 가운데 원소가 같으면 분할을 종료한다.
2)Conquer
탐색키가 가운데 원소보다 작으면 왼쪽 부분 배열을 대상으로 이진 탐색을 순환 호출하고, 크면 오른쪽 부분 배열을 대상으로 이진탐색을 호출한다.
3)Combine 탐색 결과가 직접 반환되므로 결합이 불필요하다.

arr = list(map(int, input().split()))


def binarySearch(arr, value, left, right):
    if left > right:
        return None
    mid = (left + right) // 2

    if arr[mid] == value:
        return mid

    elif arr[mid] > value:
        return binarySearch(arr, value, left, mid-1)

    else:
        return binarySearch(arr, value, mid+1, right)


print(binarySearch(arr, 4, 0, len(arr)-1)+1, "번째")

합병정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.

1)Divide
입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
2)Conquer
부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 (left<right) 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3)Combine
정렬된 부분 배열들을 하나의 배열에 합병한다.

arr = list(map(int, input().split()))


def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)


def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result


print(merge_sort(arr))