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

분할 정복 알고리즘은 이름에서 부터 알 수 있듯, 그대로 해결할 수 없는 문제를 거의 같은 크기의 여러개의 작은 문제로 분할하여 해결하는 방법이다.

또한 분할 정복 알고리즘의 경우 보통 재귀함수를 통해서 구현되지만 거의 같은 크기의 문제로 나눠야 한다는 것에 차이가 있다.

 

분할 정복의 구성

1) 주어진 문제를 여러개의 부분 문제로 나눈다. (divide)

2) 재귀 함수를 통해서 각각의 부분 문제를 해결한다 (conquer)

3) 각 부분의 문제의 답으로 부터 전체 문제의 답을 계산한다. (merge)

 

문할 정복의 적용을 위해 요구되는 특성

1) 문제를 둘 이상으로 나누는 자연스러운 방법이 있어야한다.

2) 부분 문제의 답을 조합하여 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

 

문할 정복 문제의 경우는 어떻게 분할 하느냐에 따라서 효율성의 차이가 많이 발생한다. 따라서 문제를 해결하기 위해 분할을 잘 하는 것이 중요하다.

 

분할 정복의 장점

작은 문제로 분할하여 같은 작업을 더 빠르게 처리할 수 있게 해준다. (효율성 증가)

어려운 문제를 간단한 작은 문제로 나누어 쉽게 해결할 수 있다.