분할 정복

분할 정복이란?

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤,

각 부분 문제에 대한 답을 재귀 호출을 이용(basecase : 상수 크기의 부문제들)해 계산하고,

그 답으로 부터 전체 문제의 답을 계산

일반적 재귀 호출과의 차이점 ?

문제를 나누는 크기 !

재귀 호출은 문제를 한 조각과 나머지 전체로 나누지만, 분할 정복은 거의 같은 크기의 부분 문제로 나눔

예제 1) 분할 정복을 이용한 수열의 합 구하기

fastSum(n) 

= 1+2+3+...+n 

= (1+2+3+..+n/2) + ((n/2+1)+...+n)

= (1+2+3+..+n/2) + (n/2+1) + (n/2+2) + ... + (n/2 + n/2)

= (1+2+3+..+n/2) + n/2 * n/2 + (1+2+...+n/2)

= fastSum(n/2) + n/2 * n/2 + fastSum(n/2)

 

코드

#include <iostream>
using namespace std;

int fastSum(int n) {
	if (n == 1) return 1;
	if (n % 2 == 1) return fastSum(n - 1) + n;
	return 2 * fastSum(n / 2) + n / 2 * n / 2;
}

예제2) 병합 정렬과 퀵 정렬

병합정렬 (Merge sort) ?

• 수열을 가운데에서 쪼개 비슷한 크기의 수열 2개로 만든 후, 재귀 호출을 통해 각각 정렬 → 정렬된 배열을 하나로 합침
• 즉, 각 수열의 크기가 1이 될 때까지 절반씩 쪼갠 후, 정렬된 부분 배열들을 다시 합침
• 실행시간 : O(nlogn)
  ▶ 주어진 배열을 절반으로 나누는 시간 + 정렬한 배열들을 하나의 배열로 합치는 시간 = O(1) + O(n) = O(n)
  ▶ 배열은 절반으로 나누어지기 때문에 필요한 단계의 수는 logn

퀵 정렬 (Quick sort) ?

• 병합 정렬 방법에서 병합 과정이 필요없도록 한쪽 배열에 포함된 수가 다른 쪽 배열보다 항상 작도록 배열 분할
• 배열에서 임의의 기준 수(pivot)를 지정한 후, 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보냄(파티션 단계라고 부름)
• 최악 실행시간 : O(n^2) → 기준으로 택한 원소가 최소/최대인 경우
• 기대 실행시간 : O(nlogn)