03. Divide & Conquer 분할정복

분할 정복

• 어떤 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고, 다시 합병하여 문제의 답을 얻는 알고리즘
• 크기가 작아질 뿐 문제 자체는 변하지 않기 때문에, 분할은 재귀적 분할
• 재귀적으로 나타낼 수 있기에 수행시간 $T(n)$은 점화식으로 표현될 수 있음
• Selection에서 배운 quick_select, MoM 알고리즘 모두 분할 정복 알고리즘

---

$a^n$ 계산하기

1. 선형 재귀 호출

def power1(a, n):
    if n == 1:
        return a
    return a * power1(a, n - 1)

• 수행시간

  2. 이진 재귀 호출

def power2(a, n):
    if n == 1:
        return a
    if n == 0:
        return 1
    if n % 2 == 0:
        return power2(a, n // 2) * power2(a, n // 2)
    return power2(a, n // 2) * power2(a, n // 2) * a

• 수행시간

3. 더 빠른 이진 재귀 호출

def power3(a, n):
    if n == 0:
        ****return 1
    x = power3(a, n // 2)
    if n % 2 == 0:
        return x * x
    return x * x * a

• 수행시간

---

이진 탐색

• 오름 차순으로 정렬된 n개의 숫자가 저장된 리스트 A에서 어떤 값 x가 리스트에 있는지 없는지 $O(logn)$에 알 수 있는 방법
  1. x와 리스트 A의 가운데 값 A[(i+j)/2]를 비교하여 범위를 반으로 줄이는 방법
  2. 한 번의 비교로 탐색 범위가 반으로 줄어듦 → $logn + 1$번 이하의 비교로 x의 존재 여부 결정 가능
  3. 주어진 크기의 문제를 반으로 나눠 작은 문제를 해결하는 분할정복 알고리즘

def binary_search(A, i, j, x):
    if i > j:   # 탐색 범위 내에 없다
        return None

    m = (i + j) // 2    # 중간 인덱스
    if x == A[m]:   # x 발견
        return m
    elif x < A[m]:  # 왼쪽 반 탐색
        return binary_search(A, i, m - 1, x)
    else:           # 오른쪽 반 탐색
        return binary_search(A, m + 1, j, x)

---

n번째 피보나치 수 계산 방법

• 일반 재귀함수
  • 간단하지만, 수행시간이 $O(\phi^n)$. 지수(exponential) 시간이 걸림

def fibo_rec(n):
    if n < 1:
        return 1
    return fibo_rec(n - 1) + fibo_rec(n - 2)

• 변수 3개만을 이용한 방법
  • $O(n)$ 시간.
  • Dynamic Programming ⇒ 공간 복잡도까지 최적

def fibo_three(n):
    prev = 0
    current = 1
    for i in range(2, n + 1):
        temp = prev + current
        prev = current
        current = temp
    return current

• 배열에 0번째 수 부터 n번째 수까지 차례대로 채우는 방법
  • Dynamic Programming ⇒ $O(n)$ 시간
  • Tabulation 방법

def fibo_array(n):
    array = [0, 1]
    for i in range(2, n + 1):
        array.append(array[i - 1] + array[i - 2])
    return array[n]

• power함수 논리 응용
  • power(a, n) = $a^n$ 을 $O(logn)$ 시간에 계산하는 방법을 응용
  • $\left[
    \begin{matrix}
    F_{n+1} \
    F_n \
    \end{matrix}
    \right] =$ $A^n$$\left[
    \begin{matrix}
    F_1 \
    F_0 \
    \end{matrix}
    \right],$ $(A = \left[
    \begin{matrix}
    1 & 1 \
    1 & 0 \
    \end{matrix}
    \right])$

def fibo_pow(n):
    SIZE = 2
    ZERO = [[1, 0], [0, 1]] # 행렬의 항등원
    BASE = [[1, 1], [1, 0]] # 곱셈을 시작해 나갈 기본 행렬

    # 두 행렬의 곱을 구한다
    def square_matrix_mul(a, b, size=SIZE):
        new = [[0 for _ in range(size)] for _ in range(size)]

        for i in range(size):
            for j in range(size):
                for k in range(size):
                    new[i][j] += a[i][k] * b[k][j]

        return new

    # 기본 행렬을 n번 곱한 행렬을 만든다
    def get_nth(n):
        matrix = ZERO[:]
        tmp = BASE[:]

        if n == 0:
            return matrix

        x = get_nth(n // 2)

                if n % 2 == 0:
            return square_matrix_mul(x, x)  # x * x
        return square_matrix_mul(square_matrix_mul(x, x), tmp)  # x * x * a

    return get_nth(n)[1][0]

• 참고자료

---

큰 수 곱셈하기(Karatsuba Algorithm)

$A = a_{n-1}\cdots a_1a_0,\quad B = b_{n-1}\cdots b_1b_0$ 의 정수라고 하면,

$A \times B = a_{n-1}\cdots a_1a_0 \times b_{n-1}\cdots b_1b_0$
$= a_{n-1}\cdots a_1a_0 \times b_0$ << $b_0$와 n번 곱셈 수행

$+ \ a_{n-1}\cdots a_1a_0 \times (b_1 \times 10)$ << $b_1$와 n번 곱셈 수행, 마지막 0 추가

$+ \cdots$

$+ a_{n-1}\cdots a_1a_0 \times (b_{n-1}\times 10 ^{n-1})$ << $b_{n-1}$과 n번 곱셈 수행, 마지막 0 n-1개 추가

⇒ $n^2$번의 기본 곱셈, $2n^2$번의 기본 덧셈

$T(n) =$ n 자리수의 두 수를 곱하는데 필요한 기본 연산($+$, $\times$) 횟수

$T(n) = 3n^2 \rightarrow O(n^2)$

위의 방법보다 기본 연산 횟수를 줄일 수 없을까?

$u = a_{n-1}\cdots a_{\frac n 2}a_{\frac n 2 + 1} \cdots a_1a_0 = x\cdot10^{\frac n 2} + y$

$v = b_{n-1}\cdots b_{\frac n 2}b_{\frac n 2 + 1} \cdots b_1b_0 = w\cdot10^{\frac n 2} + z$ 라고 표현,

$u\times v = (x \cdot 10^{\frac n2} + y)\times(w \cdot 10^{\frac n2} + z)$
$= x \cdot w \cdot 10^{\frac n 2} + (x \cdot z + y\cdot w)\cdot 10^{\frac n2} + yz$
⇒ $x,\ y,\ w,\ z$ 모두 $\frac n 2$자리 숫자다. 즉, $x\cdot w$과 같은 연산은 $\frac n 2 \times \frac n 2$ 자릿수의 곱셈!

결국, $n\times n \rightarrow \frac n 2 \times \frac n 2$ 자릿수들의 연산으로 바뀐 것

$T(n) = T(\frac n 2)\times 4 + c \times n \quad T(1) = c, \ n = 2^k$
$=4^2T(\frac n {2^2}) + 2 cn + cn$
$\vdots$
$=4^kT(\frac n {2^k}) + cn(1 + 2+ \cdots + 2^{k-1}) = O(4^k) = O(n^2)$

그래도 아직 $O(n^2)$이다!

$\frac n 2$ 자리수 곱셈 문제를 3개까지 줄여보자.

$u\times v = x \cdot w \cdot 10^ n + (xz +yw)\cdot 10^{\frac n2} +yz$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \downarrow$
$\quad\quad \quad \quad {(x+y)(w+z)-xw-yz }$

n자리 $\times$n자리 = $(\frac n 2$자리$\times$ $\frac n 2$ 자리$)\times2$ $+ (\frac n 2 + 1)$자리 $\times(\frac n 2 + 1)$자리 + $cn$

$T(n) = 2T(\frac n 2) + T(\frac n 2 + 1) + cn = 3T(\frac n 2)+cn$
$\rightarrow O(n^{log_2 3})$