티스토리 뷰

알고리즘

분할정복

안드로이드용용 2016. 8. 4. 09:49

오늘 알고리즘 공부는 분할 정복 문제들에 대해서 살펴보도록 하자.


분할 정복 알고리즘이란?

 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 계산하는 방법.


재귀와의 차이점은 재귀는 한조각과 나머지 부분과 분할하지만, 분할 정복은 항상 절반씩으로 나눈다.


분할 정복 알고리즘의 구성요소

  • 문제를 더 작은 문제로 분할하는 과정 (divide)
  • 문제에 대해 구한 답을 원래 문제에 답으로 병합하는 과정 (merge)
  • 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)
분할 정복의 장점

작업을 더 빠르게 처리해 준다.


예제 : 수열의 빠른 합과 행렬의 빠른 제곱


1~n까지의 합

fastsum() = 1 + 2 + .... + n

 1~n/2 + n/2 ~ n까즤 합으로 바꿀 수 있다.


= (1 + 2 + ... + n/2) + ((n/2 +1) + ...+ n) 부분 분할


= fastsum(n/2) + ((n/2 + 1) + (n/2 +2) + ... + (n/2 + n/2 )

= fastsum(n/2) + (n/2 * n/2) + (1+2+3+... + n/2)

= fastsum(n/2) + n^2/4 + fastsum(n/2)

= 2 * fastsum(n/2) + n^2/4  가 된다.

	int fastSum(int n) {
		if(n == 1) return 1;
		if(n % 2 == 1) return fastSum(n-1) +n;
		return 2*fastSum(n/2) + (n/2)*(n/2);
	}


시간 복잡도 = O(logN)



행렬의 거듭제곱


일반적으로 행렬의 곱셈은 O(n^3)의 시간이 들기 때문에, m-1번의 곱셈을 하려면 O(n^3m)번의 연산이 필요하다. 이것은 분할 정복을 이용하면 눈 깜짝할 사이에 계산이 가능하다.


A^m을 구하는데 필요한 m개의 조각을 절반으로 나눠보자

A^m = A^m/2 * A^m/2

// 정방행렬을 표한하는 SquaueMatrix 클래스가 있다고 가정하면
class SquareMatrix;
// n*n 크기의 항등행렬을 반환하는 함수
SquareMatrix identity(int n);
// A^m을 반환한다.
SquareMatrix pow(const 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/2) * A^(m/2)
    return half * half;
}


m이 짝수일때는 반으로 나누면 되지만 홀수 일때는 비슷하게 반으로 나누는 것보다는 m-1 한 값에다가 A 를 한번 곱해주는 것이 훨씬 성능이 좋을 것이다.


병합 정렬과 퀵 정렬

해당 정렬 알고리즘은 정렬에 있어서 가장 성능이 좋고 빠른 방법으로 알려져 있다. (개념은 CS공학도라면 알고 있을 거라 생각된다.)

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


시간 복잡도는 병합정렬의 경우 병합에 필요한 시간은 O(n)이고 정렬에 필요한 복잡도는 각단계의 수가 매번 절반으로 나누어지기 때문에 O(logN)이 된다. 따라서 병합 정렬의 시간 복잡도는 n * O(logN)인 O(nlogn)이 된다.


퀵 정령의 경우는 피봇값에 따라 달라지고, 최악의 경우 O(n^2)이 되고 평균적으로 부분 문제가 절반에 가깝게 나누어 질때는 O(nlogn)이 된다.


예제 : 카라츠바의 빠른 곱셈 알고리즘

일반적으로 두개의 정수를 곱하는 알고리즘은, 일반적으로 수학에서 곱셈을 사용할때 계산하는 방법과 동일하고, 덧셈과 나머지 연산으로 이루어 져 있다.


카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠 후 계산한다.

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) * 10^128 + a0 * b0

여기서 우리는 절반 크기로 나눈 조각을 4번 곱한다.

이를 각각 재귀 호출해서 해결하면 분할 정복 알고리즘으로 풀 수 있다.


시간 복잡도는, 길이 n인 두 정수를 곱하는 데 드는 시간은 시프트 연산에 드는 시간 O(n)과 n/2 조각들의 곱셈 네번으로 나눌 수 있다. 계산해보면 수행시간은 O(n^2)이 된다. 이는 두 정수를 곱하는 시간과 같기 때문에 구현의 의미가 없어진다.


그 다음으로 카라츠바가 발견한것은 네번의 곱셈이 아니라 세번의 곱셈 만으로 계산을 할 수 있다는 것이었다.

a*b = a1*b1 *10^256 + (a1*b0 + a0*b1) *10^128 + a0*b0

= 각각 z0 + z1 + z2 라 할때, z1인 a1*b0 + a0*b1 을 한번의 곱셈으로 생각하게 되면

z2 = a0*b0

z0 = a1*b1

z1 = (a0 + a1) * (b0 + b1) -z0 -z2; 로 바꿀 수 있다.


시간 복잡도는 총 O(n^log3)이 된다. 이는 일반 곱셈이 10만이라고 하면 100배 정도의 차이를 보인다.


'알고리즘' 카테고리의 다른 글

재귀 함수  (0) 2016.07.29
최대 연속 부분 구간 합 최대가 나오는 알고리즘 풀이  (0) 2016.07.27
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
66,013
Today
0
Yesterday
10
TAG
more
«   2022/12   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함