Divide-and-Conquer(분할정복법)

Basic Concept

---

Divide-and-conquer is patterned after the brilliant strategy employed by the French emperor Napoleon in the Battle of Austerlitz on December 2, 1805. A combined army of Austrians and Russians outnumbered Napoleon’s army by about 15,000 soldiers. The Austro-Russian army launched a massive attack against the French right flank. Anticipating their attack, Napoleon drove against their center and split their forces in two. Because the two smaller armies were individually no match for Napoleon, they each suffered heavy losses and were compelled to retreat. By dividing the large army into two smaller armies and individually conquering these two smaller armies, Napoleon was able to conquer the large army.

 

👉 분할정복법은 아우스터리츠 전투에서 프랑스 황제 나폴레옹이 구사한 전략을 본 떠서 만든 것이다. 프랑스군은 오스트리아와 러시아 연합군에 비해 수적으로 열세였지만, 나폴레옹이 적 중앙을 돌파하여 적의 부대를 둘로 나누고 각개격파함으로써 전쟁에서 승리할 수 있었다.

 

 

The Divide-and-Conquer Approach

---

It divides an instance of a problem into two or more smaller instances. The smaller instances are usually instances of the original problem. If solutions to the smaller instances can be obtained readily, the solution to the original instance can be obtained by combining these solutions. If the smaller instances are still too large to be solved readily, they can be divided into still smaller instances. This process of dividing the instances continues until they are so small that a solution is readily obtainable. The divide-and-conquer approach is a top-down approach.

 

Top-down Approach

1. Divide

문제를 해결하기 쉽도록 여러 개의 작은 부분으로 나눈다. 이 작은 문제들은 원래 문제의 한 부분이다.

 

2. Conquer - Solve

나눈 문제를 각각 해결한다. 만약 문제가 여전히 커서 쉽게 해결되지 않으면 더 작은 부분으로 나눈다.

 

3. Combine - Obtain the solution

필요하다면 해결된 해답을 모은다.

 

👉 분할정복법은 top-down 방식으로 문제를 해결한다.

 

 

 

When Not to Use Divide-and-Conquer

---

If possible, we should avoid divide-and-conquer in the following two cases. The first partitioning leads to an exponential-time algorithm, where the second leads to a nΘ(logn) algorithm. Neither of these is acceptable for large values of n.

 

Case 1. An instance of size n is divided into or more instances each almost of size n.

입력크기가 n인 문제를 분할하는 과정에서, 각 분할된 문제의 크기가 거의 n인 두 개 이상의 인스턴스로 나뉘는 경우라면 분할정복법 사용을 피해야 한다. 피보나찌 수열을 예로 들면, fib(n)을 구하기 위해 문제를 fib(n-1)과 fib(n-2)로 분할했지만 전체 문제의 크기는 처음 가지고 있던 것보다 더 커져 비효율적인 결과를 초래한다. (n < 2n-3)

// n th Fibonacci Term (Recursive)
fib(n) = fib(n－1) ＋ fib(n－2) // n < 2n-3

👉 첫 번째와 같이 문제를 분할하면 시간복잡도가 지수시간(exponential-time)인 알고리즘이 나온다.

 

Case 2. An instance of size n is divided into almost n instances of size n/c, where c is a constant

입력크기가 n인 문제를 분할하는 과정에서, 거의 n개의 n/c(c는 상수) 크기 인스턴스로 나뉘는 경우라면 분할정복법 사용을 피해야 한다.

 

👉 두 번째와 같이 문제를 분할하면 시간복잡도가 n*Θ(logn)인 알고리즘이 나온다. 입력크기 n 값이 크다면 이 중 어떤 것도 받아들일 수 없다.

결론적으로 입력크기 n 값이 크다면 이 중 어떤 것도 받아들일 수 없다. 따라서 상기 두 가지 경우처럼 분할했을 때의 크기가 처음 가지고 있던 문제의 크기 보다 커지거나 혹은 비슷하다면 분할정복법 사용을 지양해야 한다.