개요

문제를 2개 이상의 작은 문제로 분할하고 부분 해를 구한 다음 그 해들을 통합해 전체 해를 구하는 방법

그림과 같이, Divide and Conquer(분할 정복) Algorithm의 경우에는 일반적으로 세 가지 단계를 포함한다.

1. 분할 단계
   • 주어진 문제를 2개 이상의 작은 사례로 분할
2. 정복 단계
   • 작은 사례를 바탕으로 더 작은 사례로 분할하고 더 이상 분할할 필요가 없으면 부분 해를 구함
3. 통합 단계
   • 부분 해를 합쳐 문제의 전체 해를 구함

예시

거듭제곱

일반적인 알고리즘

일반적으로 거듭제곱을 구하는 방법에 대해서 생각한다면, 우리는 상대적으로 간단하게 이러한 방법을 생각해 볼 수 있다.

def power(base: float, exponent: int) -> float:
    result: float = 1.0
    for _ in range(0, exponent):
        result *= base
    return base

간단하게 사용자로부터 밑과 지수를 받아오고, 지수만큼 밑을 곱해주는 형식으로 거듭제곱의 값을 구할 수 있을 것이라고 생각할 수 있다. 우리가 $2^3$이라는 연산의 참값을 구하기 위해 2를 세 번 곱해야 겠다고 생각하는 것처럼.

이 알고리즘의 시간 복잡도는 $O(n)$이다. 지수가 작을 때에는 큰 문제가 발생하지 않지만 지수가 커질 경우 실행 시간이 길어지는 문제가 발생한다.

고속 거듭제곱 알고리즘

이를 상대적으로 더 짧은 시간에 구할 수 있는 방법이 있을까?

놀랍게도 존재한다. Divide and Conquer 알고리즘의 대표적인 예시 중 하나이기도 한 이 알고리즘은 $O( \log n )$이라는 시간 복잡도를 갖는다.

def fast_power(base: float, exponent: int) -> float:
    result: float = 1.0
    while (exponent):
        if (exponent % 2 == 1):
            result *= exponent
        exponent *= exponent
        b //= 2
    return result

이를 식으로 나타내 보면 아래와 같다.

거듭제곱의 제곱을 활용해 결과 값을 구하기 때문에 $2^8$을 구하기 위해 8번 곱할 필요 없이 $2$, $2^2=4$, $(2^2)^2= 2^4$, $((2^2)^2)^2=2^8$으로 3번의 연산 만으로 구할 수 있다.

이를 활용하여 연산량을 획기적으로 감소시킨 것이 고속 거듭제곱 알고리즘이다.

정렬

정렬에서도 Divide and Conquer 알고리즘을 바탕으로 시간 복잡도를 낮출 수 있는 방법이 존재한다. 병합정렬(Merge Sort)과 퀵정렬(Quick Sort), 기수정렬(Radix Sort)가 대표적인 예시이다. 이 알고리즘들은 추후 정렬 알고리즘에 대해 다룰 때 심도 있게 다룰 예정이다.