분할 정복법 요약

• Top-Down 접근법
• trival 한 작은 instances로 나누고 문제를 해결
• 재귀적인 관계가 비효율적일 때가 있다. ex) 피보나치 수열

분할 정복법(Divide and Conquer)

1. 귀납법 - 예시 문제

귀납법은 수학적 증명 기법 중 하나로, 범위가 무한하게 계속되는 성질을 증명할 때 사용합니다. 예를 들어, 모든 자연수에 대해 주어진 명제가 참임을 증명하고자 할 때 사용됩니다.

예제 문제:
자연수 ( n )에 대해 ( 1 + 2 + \cdots + n = \frac{n(n+1)}{2} )임을 귀납법으로 증명하시오.

증명 과정:

• 기본 단계: ( n = 1 ) 일 때, 좌변은 ( 1 ), 우변은 ( \frac{1(1+1)}{2} = 1 )로 명제가 성립합니다.
• 귀납 단계: ( n = k )일 때 성립한다고 가정하면, ( n = k+1 ) 일 때, ( 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) )를 통해 증명할 수 있습니다. 이는 (\frac{(k+1)(k+2)}{2})와 같으므로 귀납적으로 성립함을 확인할 수 있습니다.

2. 분할 정복법의 정의 및 설계 기법 - Merge Sort 코드 예제

Merge Sort(합병 정렬) 는 분할 정복법의 대표적인 예입니다. 배열을 반으로 나눈 다음, 각 부분을 재귀적으로 정렬하고, 마지막에는 두 정렬된 리스트를 합쳐 전체를 정렬합니다.

def merge(left, right):
    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.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
    

Even Split에서의 분할 정복법 설명

Even split에서는 문제를 가능한 한 동일한 크기의 서브 문제로 나눕니다. 예를 들어, Merge Sort는 배열을 계속해서 반으로 나누는 것이 even split에 해당합니다.

쉬트라쎈 행렬 곱(Strassen's Matrix Multiplication)

쉬트라쎈 행렬 곱은 복잡한 행렬 곱셈을 보다 효율적으로 수행하기 위해 개발된 분할 정복 알고리즘입니다. 이 알고리즘은 특히 큰 행렬을 곱할 때 일반적인 방법보다 적은 수의 곱셈 연산을 사용합니다.

작동 원리

쉬트라쎈 알고리즘은 (2 \times 2) 행렬 곱셈에 필요한 곱셈 연산을 8번에서 7번으로 줄입니다. 이 접근 방식은 재귀적으로 (n \times n) 행렬에 적용되어 연산량을 대폭 감소시킵니다.

예시

(2 \times 2) 행렬 (A)와 (B)의 곱은 다음과 같은 7개의 곱셈을 사용하여 계산할 수 있습니다.

• (P1 = (A{11} + A{22}) \times (B{11} + B{22}))
• (P2 = (A{21} + A{22}) \times B_{11})
• (P3 = A{11} \times (B{12} - B_{22}))
• (P4 = A{22} \times (B{21} - B_{11}))
• (P5 = (A{11} + A{12}) \times B_{22})
• (P6 = (A{21} - A{11}) \times (B{11} + B{12}))
• (P7 = (A{12} - A{22}) \times (B{21} + B{22}))

결과 계산

최종 행렬 (C)는 이 7개의 곱셈 결과를 이용해 구성됩니다.

마스터 이론(Master Theorem)

마스터 이론은 재귀적 알고리즘의 시간 복잡도를 해석하는 데 유용한 도구입니다. 주로 분할 정복 알고리즘의 복잡도를 계산할 때 사용됩니다.

주요 개념

재귀식 (T(n) = aT\left(\frac{n}{b}\right) + f(n))이 주어졌을 때, (T(n))의 복잡도를 결정하기 위해 (f(n))과 (n^{\log_b{a}})의 성장률을 비교합니다.

시간 복잡도 분류

• 경우 1: (f(n) = O(n^{\log_b{a} - \epsilon})) for some (\epsilon > 0)
  • (T(n) = \Theta(n^{\log_b{a}}))
• 경우 2: (f(n) = \Theta(n^{\log_b{a} \cdot \log^k{n}})) for some (k \geq 0)
  • (T(n) = \Theta(n^{\log_b{a}} \cdot \log^{k+1}{n}))
• 경우 3: (f(n) = \Omega(n^{\log_b{a} + \epsilon})) for some (\epsilon > 0)
  • (T(n) = \Theta(f(n)))

Uneven Split

분할 정복 알고리즘에서 데이터를 균일하지 않게 나누는 경우를 uneven split이라고 합니다. 대표적으로 이진 검색과 퀵소트가 이에 해당합니다.

이진 검색(Binary Search)

• 배열의 중간점을 찾아 한 쪽은 한 개의 요소만 포함하고, 다른 쪽은 나머지 요소를 포함하도록 나눕니다.
• 재귀적으로 검색 범위를 줄여가며 원하는 값을 찾습니다.

퀵소트(Quick Sort)

• 피벗 선택에 따라 배열을 피벗보다 작은 요소와 큰 요소로 나눕니다.
• 이 과정에서 분할의 크기가 균일하지 않을 수 있습니다.
• 선택된 피벗의 위치에 따라 한 쪽 분할은 매우 작을 수 있고, 다른 쪽은 매우 클 수 있습니다.