분할 정복 & 백트래킹

분할 정복 기법

유래

• 1805년 나폴레옹이 사용한 전략
• 연합군을 임의로 둘로 나누고 둘을 각각 격파

설계전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(conquer) : 나눈 작은 문제를 각각 해결한다.
• 통합(combine) : 해결된 해답을 모은다.

예시

• 거듭제곱

Recursive_power(x, n):
	if n ==1 : return x
    if n is even:
    	y = Recursive_power(x, n/2)
        return y * y
    else:
    	y = Recursive_power(x, (n-1)/2)
        return y * y * x

병합정렬

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
  • top-down 방식
• 시간 복잡도
  • O(n log n)

병합 정렬 과정

• 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업 수행
• 병합 단계 : 2개의 부분지밥을 정렬하면서 하나의 집합으로 병합

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

• 외부 정렬의 기본이 되는 정렬 알고리즘이다.
• 멀티코어 CPU나 다수의 프로세서에서 정렬 알고리즘을 병렬화하기 위해 병합 정렬 알고리즘이 활용된다.

퀵 정렬

• 주어빈 배열을 두개로 분할 하고 각각을 정렬한다.
  • 병합정렬과 다른점
    • 병합정렬은 그냥 두 부분으로 나누는 반면에 퀵 정렬은 분할할 때 기준 아이템 중심으로 분할한다
    • 각 부분 정렬이 끝난 후, 병합정렬은 "병합"이란 후처리 작업이 필요하나 퀵 정렬은 필요로 하지 않는다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

• p를 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 위치한다.

이진 검색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
  • 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위의 반으로 줄여가면서 빠르게 검색
• 정렬 된 상태여야 검색이 가능

# Case 1 반복문
def binary_search(target, data):
    data.sort()
    start = 0 			# 맨 처음 위치
    end = len(data) - 1 	# 맨 마지막 위치

    while start <= end:
        mid = (start + end) // 2 # 중간값

        if data[mid] == target:
            return mid 		# target 위치 반환

        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1
        else:                    # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return

# Case 2 재귀
def binary_search(target, start, end):
    if start > end:		 # 범위를 넘어도 못찾는다면 -1을 반환
        return -1

    mid = (start + end) // 2  # 중간값

    if data[mid] == target:	# 중간값의 데이터가 target과 같다면 mid를 반환
        return mid

    elif data[mid] > target: # target이 작으면 왼쪽 탐색
        end = mid - 1
    else:                    # target이 크면 오른쪽 탐색
        start = mid + 1

    return binary_search(target, start, end) # 줄어든 범위를 더 탐색

• 정렬된 데이터를 기준으로 특정 값이나 범위를 검색하는데 사용
• Lower Bound, Upper Bound로 나뉨
  • 정렬된 배열에서 특정 값 이상 또는 이하가 처음으로 나타나는 위치를 찾는 알고리즘
  • 특정 데이터의 범위 검색 등에서 활용