분할 정복 알고리즘 (Divide-and-conquer)

필자는 분할 정복 알고리즘을 '협업 또는 분업'이라고 생각한다.

 

대학에서의 조별 과제부터 사회로 진출해 회사에 입사하여 하는 일까지 우리는 살면서 늘 협업과 분업을 하고 있다.

협업이라 하면 '서로 커뮤니케이션을 하면서 하나의 공통된 목적을 이루는 것이 처음 생각나는 것'이 겠지만 본질적으로는 한 사람이 전부 하기에는 시간적인 제약과 분야에 따른 능력적 제약이 있기 때문에 일을 나누는 것이다.

일을 나누면 결론적으로는 효율이 올라가기 때문이다.

분업은 말그대로 '업무를 나누는 것'이다. 한가지 일을 한사람이 하는 것 보다는 두사람이 하는 것이 시간적으로 많이 단축될 것이다.

 

생각을 해보자. 어느 기업이 있다. 기업이 성장하려면 여러 분야에서 성과를 보여야한다.

기본적인 사업모델부터 마케팅, 제무관리 등, 여러분야에서 일을 할 필요가 있다.

물론 능력이 되어서 1인 기업을 운영할 수도 있다. 하지만 기업이 성장하여 혼자서 모든 부담을 지는데에는 한계점이 있다.

따라서 기업에는 직책이 있다. 가장 책임이 크고 권한이 많은 C라인(CEO, CTO, COO 등)부터 말단의 인턴까지 여러 직책이 존재한다.

더 나아가서 하청, 외주 등이 있지만 기업이 돌아가는 글을 쓰는 것이 아니므로 넘기겠다.

 

 

 

 

요는 능률과 효율이 올라가라면 협업과 분업을하여 일을 해야한다. 처리해야하는 업무량이 많을 수록 말이다.

분할 정복도 마찬가지이다. 일을 나누어서 해결하고 합치는 과정이라고 생각하면된다.

 

분할 정복

주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘, 분할된 입력에 대해 동일한 알고리즘을 적용하여 해를 계산하고 이들의 해를 취합하여 원래 문제의 해를 얻는다.

 

사전적 정의를 보면 분할 정복과 협업은 조금은 다르지만 문제(일)를 나눈다는 부분은 같다. 

 

주어진 문제에서 분할된 문제를 우리는 부분문제(subproblem)이라고 부르며 부분문제의 해를 부분해라고 한다. 

분할 정복 알고리즘은 부분문제를 더 이상 분할 할 수 없을 때까지 분할하는 것을 기억하자.

 

부분문제를 더 이상 분할할 수 없을 때까지 분할한다.

 

분할한 총 횟수를 k라고 하고 입력크기를 n이라고 하면 k번 분할 할 경우 각각의 입력 크기는 n/2^k임을 알 수 있다.

입력의 크기가 n/2^k = 1이 될 경우 더 이상 분할 할 수 없으므로, 총 분할될 수 있는 횟수 k = log2n임을 알 수 있다.

 

대부분의 분할 정복 알고리즘은 input된 문제를 단순히 분할만 해서는 해를 구할 수 없다.

따라서 분할된 문제를 해결, 부분해를 구해야 한다.

문제를 정복하는 방법은 문제에 따라 다르나 일반적으로는 부분문제의 해를 취합하여 상위의 부분문제의 해를 구한다.

 

 

문제를 분할하고 취합하는 과정(합병 정렬)

 

분할정복의 종류

분할 정복 알고리즘은 분할되는 부분문제의 수와 부분문제의 크기에 따라 분류될 수 있다.

 

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

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

    - a = 7, b = 2 인 경우: 스트라센(Strassen)의 행렬 곱셈 알고리즘

 

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

    - 퀵 정렬

 

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

    - 이진탐색

 

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

    - 선택 문제 알고리즘

 

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

    - 삽입정렬

    - 피보나치 수의 계산

 

위에 나온 여러가지 종류의 분할정복 알고리즘은 하나하나 블로그에 투고할 예정이다.

 

 

분할 정복을 적용하는 데 있어서 주의해야할 점

분할 정복이 부적절하게 적용되는 경우는 문제가 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전 크기 보다

매우 커지는 경우다. 이러한 경우에는 분할 정복 알고리즘을 사용하는 것은 매우 부적절하며, 다른 방법을 찾아야한다.

 

 

 

 

잘못된 정보나 오류, 오타, 독자 입장에서의 수정사항 및 피드백 환영합니다. 

E-mail : jhmh0226@gmail.com