[Advanced] 4. 분할 정복 - 이론편

분할 정복

"분할 + 정복 + 통합"의 Top-down 방식

• 분할 : 해결할 문제를 여러 개의 작은 부분 문제들로 분할
• 정복 : 나눈 작은 문제를 각각 해결
• 통합 : 필요시 해결된 해답을 모음

 

가짜 동전 찾기

n개의 동전들 중에 가짜 동전이 하나 포함되어 있음 → 가짜는 진짜보다 아주 조금 가벼움
❔ 진짜 동전들의 무게가 동일하다고 할 때 양팔 저울을 이용해서 가짜 동전 찾아보기
    양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은?

 

거듭제곱을 구하기

1. 반복 알고리즘 O(n)
   • 반복문으로 n번 곱셈 연산
2. 분할 정복 O(logn)
   • 짝수/ 홀수 나눠서 재귀로 계산

 

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식

• 분할 정복 알고리즘 활용
• 자료를 최소 단위릐 문제까지 나눈 후, 차례대해 정렬하여 최종 결과 획득하는 Top-down 방식
• 시간 복잡도 O(n logn)

 

병합 정렬 과정

분할 단계 - 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 계속 분할 작업

ex) {69, 10, 30, 2, 16, 8, 31, 22} 를 병합 정렬

 

병합 정렬 알고리즘

def merge_sort(m):
    if len(m) <= 1: # 사이즈가 0이거나 1인 경우, 바로 리턴
        return m

    # DIVIDE
    mid = len(m) // 2
    left = m[:mid]
    right = m[mid:]

    # Recursion
    left = merge_sort(left)
    right = merge_sort(right)

    # CONQUER
    return merge(left, right)

def merge(left, right):
    result = [] # 두 리스트를 병합하여 result를 채움

    while len(left)>0 and len(right)>0:
        # 두 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    # 왼쪽 리스트에 원소 남아있는 경우
    if len(left) > 0:
        result.extend(left)
    # 오른쪽 리스트에 원소 남아있는 경우
    if len(right) > 0:
        result.extend(right)
    return result

 

 

퀵 정렬

주어진 리스트를 두 개로 분할하고 각각을 정렬

• 분할시, 기준 아이템(pivot) 중심으로 작은 것은 왼쪽 큰 것은 오른쪽에 배치
• 정렬이 끝난 후 병합과정 X

 

퀵 정렬 알고리즘

def quick_sort(A, l, r): # 리스트, 시작 인덱스, 끝 인덱스
    if l < r:
        # s = LomutoPartition(A, l, r)
        s = HoarePartition(A, l, r)
        quick_sort(A, l, s-1)
        quick_sort(A, s+1, r)

def HoarePartition(A, l, r): # Hoare
    p = A[l]  # 피봇 : 맨앞
    i = l+1
    j = r
    while i <= j:
        while i <= j and A[i] <= p:
            i += 1
        while i <= j and A[j] >= p:
            j -= 1
        if i <= j:
            A[i], A[j] = A[j], A[i]
    A[l], A[j] = A[j], A[l]
    return j

def LomutoPartition(A, l, r): # Lomuto
    x = A[r]  # 피봇 : 맨끝
    i = l - 1
    for j in range(l,r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

 

이진 검색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 이진 검색을 하기 위해 데이터는 정렬되어 있어야 함

 

이진 검색 과정

1. 자료의 중앙에 있는 원소를 고른다.
2. 중앙 원소의 값과 목표 값을 비교한다.
3. 목표 값 > 중앙 원소값 = 오른쪽
   목표 값 < 중앙 원소값 = 왼쪽
   목표 값 = 중앙 원소값 = 종료
4. 1~3 반복, 마지막 인덱스까지 가도 없으면 검색 실패!

 

이진 검색 알고리즘 : 반복문

def BinarySearch(a, low, high, key):
    start = 0
    end = len(a) - 1
    while start <= end:
        middle = start + (end - start)//2
        if key == a[middle]: # 검색 성공
            return middle
        elif key < a[middle]:
            end = middle - 1
        elif key > a[middle]:
            start = middle + 1
    return -1

이진 검색 알고리즘 : 재귀구조

def BinarySearch(a, low, high, key):
    if low > high:
        return -1
    else:
        middle = (low + high)//2
        if key == a[middle]: # 검색 성공
            return middle
        elif key < a[middle]:
            return BinarySearch(a, low, middle-1, key)
        else:
            return BinarySearch(a, middle+1, high, key)