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

분할정복 (Divide and Conquer)

이는 재귀함수에 대한 명확한 이해가 필요한 파트이다.

재귀함수가 부족하다고 생각하면 좀 더 공부를 해놓고 학습을 하는 것이 좋겠다.

 

분할정복은 이름 그대로 문제를 분할하여 해결하는 것이다. 이는 총 3단계로 구성된다.

 

1. Divide : 문제를 나눈다.

2. Conquer : 나눠진 문제를 각각 해결한다.

3. Combine : 각각 해결한 두 문제의 답을 결합한다.

 

여기서 생각해야 될 것은 분명 우리는 어떤 문제를 해결하기 위해 분할정복을 시작했다. 그런데 여기서 2번단계를 보면 '나눠진 문제를 각각 해결한다' 라고 한다. 이 말은 결국 무엇이겠는가? 이 2번 단계에서 나눠진 문제에도 각각 분할정복을 적용할 수 있다는 뜻이다. 그리고 당연하게도 그렇게 2번 단계에서 분할한 문제 안에서 또 분할정복을 할 수도 있다. 이는 문제조건이 허락하는 한 무한히 가능할 것이다. (이렇기 때문에 재귀함수에 대한 명확한 이해가 필요하다고 한 것이다.)

 

예를 들어 1부터 8까지 더하는 문제를 생각해보자. 이는 1~4까지 더하는 문제와 5~8까지 더하는 문제로 나눌 수 있다. 이렇게 나눠진 두 문제는 또 1~2까지 더하는 문제와 3~4까지 더하는 문제, 5~6까지 더하는 문제와 7~8까지 더하는 문제로 나눌 수 있다. 마지막으로는 1~1,2~2,3~3,4~4,5~5,6~6,7~7,8~8을 더하는 문제로도 나눌 수 있다. 여기서는 더 나눌 수 없다. (이를 Base-case라고 한다. 재귀에서 보았던 종료조건같은 개념이다.) 이를 모두 각각계산하고 Combine을 한묶음씩 해나가면 결국 1~8까지 더하는 문제를 해결할 수 있다.