분할정복

분할정복 알고리즘

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

알고리즘을 설계하는 요령

• Dived : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다,

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

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

분할정복의 응용

1. 병합 정렬
• 시간 복잡도는 O(n logn)이고 공간 복잡도는 O(n)이다.
• 정렬할 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고 그렇지 않으면?
• 데이터 집합을 반으로 나눈다.
• 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞게 정렬한다.
• 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.

분할정복의 예시

• 예를 들어 다음과 같은 데이터 집합이 있다.

• 알고리즘의 1~2 과정을 반복하여 나누며 색칠한 부분은 나눈 기준이 되는 부분이다.
• 정렬할 데이터의 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고 그렇지 않으면?
• 데이터 집합을 반으로 나눈다.

• 분할을 마치면 정복을 할 차례로 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을 삭제한다.



이렇게 데이터를 비교해서 C에 넣고 A와 B의 요소를 삭제해 나가다 보면 A에 9하나만 남게된다 B에 비교할 요소가 남아있지 않아서 9를 그냥 추가하고 A에서 9를 삭제한다. 이로써 정렬이 끝이난다.

REF

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

정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다. 알고리즘을 설계하는 요령 (1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. (2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

https://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