분할정복(Divide-and-Conquer)

분할정복(Divide-and-Conquer)

---

분할정복(Divide and Conquer)이란?

분할정복은 프랑스 나폴레옹이 실제로 시도한 전략에서 따온 것으로 오스트리아-러시아 연합군을 상대할 때 중앙으로 돌격하여 병력을 둘로 나누어 나뉜 병력을 각개격파한 것에서 따왔습니다.

 

분할정복은 문제를 작은 하위 문제로 나누고 하위 문제들을 각각 해결한 후 결과를 합쳐서 원래 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 복잡한 문제를 단순하고 효율적으로 해결할 수 있습니다.

 

분할한 입력사례를 바로 답을 구하지 못할 경우 다시 분할하여 답을 구할 수 있을 만큼 충분히 작아질 때까지 입력사례를 분할합니다.

 

즉 분할정복은 3단계의 절차를 거칩니다. 분할(Divide) => 정복(Conquer) => 결합(Combine) 의 절차를 가집니다.

• 분할(Divide) : 문제를 하위 문제들로 나누는 절차입니다.
• 정복(Conquer) : 나뉜 하위 문제들을 해결하는 절차입니다.
• 결합(Combine) : 해결된 문제의 결과를 결합하여 원래 문제를 해결하는 절차입니다.

 

분할정복의 특징

분할정복은 하향식(Top-Down) 문제풀이 방식입니다. 즉 문제의 상위 입력사례의 해답은 하위의 작은 사례들의 해답을 가지고 구하기 때문에 재귀함수가 작동하는 원리와 같습니다.

 

재귀함수는 비효율적이지만 재귀함수의 하위ㅣ 문제를 독립적으로 해결할 수 있게 병렬 처리가 가능할 때 효율적으로 많은 경우와 시간 복잡도를 크게 줄일 수 있습니다.

 

분할정복의 장단점

분할정복의 장점

재귀와 비슷한 방식이기 때문에 코드를 재귀적으로 작성할 수 있어 코드가 간결해지고 이해하기 쉬워집니다. 그리고 문제를 해결하기 위해 여러 하위 문제로 나누고 나뉜 하위 문제들이 독립적이므로 병렬적으로 처리할 수 있어 어떤 복잡한 문제라도 쉽게 해결할 수 있습니다.

 

분할정복의 단점

재귀 호출이 깊어질 수록 스택 오버플로우 가능성이 증가하며 병합 정렬처럼 새로운 배열을 생성해야 하는 경우 메모리 사용량이 증가하게 됩니다.

 

분할정복 설계방법

분할정복(Divide and Conquer) 설계전략은 다음과 같은 절차로 이루어집니다.

1. 문제의 입력사례를 하나 이상의 작은 입력사례로 분할합니다.
2. 작은 입력 사례를 각각 정복합니다. 작은 입력사례가 충분히 작지 않다면 재귀 호출을 합니다.
3. 작은 입력사례의 해답을 통합하여 원래 입력사례의 해답을 구합니다.

3번째 단계는 필수로 진행할 필요가 없습니다. 이분검색 알고리즘같이 분할한 입력사례를 하나만 사용하므로 통합할 필요가 없기 때문입니다.