분할 정복 알고리즘에 대해 알아보자

분할 정복은 여러 알고리즘의 기본이 되는 해결방법으로 하나의 큰 문제를 작은 단위로 나눈 후 다시 합치면서 문제를 해결합니다. 대표적인 알고리즘으로는 퀵 소트나 병합 정렬이 있습니다.

위 그림과 같이 분할 정복은 상단에서 분할을 한 후 중앙에서 정복하고 마지막 하단에서는 조합을 하는 형태입니다.

• 분할 : 문제를 더 이상 분할할 수 없을 때까지 동일한 유형으로 문제를 가장 작은 단위로 나눈다.
• 정복 : 가장 작은 단위의 문제를 해결하여 정복합니다.
• 조합: 가장 작은 문제에 대한 결과를 원래 문제에 대한 결과로 조합하여 해결합니다.

 

분할 정복 적용 방식

분할 정복법은 재귀적으로 자신을 호출함으로써 그 연산의 단위를 조금씩 줄여가는 방식입니다.

function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

즉, “F(x)가 간단”이라는 조건을 만족할 때까지 문제를 가장 작은 단위로 쪼개서 값을 구하는 것입니다.

장점

문제를 작은 단위로 나눔으로써 복잡하고 어려운 문제를 해결이 가능하다는 장점을 가지고 있습니다. 또한 이 방식을 그대로 사용하여 해결하는 알고리즘인 병합정렬은 시간 복잡도가 O(n log n)을 가집니다. 문제를 나누면서 해결하는 특징상 병렬적으로 문제를 해결한다는 큰 강점을 가지고 있습니다.

단점

• 재귀적으로 함수 호출함에 있어 오버헤드를 발생시킬 수 있습니다.
• 스택에 다양한 데이터를 보관해야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용하는 단점이 있습니다.

예시

• 퀵소트
• 합병정렬
• 고속 푸리에 변환
• 카라추바 알고리즘