코딩테스트 - 분할정복 알고리즘

분할정복 알고리즘

큰 문제를 하위 문제로 분할하고, 각 하위 문제를 독립적으로 해결한 후 그 결과를 결합하여 최종 결과를 얻는다

(일반화)

- 특징

분할 정복 알고리즘의 시간 복잡도 O(n^log_b(a))

 

- 절차

1. 분할 : 주어진 문제를 동일한 크기의 하위 문제로 분할

2. 정복 : 하위 문제를 재귀적으로 해결

3. 결합 : 각 하위 문제의 결과를 결합

 

 

- 기본적인 예시 (이진 검색)

def binary_search(arr, low, high, target):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == target:
            return mid

        elif arr[mid] > target:
            return binary_search(arr, low, mid - 1, target)

        else:
            return binary_search(arr, mid + 1, high, target)

    else:
        return -1