분할정복?
분할정복이란 주어진 문제를 둘 이상의 부분문제로 나누어 각 문제에 대한 해답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산해 내는 알고리즘이다.
분할정복은 재귀 호출과 다르게 문제를 한 조각과 나머지 전체로 나누는 대신 한 문제를 거의 같은 크기의 부분 문제로 나누는 것 이다.
- 분할 정복의 알고리즘은 세 간계의 구성 요소를 갖는다.
-
문제를 더 작은 문제로 분할하는 과정 - Divide
-
각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결 - Conquer
- 더이상 분해되지 않고 곧장 풀 수 있는 매우 작은 문제 - Base case
-
각 문제에 대해 구한 답으로 부터 전체 문제에 대한 답으로 합치는 과정 - Merge
- 분할 정복을 적용해 문제를 해결하기 위해 요구되는 특성
-
문제를 둘 이상의 부분문제로 나누는 자연스러운 방법이 있어야 한다.
-
부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.
- 분할 정복의 장점?
-
같은 작업을 더 빠르게 처리해준다.
-
중복 호출 문제가 상대적으로 적다.
카라츠바의 빠른 곱셈 알고리즘
- 카라츠바의 빠른 곱셈 알고리즘은 두개의 정수를 곱하는 알고리즘이다. 일반적인 정수의 곱은 아니고 수백자리 혹은 수만자리의 큰 숫자들의 곱을 다룰 때 사용된다.
- 수백 수만 자리가 넘는 큰 숫자들은 long같은 자료형에도 담기지 않기 때문에 저장할 때는 배열을 이용해 저장을 해야한다.
- 두 정수의 곱셈을 하는 가장 기본적인 방법은 곱할 수의 각 자릿수를 맨 아래 자리부터 저장
- 입출력할 때는 불편하지만, A[i]에 주어진 자릿수의 크기를 10^i로 쉽게 구할 수 있다. A[i]와 B[j]를 곱한 결과를 C[i+j]에 저장하는 등, 훨씬 직관적인 코드를 작성 가능.
- 자릿수 올림을 처리하는 normalize()에서 자릿수가 음수인 경우도 처리하고 있지만 multiply()에서는 덧셈밖에 하지 않기 때문에 자릿수가 음수가 될 일이 없다.
static ArrayList<Integer> normalize(ArrayList<Integer> num) {
num.add(0);
// 자릿수 올림 처리
for (int i = 0 ; i+1 < num.size(); ++i) {
if(num.get(i) < 0) {
int borrow = (Math.abs(num.get(i)) + 9) / 10;
num.set(i+1, num.get(i+1) - borrow);
num.set(i, num.get(i) + borrow*10);
}
else {
num.set(i+1, num.get(i+1) + (num.get(i) / 10));
num.set(i, num.get(i) % 10);
}
}
while(num.size() > 1 && num.get(num.size()-1) == 0) num.remove(num.size()-1);
return num;
}
// 두 자연수의 곱을 배열로 반환한다.
//(1,2,3,4),(4,3,2,1) 을 파라미터로 입력하면 (5,3,3,2,1,1,4) 형태로 출력
public static ArrayList<Integer> multiply(ArrayList<Integer> a, ArrayList<Integer> b) {
ArrayList<Integer> c = new ArrayList<Integer>();
for (int i = 0; i < a.size() + b.size(); i++) {
c.add(0);
}
for (int i = 0; i < a.size(); ++i) {
for (int j = 0; j < b.size(); ++j) {
c.set(i+j, c.get(i+j) + a.get(i)*b.get(j));
}
}
c = normalize(c);
return c;
}- 위의 경우 시간복잡도는 두 정수의 길이가 모두 n이라고 할 때 o(n^2) n번 실행되는 for문이 존재하기 때문
이보다 빠른 알고리즘이 카라츠바 알고리즘
- 카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다
a 와 b가 각각246wkfl tnfkaus a1과 b1은 첫 128자리 a0와 b0는 그 다음 128자리를 저장하도록 하는것
a = a110^128 + a0
b = b110^128 + b0
이렇게 쓸 수 있다. 카라츠바는 이때 a*b를 네 개의 조각을 이용해 표현하는 방법을 고안.
예를 들면 다음과 같다.
ab = (a110^128 + a0)(b110^128 + b0)
= a1b110256 + (a1b0+a0b1) + a0b0
이 방법에서 큰 정수 두개를 한번 곱하는 대신, 절반 크기로 나눈 작은 조각을 네번 곱한다.
이것을 각각을 재귀 호출해서 해결하면 분할 정복 알고리즘이라고 할 수 있다.
시간 복잡도는 덧셈과 시프트 연산에 걸리는 시간 O(n)과, n/2 길이 조각들의 곱셈 네 번.
그런데 사실 이 방법의 전체 수행 시간은 O(n^2)이 된다. (T(n) = O(n) + 4*T(n/2)라고 했을 때 마스터 정리로 증명 가능)
이래서는 분할 정복을 애써 구현한 의미가 없다
카라츠바가 발견한 것은 다음과 같이 가정했을 때 네 번 대신 세 번의 곱셈으로만 이 값을 계산할 수 있다는 것
z2 = a1 b1;
z0 = a0 a0;
z1 = (a0 + a1) * (b0+b1) - z0 - z2;
이 세 결과를 다시 적절히 조합해 원래 두 수의 답을 수할 수 있다.
public static ArrayList<Integer> addTo(ArrayList<Integer> a, ArrayList<Integer> b, int k) {
// a+= b*(10^k);를 구현
return a;
}
public static ArrayList<Integer> subFrom(ArrayList<Integer> a, ArrayList<Integer> b) {
// a-= b;를 구현. a>=b를 가정
return a;
}
// 두 긴 정수의 곱을 반환.
public static ArrayList<Integer> karatsuba(ArrayList<Integer> a, ArrayList<Integer> b) {
int an = a.size();
int bn = b.size();
// a가 b보다 짧을 경우 둘을 바꾼다.
if(an < bn) return karatsuba(b, a);
// 기저 사례 : a나 b가 비어 있는 경우
if(an == 0 || bn == 0) return new ArrayList<Integer>();
// 기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경.
if (an <= 50) return multiply(a, b);
int half = an / 2;
// a와 b를 밑에서 half 자리와 나머지로 분리한다.
ArrayList<Integer> a0 = new ArrayList(a.subList(0, half));
ArrayList<Integer> a1 = new ArrayList(a.subList(half, a.size()));
ArrayList<Integer> b0 = new ArrayList(b.subList(0, Math.min(b.size(), half)));
ArrayList<Integer> b1 = new ArrayList(b.subList(Math.min(b.size(), half), b.size()));
// z2 = a1*b1
ArrayList<Integer> z2 = karatsuba(a1, b1);
// z0 = a0*b0
ArrayList<Integer> z0 = karatsuba(a0, b0);
// a0 = a0+a1, b0 = b0+b1
a0 = addTo(a0, a1, 0);
b0 = addTo(b0, b1, 0);
// z1 = (z0*b0) - z0 - z2;
ArrayList<Integer> z1 = karatsuba(a0, b0);
z1 = subFrom(z1, z0);
z1 = subFrom(z1, z2);
// ret = z0 + z1 * 10^half + z2 * 10^(half*2)
ArrayList<Integer> ret = new ArrayList<Integer>();
ret = addTo(ret, z0, 0);
ret = addTo(ret, z1, half);
ret = addTo(ret, z2, half + half);
return ret;
}