분할 정복 알고리즘

분할 정복 알고리즘

주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘

- 분할한 입력에 대하여 동일한 알고리즘 적용해 해 계산

- 이들의 해 취합하여 원래 문제의 해 얻음

분할

1이 되어 더 이상 쪼개질 수 없을 때까지 분할

<예제>: 총 분할 횟수=k일 때

정복

대부분의 문제는 분할만 해서 해를 구할 수 없다.

부분해를 찾아 정복해야 하는데, 정복하는 방법은 문제에 따라 다르다.

일반적으로 부분 문제들의 해를 취합하여 보다 큰 부분 문제의 해를 구한다.

(정렬의 경우 혼자 있는 것만으로 정복 완료)

분할되는 부분문제의 수와 부분문제의 크기에 따라 다음과 같이 분류

문제가 a개로 분할되고, 부분 문제 크기가 1/b로 감소하는 알고리즘

1. a=b=2인 경우: 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제

2. a=3, b=2인 경우: 큰 정수의 곱셈(위 예제)

3. a=4, b=2인 경우: 큰 정수의 곱셈(아래 예제-"기본 곱셈")

4. a=7, b=2인 경우: 스트라센의 행렬 곱셈 알고리즘

<예제>

2. 큰 정수의 곱셈(기본 곱셈)

a=4, b=2

문제가 4개로 분할되고 부분 문제 크기가 1/2로 줄어듦

ex. 8자리라면 4개씩 쪼갬

그 결과 다음과 같이 4번의 곱셈으로 나누어짐

세 개의 곱셈으로 줄이면 시간 복잡도는 다음과 같다.

분할 정복 알고리즘의 분류

1. 퀵 정렬

: 문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

2. 이진 탐색

: 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 1/2로 감소하는 알고리즘

3. 선택 문제 알고리즘

: 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 감소하는 알고리즘

4. 삽입정렬, 피보나치 수의 계산

: 부분 문제의 크기가 1,2개씩 감소하는 알고리즘

dustn