분할 정복(Divide&Conquer) 알고리즘

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

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘으로, 보통 재귀 함수를 통해 자연스럽게 구현된다. 주어진 문제를 둘 이상의 부분 문제로 나누어 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x 를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

 

주어진 문제를 둘 이상의 부분 문제로 나누어 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.

 

분할 정복이 일반적인 재귀호출과 다른 점은 한 조각과 나머지 전체로 나누는 대신 비슷한 크기의 부분 문제로 나누는 것이다. 

 

분할 정복 알고리즘은 보통 분할(divide), 병합(merge), 더이상 분할하지 않고 풀 수 있는 매우 작은 문제(base case)로 이루어져있다. 

 

이 알고리즘을 사용해 문제를 풀기 위해서는 1. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하고, 2.  부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

빠른 실행이나 부문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐(queue) 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.

 

 

 

 

참조:

도서 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 - 구종만

웹 https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98