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

분할 정복이란?

 

분할 정복으로 통칭하는 이 패러다임은 한 문제를 유형이 비슷한 여러 개의 하위 문제로 나누어 재귀적으로 해결하고 이를 합쳐 원래 문제를 해결한다. 분할 정복 방식이 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 한다. 분할 정복 알고리즘을 이해하기 위해 다음과 같이 세 부분으로 나눠서 생각해보자.

1. 분할(divide): 문제가 분할이 가능한 경우 2개 이상의 하위 문제로 나눈다.
2. 정복(conquer): 하위 문제가 여전히 분할 가능하면, 또 다시 분할을 수행한다. 그렇지 않으면 문제를 푼다.
3. 합치기(combine): 정복한 하위 문제들의 답을 합쳐서 원래 문제를 해결하자.

 

• 문제를 제대로 나누면 conquer하는 것은 쉽기 때문에 divide를 제대로 하는 것이 가장 중요.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

분할 정복 알고리즘의 단계를 분할, 정복, 합치기 세 개로 나누면 쉽게 기억할 수 있다. 분할 단계에서 하위 문제가 두 개 생긴다고 가정하면 이 알고리즘은 아래 그림으로 정리할 수 있다. (일부 분할 정복 알고리즘은 하위 문제 두 개 이상으로 이루어질 수 있다.)

재귀적 문제를 두 개 더 만들어 확장할 경우 다음과 같이 나타낼 수 있다.

 

분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 여러번 재귀 호출을 한다.

 

 

 

 

 

출처:https://ko.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5