분할 정복에 관해 공부하기 위해

INTRODUCTON TO ALGORITHMS라는 책을 읽으려 헀으나…

피치 못할 사정 (존나 어려움;;)
때문에 가볍게만 정리해보았다

책에선 자꾸 지들만 아는 얘기해서 잘 이해 못했다

분할 정복

개념

분할 정복은 이름처럼
분할하고 정복해 나가는 방식이다

정확히는, 3단계로 이루어져있다

• Divide(분할): 문제를 더 작은 문제로 나눈다

• Conquer(정복): 하위 문제들을 각각 재귀적으로 해결한다

• Combine(병합): 합쳐서 원래 문제의 해답을 만든다

예시

흐름

1. 분할(Divide):

• 정렬하려는 리스트를 반으로 가/른/다

2. 정복(Conquer):

• 나뉜 리스트 계속 쪼개기

• 리스트 크기가 1이면 이미 정렬됨

• 영국이 잘한다

3. 병합(Combine):

• 두 개의 정렬된 리스트를 하나로 합칩니다

• 나라 합치는 것도 병합이다만…
  여기선 안다룬다

병합 정렬 (Merge Sort)

흐름

1. 배열을 반씩 계속 나눈다.

2. 한 칸이 될 때까지 나눈다.

3. 한 칸짜리 배열 두 개를 합쳐 정렬한다.

4. 이 과정을 거슬러 올라가며 두 개씩 합치면서 정렬한다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    result = []
    i = j = 0
    # 두 부분 배열 합치기
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

___