분할 정복

• 어떤 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고, 다시 합병하여 문제의 답을 얻는 알고리즘
• 크기가 작아질 뿐 문제 자체는 변하지 않기 때문에, 분할은 재귀적 분할
• 재귀적으로 나타낼 수 있기에 수행시간 $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번째 피보나치 수 계산 방법