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

출처:http://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

분할정복

정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.

알고리즘을 설계하는 요령

(1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

(2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

(3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

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

분할정복의 응용

1. 병합 정렬 (Merge Sort)

헝가리 출신 미국인 수학자인 존 폰 노이만이 1945년에 개발한 알고리즘이다. 시간복잡도는 이고, 공간복잡도는 이다.

알고리즘

1. 정렬할 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면

2. 데이터 집합을 반으로 나눈다.

3. 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.

예를 들어 다음과 같은 데이터 집합이 있다고 해보자.

알고리즘의 1~2 과정을 반복하여 나눈다. 색칠한 부분은 나눈 기준이 되는 부분이다.

분할을 했으니 정복을 할 차례다. 3~4과정을 반복해서 수행한다.

조각난 데이터 집합을 정렬해가면서 병합하면 결국 완전히 정렬된 하나의 데이터 집합을 얻는 알고리즘이다.

그런데 병합이 어떻게 정렬하면서 합칠 수 있는 것일까.

두 데이터 집합을 정렬하면서 합치는 방법

1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.

2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제한다.

3. 원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.

예를 들어 다음과 같은 데이터 집합 A, B와 이 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합인 C가 있다고 하자.

두 데이터 집합의 첫 번째 요소를 비교한다. A의 첫 번째 요소는 2, B의 첫번째 요소는 1이므로 B의 것이 더 작다. C에 1을 추가하고 B에서 1을 삭제한다.

그 다음 A의 2와 B의 3을 비교한다. 2가 작으니 C에 2를 추가하고 A에서 2를 삭제한다.

A의 5와 B의 3을 비교한다. 3이 작으니 C에 3을 추가하고 B에서 3을 삭제한다.

이렇게 데이터 A와 B의 요소들을 비교해서 C에 넣고 A와 B의 각 요소들을 삭제해나가다보면, A에 9하나만 남게된다. B에는 비교할 요소가 남아 있지 않으므로 그냥 9를 C에 추가하고 A에서 9를 삭제한다. 이로써 A와 B의 요소들이 모두 삭제되었고 C는 정렬된 데이터 집합이 되었다.

2. 거듭 제곱 (Exponentiation)

n거듭 제곱은 자신을 n번 곱해야 함으로 의 시간이 소요된다. 이것을 개선하기 위해서 연산방법을 조금 바꾸어보자.

은 다음과 같이 정의되지만,

다음과 같이 표현할 수도 있다.

을 구할 때 C를 8번 곱하지 않고 를 구한 뒤 제곱을 두 번 더 반복하면 결국 세번의 연산만으로 같은 결과를 얻을 수 있다.

지수가 짝수일때는 지수를 반으로 나눠서 곱한다.

지수가 홀수일때는 지수에서 1을 빼고 반으로 나누어서 곱하고 밑을 한번 더 곱하면 된다.

이렇게 지수를 반으로 나눠가는 거듭 제곱 알고리즘의 수행 시간은 이다.

3. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의된다.

이 알고리즘으로는 걸리는 시간은 이다.

연산을 줄이기 위해 2차 정사각행렬을 이용한다.

 이므로 n제곱을 하게 되면

  이렇게 거듭제곱 알고리즘때와 비슷하게 나타낼 수 있다.

수행 시간 또한 거듭 제곱 알고리즘과 똑같은 이 걸리게 된다.