7.1 도입
분할 정복(Divide & Conquer) : 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산
분할 정복이 일반적인 재귀 호출과 다른 점 : 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다.
분할 정복을 사용하는 알고리즘들이 공통적으로 가지는 세 가지의 구성 요소
- divide : 문제를 더 작은 문제로 분할하는 과정
- merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
- base case : 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
분할 정복을 적용해 문제를 해결하기 위해 요구되는 문제의 특성
- 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
- 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.
분할 정복의 장점
: 많은 경우 같은 작업을 더 빠르게 처리해 준다.
예제: 수열의 빠른 합과 행렬의 빠른 제곱
1+2+…+n의 합을 분할 정복을 이용해 계산하는 fastSum() 함수
먼저, 1부터 n까지의 합을 n개의 조각으로 나눈 뒤, 이들을 반으로 뚝 잘라 n/2개의 조각들로 만들어진 부분 문제 두 개를 만든다. (n은 편의상 짝수라 가정)
fastSum() = 1+2+…+n
= (1+2+…+n/2) + ((n/2+1)+…+n)
첫 번째 부분 문제는 fastSum(n/2)로 나타낼 수 있지만, 두 번째 부분 문제는 그렇지 않다. 문제를 재귀적으로 풀기 위해서는 각 부분 문제를 ‘1부터 n까지의 합’ 꼴로 표현할 수 있어야 하는데, 위의 분할에서 두 번재 조각은 ’a부터 b까지의 합’형태를 가지고 있기 때문이다.
따라서 다음과 같이 두 번째 부분 문제를 fastSum(x)를 포함하는 형태로 바꿔 써야 한다.
(n/2+1)+…+n
= (n/2+1)+(n/2+2)+…+(n/2+n/2)
= n/2 * n/2 + (1+2+3+...+n/2)
= n/2 * n/2 + fastSum(n/2)
공통된 항 n/2를 따로 빼내면 fastSum(n/2)이 나타난다.
따라서 다음과 같이 쓸 수 있다.
fastSum(n) = 2*fastSum(n/2) + n^2/4 (n이 짝수일 때)
// 필수 조건 : n은 자연수
// 1+2+...n을 반환한다.
public static int fastSum(int n) {
// 기저 사례
if(n==1) return 1;
// n이 홀수인 경우에는 짝수인 n-1까지의 합을 재귀 호출로 계산하고 n을 더해 답을 구한다.
if(n%2 == 1) return fastSum(n-1)+n;
return 2*fastSum(n/2) + (n/2)*(n/2);
}
def fastSum(n):
if n==1:
return 1
if n%2==1:
return fastSum(n-1)+n
return 2*fastSum(n//2) + (n//2)*(n//2)
시간 복잡도 분석
fastSum()은 호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.
O(logn)의 시간복잡도
행렬의 거듭제곱
A^m = A^(m/2) * A^(m/2)코드 7.2 행렬의 거듭제곱을 구하는 분할 정복 알고리즘
// 정방행렬 squareMatrix를 표현하는 SquareMatrix 클래스
public static class SquareMatrix;
// n*n 크기의 항등 행렬을 반환하는 함수
public static SquareMatrix identity(int n);
//A^m을 반환
public static SquareMatrix pow(SquareMatrix A, int m) {
// 기저 사례: A^0 = I
if (m==0) return identity(A.size());
if (m%2 > 0) return pow(A, m-1) * A;
SquareMatrix half = pow(A, m / 2);
// A^m = (A^(n/2)) * (A^(m/2))
return half * half;
m이 홀수일 때, 왜 절반에 가깝게 나누지 않는가? 알고리즘을 더 느리게 만들기 때문.
A^m을 찾기 위해 계산해야 할 부분 문제의 수가 늘어난다.
같은 값을 중복으로 계산하는 일이 많기 때문에 m이 증가함에 따라 pow(A, m)을 계산하는 데 필요한 pow()의 호출 횟수는 m에 대해 선형적으로 증가함.
부분 문제가 중복된다(overlapping subproblems) … 동적 계획법 고안의 계기
예제: 병합 정렬과 퀵 정렬
merge sort, quick sort
분할 정복 패러다임을 기반함
merge sort : 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다. 병합 과정에서 O(n)의 시간복잡도
quick sort : 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할. partition이라고 부르는 단계 도입(배열에 있는 수 중 임의의 pivot(기준 수)를 지정하고 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보냄) partition(분할) 과정에서 O(n)의 시간복잡도
두 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐, 병합 단계에서 하느냐가 다르다.
merge sort : 정렬된 두 부분 수열을 합치는 데는 두 수열의 길이 합만큼 반복문 수행. 병합이 진행될수록 부분 문제의 수는 반으로 줄고 각 부분 문제의 크기는 두 배로 늘어남 한 단계 내에서 모든 병합에 필요한 총 시간은 O(n)으로 항상 일정. 문제의 크기는 항상 거의 절반으로 나누어지기 때문에 필요한 단계의 수는 O(logn) O(nlogn)의 시간복잡도
quick sort : 최악의 경우 O(n^2) 분할된 두 부분 문제가 비슷한 크기로 나눠진다는 보장 x
평균적으로 부분 문제가 절반에 가깝게 나눠질 때 퀵 정렬의 시간 복잡도는 O(nlogn) 대부분의 퀵 소트는 가능한 한 절반에 가까운 분할을 얻기 위해 좋은 기준을 뽑는 다양한 방법 사용
예제 : 카리츠바의 빠른 곱셈 알고리즘
두 개의 정수를 곱하는 알고리즘.
수백, 수만 자리는 되는 큰 숫자들을 다룰 때 주로 사용함.
이렇게 큰 숫자들은 배열을 이용해 저장해야 한다.
두 정수의 곱셈을 하는 가장 기본적인 방법부터 시작.
아래 코드에서 배열드은
곱할 수의 각 자릿수를 맨 아래 자리부터 저장—> 입출력할 때는 불편하지만, A[i]에 주어진 자릿수의 크기를 10^i로 쉽게 구할 수 있다. —> A[i]와 B[j]를 곱한 결과를 C[i+j]에 저장하는 등, 훨씬 직관적인 코드를 작성 가능.
자릿수 올림을 처리하는 normalize()에서 자릿수가 음수인 경우도 처리.
multiply()에서는 덧셈밖에 하지 않기 때문에, 자릿수가 음수가 될 일이 없다.
// 코드 7.3 두 큰 수를 구하는 O(n^2) 시간 알고리즘
// num[]의 자릿수 올림을 처리
public 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의 자리에서부터 시작해 저장되어 있다.
// 예: multiply([3, 2, 1], [6, 5, 4]) = 123*456 = 56088 = [8, 8, 0, 6, 5]
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;
}
def normalize(num):
num.append(0)
for i in range(len(num)):
if num[i] < 0:
borrow = abs(num[i] + 9) // 10;
num[i+1] -= borrow
num[i] += borrow * 10
else:
num[i+1] += num[i]//10
num[i] %= 10
while len(num) > 1 and num[-1] == 0:
del num[-1]
def multiply(a, b):
c = [0 for i in range(len(a) + len(b))]
for i in range(len(a)):
for j in range(len(b)):
c[i+j] += a[i]*b[j]
normalize(c)
—> 시간 복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2)
n번 실행되는 for문이 두 번 겹쳐 있기 때문.
이보다 빠른 첫 번째 알고리즘은 카라츠바 알고리즘 (1960년 등장)
- 두 수를 각각 절반으로 쪼갠다.
a와 b가 각각 256자리 수라면 a1과 b1은 첫 128자리, a0과 b0은 그 다음 128자리를 저장.
a = a1*10^128 + a0
b = b1*10^128 + b0
이렇게 쓸 수 있다.
카라츠바는 이때 a*b를 네 개의 조각을 이용해 표현하는 방법을 고안.
예를 들면 다음과 같다.
a*b
= (a1*10^128 + a0)*(b1*10^128 + b0)
= a1*b1*10*256 + (a1*b0+a0*b1) + a0*b0
큰 정수 두 개를 한 번 곱하는 대신, 절반 크기로 나눈 작은 조각을 네 번 곱한다. (10의 거듭제곱과 곱하는 것은 시프트 연산으로 간단하게 구현되기 때문에 곱셈으로 치지 않는다.)
—> 재귀 호출해서 해결하면 분할 정복 알고리즘이라고 할 수 있다.
시간 복잡도는 덧셈과 시프트 연산에 걸리는 시간 O(n)과, n/2 길이 조각들의 곱셈 내 번.
그런데 사실 이 방법의 전체 수행 시간은 O(n^2)이 된다. (T(n) = O(n) + 4*T(n/2)라고 했을 때 마스터 정리로 증명 가능)
카라츠바가 발견한 것은 다음과 같이 가정했을 때 네 번 대신 세 번의 곱셈으로만 이 값을 계산할 수 있다는 것
z2 = a1 * b1;
z0 = a0 * a0;
// z1 = a1*b0+a0*b1
z1 = (a0 + a1) * (b0+b1) - z0 - z2;
그러면 이 세 결과를 다시 적절히 조합해 원래 두 수의 답을 수할 수 있다.
아래 코드는 이렇게 구현한 카라츠바 알고리즘
public 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의 자리에서부터 시작해 저장되어 있다.
// 예: multiply([3, 2, 1], [6, 5, 4]) = 123*456 = 56088 = [8, 8, 0, 6, 5]
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;
}
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;
}
—> 분할한 부분 문제의 답에서 원래 문제의 답을 병합해 내는 부분을 개선함으로써 알고리즘의 성능을 향상시킴. 스트라센(Strassen)의 행렬 곱셈 알고리즘 역시 이와 비슷한 기법 사용.
카라츠바 알고리즘은 두 개의 입력을 절반씩으로 쪼개고 세 번 재귀 호출 수행
우선 병합 단계와 기저 사례의 두 부분으로 알고리즘을 나눈다.
병합 단계의 수행 시간 —> addTo()와 subFrom()
기저 사례의 처리 시간 —> multiply()
- 기저 단계의 수행 시간 계산
(편의를 위해 한 자리 숫자에 도달해야만 multiply()를 사용한다고 가정)
기저 사례를 처리하는 데 드는 총 시간 : 자릿수 n이 2의 거듭제곱 2^k라고 했을 때 재귀 호출의 깊이는 k. 한 번 쪼갤 때마다 해야 할 곱셈의 수가 세 배씩 늘어나기 때문에 마지막 단계에는 3^k개의 부분 문제가 있지만, 마지막 단계에서는 두 수 모두 한 자리이기 때문에 곱셈 한 번이면 충분.
—> 곱셈의 수는 O(3^k)
n = 2^k라고 가정했으니 k = logn
이때 곱셈의 수를 n에 대해 표현하면 다음과 같은 식이 도출됨.
O(3^k) = 3^logn = O(n^log3)log3의 근사치는 1.585이기 때문에 카라츠바 알고리즘이 O(n^2)보다 훨씬 적은 곱셈을 필요로 한다.
- 병합 단계의 수행 시간 계산
addTo()와 subFrom()는 숫자의 길이에 비례하는 시간만이 걸리도록 구현 가능
—> 각 단계에 해당하는 숫자의 길이를 모두 더하면 병합 단계에 드는 시간을 계산 가능
단계에가 내려갈 때마다 숫자의 길이는 절반으로 줄고 부분 문제의 개수는 세 배 늘어남
—> i번째 단계에서 필요한 연산 수는 (3/2)^i * n
이는 n^log3과 같은 속도로 증가한다.
카라츠바 알고리즘의 시간 복잡도는 곱셈이 지배하며, 최종 시간 복잡도는
O(n^log3)단, 카라츠바 알고리즘의 구현은 단순한 O(n^2) 알고리즘보다 훨씬 복잡하기 때문에 입력의 크기가 작을 경우 O(n^2) 알고리즘보다 느린 경우가 많다. <— 코드에서 입력된 숫자가 짧을 경우 O(n^2) 알고리즘을 사용하는 이유
#책/종만북
'알고리즘' 카테고리의 다른 글
| 7.4 울타리 잘라내기 (0) | 2019.12.03 |
|---|---|
| 7.2 쿼드 트리 뒤집기 (0) | 2019.12.03 |
| programmars 가장 큰 수 (0) | 2019.09.21 |
| programmars 여행경로 (0) | 2019.09.21 |
| programmars 단어 변환 (0) | 2019.09.21 |
