다음은 7개의 숫자를 가진 배열 [3, 7, 6, 1, 9, 3, 2]을 오름차순으로 정렬하는 예제 입니다.

1. 배열의 첫 숫자 3을 피벗(기준)으로 삼습니다.
2. 순서대로 숫자를 확인하며 피벗(기준)값보다 작은 값은 A배열에, 크거나 같은 값은 B 배열로 이동시킵니다.
3. 한바퀴를 다 돌고나면 A배열은 3 미만의 숫자 모음, B 배열은 3이상의 숫자 모음이 됩니다. A : [1, 2] B : [7, 6, 9, 3]
4. (A - 피벗 - B) 순서로 합치면 다음과 같이 같이 정렬이 됩니다. ([1, 2], 3, [7, 6, 9, 3])
5. 1 페이즈가 종료되었습니다.
6. A 배열과 B 배열을 정렬하기 위해 각각을 다시 1번부터 반복합니다.

7개의 숫자 정렬이였던 문제가 2개의 숫자 정렬(A)과 4개의 숫자 정렬(B) 문제로 더 간단해졌습니다. A 배열 같은 경우 정렬해야 할 숫자가 두 개이므로 바로 비교하여 순서를 정할 수도 있습니다.

2 페이즈가 끝나면 똑같이 묶었을 때 다음과 같은 형태가 됩니다.

(1, [2]), 3, ([6, 3], 7, [9])

생성된 배열 길이가 하나가 될때까지 같은 작업을 반복합니다.

1, (2), 3, ([3], 6), 7, 9

오름차순 정렬이 완료되었습니다.

이처럼 분할 정복을 사용하면 큰 문제(어려운 문제)를 작은 문제(쉬운 문제)로 쪼개고 합쳐서 어려운 문제를 쉬운 문제만으로 해결할 수 있습니다.

감사합니다.

모든 재귀함수가 분할정복을 풀기위해 사용되는 것은 아니며, 분할정복이 재귀함수로만 구현할 수 있는 것도 아닙니다. 재귀함수는 단순히 도구일 뿐입니다.

아주 쉬운 예를 들어 n 이하의 홀수를 역으로 출력하는 프로그램을 재귀함수를 사용해서 만든다고 할때 아래와 같이 만들 수 있습니다.

#include <stdio.h>
void oddPrint(int i);
int main(){
    oddPrint(8);
    return 0;
}
void oddPrint(int i){
    if (i<0)
        return;
    if (i%2 != 0){
        printf("%d\n",i);
    }
    i--;
    oddPrint(i);
}

분할정복 문제도 루프를 통해서 페이즈 1, 페이즈 2 와 같이 단계로 나누어서 작성할 수도 있습니다.

재귀함수는 단순히 자기 자신을 호출할뿐인 함수입니다.

분할정복을 대부분 재귀함수로 작성하는 이유는 재귀함수의 유용성에 대해 가르치기 쉬운 점과 분할정복을 사람이 이해하기 쉽게 작성하는데 편리하기 때문입니다.

실제로는 컴퓨터의 리소스 낭비가 심하기 때문에 재귀함수를 권장하지는 않는 것으로 알고있습니다.

감사합니다.

간단한 일상의 예를 들어볼께요.

32팀 중에서 1등을 결정할려고 해요.

16팀씩 두그룹을 만들어요. 각 그룹에서 1등을 뽑아와서, 그 두 1등끼리 싸워서 이기는 놈이 1등이에요.

이제, 각 그룹에서

16팀 중에서 1등을 결정할려고 해요.

8팀씩 두그룹을 만들어요. 각 그룹에서 1등을 뽑아와서, 그 두 1등끼리 싸워서 이기는 놈이 1등이에요.

이제, 각 그룹에서

8팀 중에서 1등을 결정할려고 해요.

4팀씩 두그룹을 만들어요. 각 그룹에서 1등을 뽑아와서, 그 두 1등끼리 싸워서 이기는 놈이 1등이에요.

...