Algorithms : Divide-and-Conquer

이 포스트에서는 Divide-and-Conquer 알고리즘에 대한 설명을 다룬다.

Divide-and-Conquer

• 개요

문제를 작은 하위 문제들로 분할(divide)하여, 하위 문제들을 재귀적으로 해결(conquer)하고, 결과를 조합(combine)하여 원래 문제의 해를 구하는 상향식 알고리즘 설계 방식

Divide-and-Conquer 일반 구조

1. Divide: 문제를 하나 또는 여러 개의 하위 문제로 분할
2. Conquer: 각 하위 문제를 재귀적으로 해결
3. Combine: 하위 문제의 해를 결합해 원래 문제의 해를 구함

Binay Search(이진 탐색)

• 정렬된 배열에서 원하는 키 x를 탐색하는 알고리즘.
• 중간값과 비교 후, 작으면 왼쪽, 크면 오른쪽 하위 배열에서 반복.
• 재귀 버전을 통해 Divide-and-Conquer 방식 예시로 활용.
• 특징:
  • Tail Recursion → 반복문으로 쉽게 전환 가능.
  • 반복문이 재귀보다 빠르고 메모리 효율적.
  • 배열은 주소로 전달되므로 불필요한 복사 피할 수 있음 (const 사용).
• 수식

\[T(n) = \text{Divide} + \text{Conquer} + \text{Combine} \\ = 1 + T\left(\frac{n}{2}\right) \\ = 1 + 1 + T\left(\frac{n}{4}\right) = 2 + T\left(\frac{n}{4}\right) \\ = 3 + T\left(\frac{n}{8}\right) \\ \vdots \\ = k + T\left(\frac{n}{2^k}\right)\]

종료 조건 : \(\frac{n}{2^k} = 1 \Rightarrow k = \log_2 n\) 최종식 : \(T(n) = T(1) + \log_2 n\) 따라서, \(T(n) \leq 1 + \log_2 n = O(\log n)\)

Merge Sort

• 두 개의 정렬된 배열을 병합하는 방식으로 전체 배열 정렬.
• 단계:
  1. 배열을 2개의 하위 배열로 나눔 (n/2)
  2. 각 하위 배열을 재귀적으로 정렬
  3. 정렬된 배열들을 병합
• 비교 횟수: 평균적으로 O(n log n)

• In-place 정렬은 아님 (추가 메모리 사용함).

• 수식

\[T(n) = \text{Divide} + \text{Conquer} + \text{Combine}\] \[\begin{align*} T(n) &= ? + T\left(\frac{n}{2}\right) + T\left(\frac{n}{2}\right) + \text{Combine} \\ &= ? + 2T\left(\frac{n}{2}\right) + \left(\frac{n}{2} + \frac{n}{2} - 1\right) \\ &= O(\text{basic operation}) + 2T\left(\frac{n}{2}\right) + (n - 1) \\ &= 2T\left(\frac{n}{2}\right) + n - 1 \quad \text{(recurrent equation)} \end{align*}\] \[\begin{align*} T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\ &= 2\left(2T\left(\frac{n}{4}\right) + \frac{n}{2} \right) + n \\ &= 4T\left(\frac{n}{4}\right) + 2n \\ &= 8T\left(\frac{n}{8}\right) + 3n \\ &\vdots \\ &= 2^k T\left(\frac{n}{2^k}\right) + kn \end{align*}\]

• 종료조건

\[Trick: n = 2^k \Rightarrow \frac{n}{2^k} = 1 \Rightarrow T(1) = \Theta(1)\] \[\begin{align*} T(n) &= n \cdot T(1) + n \log n \\ &= n \cdot O(1) + n \log n \\ &= \boxed{O(n \log n)} \end{align*}\]

• k-way Merge Sort는 어떨까?

• 기존 Merge Sort의 시간복잡도

\[T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log_2 n)\]

• k-way Merge Sort의 시간복잡도

\[T(n) = kT(n/k) + O(n) \Rightarrow O(n \log_k n)\]

일반화 시간복잡도 \(O(n \log_k n) = O\left( \frac{n \log n}{\log k} \right)\)

• 따라서 k가 커질수록 로그의 밑이 커져서 전체 복잡도는 작아짐!

하지만 실제로 무조건 k가 크다고 좋은 것은 아님

1. Merge 단계에서 k개의 리스트를 병합해야 하므로 더 복잡해짐

• 2-way는 2개의 포인터만 쓰면 되지만
• k-way는 k개의 포인터 + 최소 힙(min-heap)을 써야 효율적

1. 캐시/메모리 접근 패턴이 더 복잡해져서 실제 성능이 떨어질 수 있음

• CPU 캐시와 분기 예측 등의 이유로
• 너무 많은 분기로 나누면 오히려 느려질 수 있음

즉 Optimal K의 값은?

이론적으로는 시간복잡도만 본다면 k가 클수록 좋음

실무와 현실에서는 보통 k = 2 또는 3이 가장 빠름.

Quick Sort

• 정렬 기준이 되는 pivot을 선택하고,
  • pivot보다 작은 값은 왼쪽,
  • 큰 값은 오른쪽에 배치

• 이후 각 부분 배열에 대해 재귀적으로 정렬 수행

• partition 함수는 각 원소를 순회하며 pivot보다 작으면 왼쪽으로 이동

• 성능:
  • 최선/평균: O(n log n) (pivot이 중간일 때)
  • 최악: O(n²) (pivot이 최솟값 또는 최댓값일 때)

• 수식

  • Best Case : O(nlogn) \(T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{2}\right) + cn\)

    \[= 2T\left(\frac{n}{2}\right) + cn \quad \text{(Divide: 2 subarrays, Combine: partition)}\]

    이를 반복하면, \(= 2 \left( 2T\left(\frac{n}{4}\right) + c\frac{n}{2} \right) + cn = 4T\left(\frac{n}{4}\right) + 2cn\)

    \[= 8T\left(\frac{n}{8}\right) + 3cn\] \[= 2^k T\left(\frac{n}{2^k}\right) + kcn\] \[기저 조건: \frac{n}{2^k} = 1 \Rightarrow k = \log_2 n\] \[T(n) = nT(1) + cn \log n = O(n \log n)\]

  • Worst Case : O(n^2) \(T(n) = T(0) + T(n-1) + cn \quad \text{(or } T(n) = T(n-1) + cn\text{)}\)

    \[= T(n-1) + cn = T(n-2) + c(n-1) + cn = T(n-3) + c(n-2) + c(n-1) + cn\] \[= T(1) + c(2 + 3 + \cdots + n) = T(1) + c\left( \frac{n(n+1)}{2} - 1 \right) = O(n^2)\]