[알고리즘 시리즈] 분할 정복 : Divide and Conquer

---

분할 정복 : Divide and Conquer

목차

1. 분할 정복의 목적

2. 분할 정복의 적용 절차

3. 분할 정복이 적용된 형태

4. 재귀적으로 분할된 알고리즘의 시간복잡도를 분석하는 방법

---

1. 분할 정복의 목적

복잡한 전체 문제를 쉬운 부분 문제로 나누어 푼다.

 

2. 분할 정복의 적용 절차

1. 전체 문제를 부분 문제로 나눈다. -> divide
2. 부분 문제를 해결한다. -> conquer
3. 해결된 부분 문제들을 합친다. -> combine

 

3. 분할 정복이 적용된 형태

아래는 분할 정복을 이용하여 병합 정렬을 수행하는 코드다.

1. 배열을 절반으로 분리한다. <- divide
2. 투 포인터를 이용해 두 배열을 하나의 배열에 오름차순으로 정렬한다. <- conquer and combine

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2

        left_half = arr[:mid]
        right_half = arr[mid:]

        # ----------------- 분할 ------------------
        merge_sort(left_half)
        merge_sort(right_half)

        # ----------------- 정복 및 병합 ------------------
        i = j = k = 0

        # 왼쪽과 오른쪽 배열을 비교하여 상위 배열에 삽입한다.
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남아있는 요소를 배열에 삽입한다.
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array:", arr)

 

4. 재귀적으로 분할된 알고리즘의 시간복잡도를 분석하는 방법

1) Substitution method : 대입법

수학적 귀납법을 이용해 일반화된 식을 찾고 분할 횟수를 대입하여 시간복잡도를 분석하는 방법.

---

기본 관계식

다음 단계를 기본 관계식에 대입

이를 다시 첫 번째 식에 대입

일반화

배열 크기가 n에서 1이 될 때까지 분할할 때, 분할 횟수는 $log_2n$이다.

따라서 k = $log_2n$일 때, 배열의 크기는 1이 되고 $T(1) = O(1)$ 이므로,

 

2) Recursion-tree method : 재귀 트리 그리기

재귀 관계식을 트리 형태로 나타내어 트리의 높이와 각 단계의 비용을 계산하여 시간 복잡도를 분석하는 방법.

---

기본 관계식

기본 관계식을 이용하여 재귀 트리를 그리면

트리의 높이 : $log_2n$

각 단계의 걸리는 시간 : $n$

이므로, 시간복잡도는 $O(nlogn)$ 이다.

 

3) Master method (매우 유용)

재귀 관계식을 구하고 조건과 비교하여 주어진 형태를 이용하여 시간 복잡도를 구하는 방법.

 

기본 관계식을 다음 일반식과 대치하여

아래 세 경우 중 하나에 해당하는지 확인한다.

master method의 아이디어

 

$h = log_bn$이라고 하면, 재귀 트리의 잎의 갯수는 $a^h$이다.

이는 $a^h = a^{\log_bn} = n^{\log_ba}$와 같이 치환될 수 있으며, $n^{\log_ba}$는 잎의 개수를 의미한다.

 

case1의 경우 잎의 개수가 계층마다 증가하고,

case2의 경우 잎의 개수가 계층마다 일정하고,

case3의 경우 잎의 개수가 계층마다 감소한다.

---

기본 관계식

 

$a = 2, b = 2, d = 1$ 이므로, 아래 경우에 해당한다.

 

따라서, 시간복잡도는 $O(nlogn)$ 이다.

---