[분할 정복] 분할 정복에 대해서 알아보자

분할 정복은 이름 그대로 문제를 작은 부분으로 쪼개어서 해답을 찾은 뒤에 작은 조각들을 합치면서 다시 해답을 찾아내가는 방식입니다.

대표적인 분할 정복 방식으로는 병합 정렬이 있습니다.

위 그림에서 보듯이 병합 정렬은 배열을 반씩 쪼개서 가장 작은 단위로 쪼갠 다음에 정렬하고, 이 정렬된 배열을 점차적으로 정렬하는 방식입니다.

분할 정복을 할 때 가장 중요하게 고려해야 할 점이 있습니다.

바로 조그만 조각에서 나온 최적해를 이용해서 구해나간 답이 결국 최종 해답과 일치해야 한다는 것입니다.

작은 조각에서 나온 답이 결국 더 큰 조각에서는 쓸모가 없어진다면 의미없는 일을 한 것이겠죠...

또 다른 예로는 행렬의 거듭제곱을 구하는 코드가 있습니다.

보통의 방법으로 행렬의  m 제곱을 구하게 되면, n x n의 크기일 때 의 시간이 걸립니다. 

(하나의 원소를 구하는데 n번의 곱셈을 수행하고, 원소의 수가 n*n개 이기 때문이죠.)

하지만, 분할 정복 방법으로 씩 나누어서 구하면 의 시간이 걸립니다.

여기서 주의해야할 점이 있습니다!

만약 m이 홀수라면, 를 해야 훨씬 더 빠른 효과를 볼 수 있다는 것입니다.

A 행렬을 m번 제곱하는 형식을 pow(A, m)이라고 할 때, pow(A, 15)를 구해보겠습니다.

1) pow(A, 8), pow(A, 7)로 나누는 경우

2) pow(A, 14), A로 나누는 경우

왜 이런 결과가 생기는 것일까요?

m이 짝수인 경우에는 어짜피 같은 수를 2번 곱해주면 되기때문에 1번만 호출해도 됩니다.

pow(A, 8)의 경우에는 pow(A, 4)의 값을 한번 구한 다음에 pow(A, 4) * pow(A, 4)를 하면 되는 것 입니다.

하지만, pow(A, 7)의 홀수의 경우에는 중복계산이 발생합니다. 

pow(A, 3)을 위해 다시 계산을 하면서 pow(A,  4)를 할 때 똑같은 작업을 하는 부분이 생기기 때문입니다.

따라서, 이 방식을 사용할 때에는 중복이 나타나는 부분이 있는지 확인하는 것이 가장 중요합니다.

이러한 문제점때문에 나타난 또 다른 알고리즘 중 하나가 동적 프로그래밍 기법입니다. (dynamic programming)

그럼 이제 분할 정복 문제를 살펴봅시다.

 - 쿼드 트리 뒤집기 (난이도 하)

-> 풀이

 - 울타리 잘라내기 (난이도 중)

-> 풀이

 - 팬 미팅 (난이도 상)

-> 풀이