분할 정복 알고리즘

문제를 더이상 쪼갤 수 없을 정도로 분할 한 뒤 작은 문제들의 해를 구하고, 필요하면 작은 해를 결합해 원래 문제의 해를 구하는 방법이다.

분할, 정복, 결합 세 단계로 나뉜다.

• 분할: 주어진 문제를 더 이상 나눌 수 없을 때 까지 작은 문제들로 분할한다.
• 정복: 작은 문제의 해를 구한다.
• 결합: 작은 문제의 해를 결합해 원래 문제의 해를 구한다.

이진 탐색, 합병 정렬, 퀵 정렬, 선택 문제가 분할 정복 문제에 해당한다.

이진 탐색

날짜 맞추기 스무고개를 해본다고 생각하자. 상대방은 '업', '다운'만 알려준다. 아무런 정보가 없다면 7월 1일을 선택하는 것이 좋다.(365를 반으로 나누면.. 아무튼 그렇다) 상대방이 '업'을 외치면 7월 1일 이전은 버리면 된다. 문제 크기가 절반으로 줄어들었다. 이렇게 하면 수학적으로 정확히 n번 안에 생일을 맞출 수 있다. 이 것이 이진 탐색이다.

오름 차순으로 정렬 된 배열이라는 전제를 갖는다.

• 분할: 가운데 원소를 기준으로 오른쪽, 왼쪽을 나눈다.
• 정복: 가운데 원소가 탐색키 x와 같은지 보고 크기에 따라 오른쪽, 왼쪽 중 하나를 선택한다.
• 결합: 결합할 필요는 없다.

처음 입력한 배열 크기가 $n$이면 한번 분할하면 $n/2$가 되고 두번 분할하면 $n/2^2$가 된다. 최악의 경우 분할한 문제 크기가 1이 될 때까지 반복한다. 이 횟수를 k라고 두면 $\lfloor n/2^k \rfloor =1$이 될 때까지 반복하는 것이다.

양쪽에 로그를 취하면

$k = \lfloor \log_2n \rfloor$

가 된다. 날짜 맞추기 문제는 8번 안에 해결 할 수 있다.(스무고개라면 무조건 이길 수 있다.) 시간 복잡도는 $\log{n}$이다.

$T(n)=\log{n}+1=O(\log{n})$

1. 목표값 삽입 인덱스를 찾는 문제
2. 제곱근보다 작은 최대 정수를 찾는 문제