분할정복법
분할 정복법(Divide-and-Conquer)을 알아보기 위해서 가장 먼저 어떠한 알고리즘을 수행하여 문제를 해결하지는 살펴볼 것이다.
- 주어진 문제를 같은 유형의 더 작은 인스턴스(instance)들인 부분 문제(subproblem)들로 분할한다.
- 이 부분 문제들을 재귀적으로 풀어간다.
- 이들의 해답을 적절히 결합해간다.
위와 같은 구조는 분할정복법을 그림으로 잘 표현한 것이다. 입력 크기가 n인 문제를 계속해서 a의 지수개 만큼의 문제들로 분할하는 구조이다. 이때 n의 크기는 b의 크기로 나눠감게 되어 각 부분 문제들은 이전 문제의 n / b 사이즈가 되는 것이다.
곱셈(Multiplication)
우리는 어린 시절 가장 먼저 수학에 입문하여 배우는 것이 무엇인가? 바로 덧셈과 뺄셈이다. 이 단계를 넘어가면 조금 더 복잡한 곱셈과 나눗셈을 배우게 된다. 구구단을 배우는 이유도 곱셈을 잘 하기 위한 시작 단계인 셈이다.
조금 난이도를 높여 복소수를 배운 상태라면, 두 복소수의 곱셈은 어떠한 단계로 이루어지는가? 수학자 가우스는 두 복소수의 곱이 총 4번의 실수 곱셈을 연관시키는 것처럼 보이지만, 실제로는 단지 3번으로 이루어질 수 있다는 것을 알아차렸다.
위의 식에서 우리는 a와 c의 곱셈, b와 d의 곱셈, b와 c의 곱셈, a와 d의 곱셈까지 총 4번의 곱셈과 이후의 추가 덧셈을 통해서 계산할 수 있다. 하지만 사실, 조금만 식을 변형해 보면 4번의 곱셈이 3번의 곱셈으로 바뀌는 것을 볼 수 있다.
변형한 식을 살펴보면 덧셈과 뺄셈의 단계는 이후 부수적인 단계이므로 잠시 무시하고, 곱셈만 본다면 a와 c, b와 d, a + b와 c + d의 곱셈까지 총 3번의 곱셈만 이루어지는 것을 볼 수 있다. 이러한 적절한 개선은 재귀적으로 적용될 때 매우 중요한 부분이 된다. 이제 복소수를 벗어나, 이러한 방법이 보통의 곱셈을 어떻게 도와줄 수 있는지 볼 것이다.
컴퓨터의 관점에서 숫자는 bit로 표현이 가능하다. x와 y가 두 개의 n bit 정수라고 가정했을 때, x와 y를 곱하는데 있어 각각을 좌측과 우측 부분으로 나누는 것이다. 그러면 다음과 같이 x와 y는 n / 2 bit의 길이를 가지게 된다.
가령 예를 들어 X = 10110110이라고 하면 XL = 1001이고, XR = 0110이 되는 것이다. 그리고 bit 연산에서 자릿수는 2의 지수만큼 이동하기 때문에 8자리라면 왼쪽 부분에 2의 4제곱을 곱해서 자릿수가 앞인 것을 생각해줘야 한다. 그러면 x와 y의 곱셈은 다음과 같이 표현이 된다.
이 수식에서 중요한 연산은 4개의 n / 2 bit 곱셈이다. 이들은 4번의 재귀적인 호출에 의해서 다룰 수 있기에 n bit 수를 곱하기 위한 방법은 이들을 n / 2 bit 수의 네 쌍들을 곱하기 위하여 재귀적인 호출을 하는 것으로 시작하고, 추가적으로 n번의 덧셈 단계가 필요하다. 그래서 이 곱셈의 수행 시간은 다음과 같이 O(n2)이 된다.
개선된 곱셈
우리는 이 4번의 곱셈을 3번의 곱셈으로 바꿔 수행 시간에서 더욱 효율적으로 해결할 것이다. 중간에 있는 과정을 조금만 식을 변형하면 기존의 곱셈들과 더불어 최종적으로 3번의 곱셈만 하면 되는 식으로 바꿀 수 있다.
그리고 이는 다음과 같이 함수로 표현이 가능하다. 함수로 표현했을 때, 더욱 세부적으로 어떻게 진행이 되는지 한번에 알 수 있다.
2의 거듭제곱은 비트 연산자에서 shift연산자로 자릿수를 나타내고, P가 총 3개를 만들어져 재귀적으로 곱셈 연산을 수행하게 된다.
이렇게 개선이 된 곱셈에서 수행 시간은 상수 인자가 4에서 3으로 개선이 순환하는 모든 단계에서 발생하게 되었고, 이러한 복합적인 효과가 수행 시간을 더 효과적으로 개선하게 되는 것이다.
위 그림과 같이 트리 구조를 형성하는 알고리즘을 통해서 새로운 수행 시간이 유도될 수 있다. 이 트리는 총 logn 레벨로 깊이가 형성이 되는데, 각 연속적인 레벨에서 부분 문제들의 크기가 딱 절반이 되는 것을 알 수 있다. 마지막 단계로 가면 부분 문제의 크기가 딱 1이 될 것이고 순환은 종료하게 될 것이다. 레벨이 하나씩 내려갈 때 3개의 branch가 형성이 되어 기존 곱셈의 4에서 1개가 줄어든 것을 볼 수 있다.
이를 일반화 하면 k번째 레벨에서 개선된 곱셈 문제의 경우 3의 k제곱개의 부분 문제들이 형성이 되고, 각각의 크기는 초기 크기인 n을 2의 k제곱으로 나눈 크기가 될 것이다. 일반화 한 이 단계를 처음부터 총 레벨만큼 수행 시간을 더해주면 최종적으로 위와 같은 결과가 나오게 된다. 기존의 곱셈에서 분할정복법으로 개선된 곱셈을 통해서 수행시간이 발전된 것을 볼 수 있다. 분할정복법은 이렇게 같은 유형의 재귀적으로 분할이 가능하면 불필요한 계산을 줄일 수 있게 된다.
