분할 정복, 정렬

• 알고리즘 설계 기법의 종류

1. 전체를 다 보자! ⇒ Brute Force = 완전 탐색
배열 : for 문, while 문
그래프 ( 관계가 있는 데이터 ) : BFS, DFS

→ 완전 탐색을 구현하면 시간 or 메모리 초과가 발생할 경우?!

2. 상황마다 좋은 걸 고르자 = Greedy 그리디
-> 규칙 찾기 + 증명 → 이후 구현

3. 큰 문제를 작은 문제로 나누어 부분적으로 해결하자 = Dynamic Programming
-> 분할 정복과 달리 작은 문제가 중복되어 발생하여 계산의 비효율이 발생

-> 중복된 문제의 해답을 저장해놓고 재활용하자! (Memoization)

4. 큰 문제를 작은 문제로 나누어 부분적으로 해결하자 = 분할 정복

5. 전체 중 가능성 없는 것을 빼자 = Backtracking 백트래킹

 

위와 같은 기본들을 기반으로 고급 알고리즘들이 개발되었다.

 

대표적인 분할 정복 알고리즘

→ 병합 정렬, 퀵 정렬, 이진 검색

 

• 분할 정복

Divide(분할) and Conquer(정복), Combine(통합)

 

• 병합 정렬

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

분할 정복 알고리즘 활용 → 자료를 최소 단위로 나눈 후에 차례대로 정렬하여 최종 결과를 얻어낸다.

시간 복잡도 : O(n log n)

 

• 퀵 정렬

주어진 배열을 2개로 분할하고, 각각을 정렬한다.

병합 정렬이 그냥 두 부분으로 나누는 반면, 퀵 정렬은 기준 아이템(pivot)을 중심으로 분할한다. 또한 병합하는 등 별도의 후처리 작업이 필요하지 않다.

평균적으로 효율이 굉장히 좋다!

 

• 이진 검색

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

단, 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

# 이진 검색
arr = [324, 32, 22114, 16, 48, 93, 422, 21, 316]

# 1. 정렬된 상태의 테이터
arr.sort()

# 2. 이진 검색 - 반복문 버전
def binaryserach(target):
    # 제일 왼쪽, 오른쪽 인덱스 구하기
    low = 0
    high = len(arr)-1

    # 해당 숫자를 찾으면 종료
    # 더 이상 쪼갤 수 없을때 까지 반복
    while low <= high:
        mid=(low+high) // 2

        # 가운데 숫자가 정답이면 종료
        if arr[mid] == target:
            return mid
        elif target: 
            return mid

 

• 병합 정렬 ( list )

def merge_sort(lst):

    # 기저 사례
    if len(lst) <= 1:
        return lst
    
    # 일반 사례 -> 2분할 진행
    mid = len(lst) // 2
    # 왼쪽 -> lst[:mid], 오른쪽 -> lst[mid:]
    l = merge_sort(lst[:mid])
    r = merge_sort(lst[mid:])
    # l, r은 정렬된 리스트
    # 왼쪽과 오른쪽을 병합한다!
    result = []
    # 왼쪽과 오른쪽 모두 자료가 있을 경우
    while l and r:
        if l[0] <= r[0]:
            result.append(l.pop(0))
        else:
             result.append(r.pop(0))   
    
    if l:
        result.extend(l)
    if r:
        result.extend(r)

    return result   # 병합

arr = [69, 10, 30, 2, 16, 8, 32, 21]
print(merge_sort(arr))

 

• 병합 정렬 (index)

def merge_sort(lo, hi):     # 구간의 시작과 끝
    if lo == hi:
        return
    # 2분할 진행
    mid = (lo + hi) >> 1
    merge_sort(lo, mid)
    merge_sort(mid + 1, hi)

    # 왼쪽과 오른쪽이 정렬된 상태 => 병합
    # i는 왼쪽의 시작 위치, j는 오른쪽의 시작 위치
    # k는 arr에서 복사해서 저장할 temp의 시작 위치

    i, j, k = lo, mid + 1, lo

    while i <= mid and j <= hi:
        if arr[i] < arr[j]:
            temp[k] = arr[i]; i += 1; k += 1
        else:
            temp[k] = arr[j]; j += 1; k += 1
    while i <= mid:
        temp[k] = arr[i]; i += 1; k += 1
    while j <= hi:
        temp[k] = arr[j]; j += 1; k += 1

    for i in range(lo, hi + 1):
        arr[i] = temp[i]

arr = [69, 10, 30, 2, 16, 8, 32, 21]
N = len(arr)
temp = [0] * N  # 정렬 과정에서 임시로 정렬된 자료를 저장하는 공간
merge_sort(0, N-1)