7장 분할 정복

분할 정복 알고리즘이란 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 재귀 호출과 차이점은 이 부분 문제를 나누는 방법에 있어 재귀 호출은 작은 부분하나씩 분리해서 해결하지만, 분할 정복은 항상 비슷한 크기의 부분으로 나눈다는 것

분할 정복을 사용하는 알고리즘들의 세 가지 구성 요소

• 문제를 더 작은 문제로 분할하는 과정
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

분할 정복을 이용한 문제

---

1) 1~n까지의 합을 구하여라

재귀 함수를 이용하여 1~n 까지의 합을 구했을 때는 O(n) 시간 복잡도였지만

분할 정복을 이용한다면 O(log n) 까지 줄일 수 있다.

2)행렬의 거듭제곱

n*n 행렬을 m번 곱하게 된다면 일반적인 방법은 O(n^3)시간 복잡도가 걸린다면 분할 정복을 이용했을 때는 O(log m)이 걸린다.

절반은 어떠한 형태로 나누어야 할까?

A^m을 나눌 때는 어떤 형식으로 나누어야 할까

1) A*A^(m-1)

2) A^(m/2) * A^(m/2)

이것은 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예이다.

절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문이다. 예로 A(11)→A(5)*A(6)→(A2)(A3) * (A3)(A3)→... 이와 같이 반복되는 부분문제들이 많아지게 때문이다. 

3) 병합 정렬과 퀵 정렬

병합 정렬 = 병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬하는 알고리즘으로, 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

분할 단계의 시간 복잡도 : O(1)

병합 단계의 시간 복잡도 : O(n)

퀵 정렬 = 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 분할.

이 두 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐, 병합 단계에서 하느냐가 다르다.

4) 카라츠바의 빠른 곱셉 알고리즘

카라츠바의 빠른 곱셉 알고리즘은 두 개의 정수를 곱하는 알고리즘이다. 기존의 두 개의 정수의 곱셈으로 사용했던 아이디어는 O(n^2)의 시간 복잡도를 요구하였지만 카라츠바의 바른 곱셉 알고리즘의 시간 복잡도는 O(n^log 3)이다. 단 카라츠바의 알고리즘 구현은 매우 복잡하기 때문에 입력의 크기가 작은 경우에는 O(n^2)의 알고리즘을 사용한다. 

5) 쿼드 트리 뒤집기 문제