분할 정복(Divide and Conquer)

 기법의 이름 그대로 큰 문제를 분할하여, 작은 문제들(Sub problems)로 나눈 뒤 그 결과들을 합쳐 기존의 큰 문제를 해결해나가는 기법입니다.

 네이버 사전에 검색하면 아래와 같은 결과가 나옵니다.

 분할정복의 경우 재귀적으로 해결하는 방식이 가장 많이 사용되곤 합니다. 위 사전에서 설명하듯 성질이 같은 여러 개의 부분 문제로 쪼개고, 쪼개진 문제(Sub problem)에서 동일한 방식으로 다시 쪼개고, 쪼개고 ... 쪼개다가 더이상 나눌 수 없을 경우 해당 Sub problem에서 해를 구하고 재귀적으로 돌아오면서 전체의 큰 문제를 해결합니다.

 예를 들어 아래와 같은 [배열에서 1의 개수]를 구하는 문제가 있다고 합시다.

 (물론 2차원 배열이기 때문에, 2중 반복문을 통해 1의 개수를 찾는 것이 가장 간단한 방법이 될 수 있습니다.)

 

 저희는 분할정복방식으로 문제를 해결할 것이기 때문에, 해당 8 X 8 배열(Problem)을 우선 4 X 4 배열들(Sub problems)로 나누어 봅니다.

 그러면 저희는 4 X 4 [배열에서 1의 개수]를 구하는 작은 문제들을 해결한 뒤, 그 결과를 모두 더하면 기존의 문제를 해결할 수 있습니다.

 4 X 4 역시 2 X 2의 Sub problems들로 나눌 수 있습니다. 위 배열들 중 왼쪽 상단의 것을 분할하게 되면 아래와 같이 됩니다.

 2 X 2 역시 1 X 1의 Sub problems로 나눌 수가 있습니다. 이 때 1 X 1은 더이상 분할할 수 없으며, 1 X 1에서 충분히 1의 유무를 알 수 있습니다. 다시 말해 해결가능한 Sub problem이 됩니다. (이 때 1이 있다면 return 1, 아니라면 return 0과 같이 간단하게 반환하면 됩니다.)

 해결가능한 단계까지 분할한 후, 1의 개수를 다시 재귀하며 전체의 문제에 대한 해답을 구하면 됩니다.

 최종적으로 위와 같은 형태로 분할된 문제를 재귀적으로 해결해나가며 기존의 문제에 대한 해답이 10임을 알 수 있습니다.

 분할정복 기법은 다양한 형태로 응용이 가능합니다. 따라서 기존의 성질이 무엇인지를 가장먼저 파악하고, 작은 문제들로 어떻게 분할해 나갈지를 가장 먼저 고민해야 합니다. 그 후, 분할 후 해결가능한 문제가 되었을 때 어떠한 방식으로 문제를 해결할지와 어떠한 방식으로 결과를 합쳐나갈지를 고민하면 됩니다. (이 고민하는 과정이 굉장히 흥미로운 기법입니다.)

 다양하게 응용될 수 있는 유형으로, 주로 다른 기법들과 함께 사용되곤 합니다.

 

 P.S. 분할정복 문제와 병렬처리를 연관지어서 공부하시면 큰 도움이 될거라고 생각합니다.