분할 정복(Divide and Conquer)

Goal

• 분할 정복에 대해 설명할 수 있다.

---

분할 정복

한 문제를 둘 이상의 부분 문제(sub-problem)로 나누어 해결하고 이를 합쳐 원래 문제를 해결하는 기법

 

분할 정복 알고리즘은 다음과 같이 세 부분으로 나누어서 생각해볼 수 있다.

분할 정복의 단계

1. 분할(Divide) : 원래 문제를 분할하여 더 작은 하위 문제들 나눈다.
2. 정복(Conquer) : 하위 문제 각각을 재귀적으로 해결. (정복 과정에서 더이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제를 기저 사례(base case)라 한다.)
3. 병합(merge) : 하위 문제들의 답을 합쳐서 원래 문제를 해결

 

분할 정복을 적용하기 위해서는 문제에 다음과 같은 몇 가지 특성이 성립해야 한다.

• 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. (분할 정복을 사용한다고 무작정 효율이 좋아지는것이 아니다.)

 

일반적인 재귀 호출과 다른점

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 전체를 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

 

참고)

보통 재귀 함수를 사용해서 분할 정복 알고리즘을 구현하지만, 분할 정복이라고 해서 반드시 재귀 함수를 이용하는 것은 아니다. 함수 호출시 발생하는 오버헤드를 없애기 위해서 스택이나 큐 등을 이용하는 경우도 있다.

 

다음 그림은 분할 정복과 일반 재귀호출이 다른점을 나타낸다.

 

분할 정복의 장점

• 보통, 분할 정복의 경우 작은 문제로 분할함으로써 같은 작업을 더 빠르게 처리할 수 있게 해준다. (수행 시간 감소)
• 어려운 문제를 간단한 작은 문제로 나누어 풀 수 있다.

---

분할 정복 알고리즘 예시

예제1. 중복 없이 분할하기

예제 1.1 : 수열의 빠른 합

문제 : 1 ~ n 까지의 합을 구하시오.

 

이 문제의 경우 등차 수열의 합 공식을 사용해서 한줄의 코드 최적화 할 수 있지만, 수식으로 표현되지 않는 문제를 풀때 분할 정복 기법을 유용하게 사용할 수 있으므로 분할 정복 풀이법에 대해 알아보도록 하자.

 

문제 풀이

1부터 n까지의 수를 반으로 뚝 잘라 다음과 같은 형태로 만든다. (편의상 n은 짝수라고 가정)

$fastSum(n) = 1 + 2 + 3 + \dotso + n$

= $(1 + 2 + \dotso + \frac{n}{2}) + \lbrace (\frac{n}{2} + 1) +  (\frac{n}{2} + 2) + \dotso + n \rbrace$

 

이떄, 두 조각으로 나눠진 부분 문제 또한 fastSum(x) 형태로 표현할 수 있어야 한다.

 

1. 첫 번째 조각 부분 문제

$fastSum(\frac{n}{2}) = (1 + 2 + \dotso + \frac{n}{2})$

 

2. 두 번째 조각 부분 문제

$(\frac{n}{2} + 1) +  (\frac{n}{2} + 2) + \dotso + n = (\frac{n}{2} + 1) +  (\frac{n}{2} + 2) + \dotso + (\frac{n}{2} + \frac{n}{2})$

= $\frac{n}{2} \times \frac{n}{2} + fastSum(\frac{n}{2})$

 

따라서 다음과 같이 쓸 수 있다.

$fastSum(n) = 2 \times fastSum(\frac{n}{2}) + \frac{n^2}{4} $ (단, n은 짝수)

 

만약, n이 홀수라면 다음과 같이 표현할 수 있다.

$fastSum(n) = fastSum(n-1) + n$ (n은 홀수)

 

구현 코드

int fastSum(int n)
{	
    if(n == 1) return 1; // 기저 사례
    if(n % 2 == 1) return fastSum(n-1) + n; // n이 홀수인 경우
    return 2 * fastSum(n/2) + (n/2) * (n/2); // n이 짝수인 경우
}

 

시간 복잡도 분석

위 함수에는 반복 구문이 없기 때문에 순전히 함수 호출 횟수에 따라 시간 복잡도가 결정된다.

 

위 함수 호출 횟수는 다음 두가지 요소에 의해 결정 된다.

1. n의 이진수 표현의 자릿수
2. 첫 자리를 제외하고 나타나는 1의 개수

따라서, 시간 복잡도는 $O(\log_2n) + O(\log_2n) = O(\log_2n)$이 된다.

 

설명

ex) fastSum(11)을 실행할 때 재귀 호출의 입력이 어떻게 되는지 변화를 이진수로 표현하면 다음과 같다.

$fastSum(1011_{2}) = fastSum(1010_{2}) + 11$

$fastSum(1010_{2}) = fastSum(101_{2}) \times 2 + 25$

$fastSum(101_{2}) = fastSum(100_{2}) + 5$

$fastSum(100_{2}) = fastSum(10_{2}) \times 2 + 4$

$fastSum(10_{2}) = fastSum(1_{2}) \times 2 + 1$

$fastSum(1_{2}) = 1$

 

위와 같이 이진수로 표현했을 때 다음과 같은 패턴을 갖는다.

1. 홀수인 경우 : 마지막 자리가 1인 경우로, 끝 자리 1을 0으로 바꾼다.
2. 짝수인 경우 : 마지막 자리가 0인 경우로, 끝 자리가 없어진다.

위 두 값의 상한은 모두 lgn이므로 이 알고리즘의 실행 시간은 O(lgn)이 된다.

 

 

 

예제 1.2 : 행렬의 빠른 제곱

문제 : n * n 크기의 행렬 A가 주어질 때, $A^m$의 값을 구하시오.

 

행렬 곱셈에는 $O(n^3)$의 시간이 들기 때문에 곧이 곧대로 m-1번을 곱하면 $O(n^3m)$번의 연산을 필요로 한다.

이는 n과 m이 커짐에 따라 굉장히 많은 연산을 필요로 하기 때문에 다른 방법 계산하는 것이 더 효율적이다.

 

문제 풀이

예제 1.1과 마찬가지로 두 조각의 부분 문제로 나눠서 생각해보면 다음과 같이 표현할 수 있다.

(m은 짝수라고 가정)

 

$A^m = A^{\frac{m}{2}} \times A^{\frac{m}{2}}$

반으로 자르는 것만으로도 절반 크기의 부분 문제를 풀 수 있으니 문제가 더 단순해진다.

 

m이 홀수인경우 다음과 같이 표현할 수 있다.

$A^m = A \times A^{m-1}$

 

구현 코드

//정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정한다.
class SquareMatrix;
//항등행렬을 반환하는 함수
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 = (A^(n/2) * A^(n/2))
    return half * half;
}

 

앞서 본 예제 1.1에서도 그렇고 나누어 떨어지지 않을 경우, 즉 홀수인 경우 1을 뺀 짝수로 만들어서 문제를 푸는데는 이유가 있다.

 

다음 그림은 두가지 방식의 거듭제곱 분할 방식을 비교한 방법이다.

 

 

얼핏 보면 비슷해 보이지만 각 부분 문제가 계산되는 횟수가 다르다는 데 큰 차이가 있다.

화살표의 연결은 문제를 풀기 위해 호출해야 하는 각 부분 문제를 나타낸다.

 

case 1. 홀수를 반으로 나누는 경우

pow(A,8)은 pow(A,15)를 계산할 때와, pow(A,16)을 계산할 때 두 번 호출된다.

따라서, pow(A,8)과 pow(A,7)을 계산할 때 사용하는 pow(A,4)는 모두 세 번 호출된다.

이와 같이 같은 값을 중복으로 계산하는 일이 많기 때문에 m이 증가함에 따라 pow(A,m)을 계산하는 데 필요한 pow()의 호출 횟수는 m에 대해 선형적으로 증가하게 된다.

 

case 2. 짝수로 만들어서 사용하는 경우

짝수로 만들어서 계산하는 경우 O(lgm)개의 거듭제곱에 대해 한 번씩만 호출하기 때문에, 중복을 피할 수 있어 더 빨리 계산할 수 있다. => 호출 횟수 O(lgm)

 

결론

1. 같은 문제라도 어떻게 분할하냐에 따라 시간 복잡도 차이가 커진다.
2. 중복 계산되는 부분을 제거하면 성능 향상을 기대할 수 있다.

 

예제2. 같은 문제를 어느 단계에서 해결하느냐에 따른 구분 (병합 정렬, 퀵정렬)

병합 정렬(merge sor)과 퀵 정렬(quick sort)은 분할 정복 패러다임을 기반으로 해서 만들어진 대표적인 정렬 알고리즘이다. 이 두 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐, 병합 단계에서 하느냐가 다르다.

 

이렇게 같은 문제를 해결하는 알고리즘이더라도 어떤 식으로(어느 단계에서) 분할하느냐에 따라 다른 알고리즘이 될 수 있다.

 

참고) 병합 정렬, 퀵정렬

병합 정렬

• 전체 수행 시간은 병합 과정에 의해 지배된다.
• O(n) 시간이 걸리는 과정을 재귀 호출 후에 진행 (병합 과정)
• 문제의 수는 항상 절반으로 나눠지기 때문에 필요한 단계 수는 O(logn)
• 시간 복잡도 : 항상 O(nlogn) 으로 일정. 

퀵 정렬

• 전체 수행 시간은 두개 부분 문제로 나누는 파티션(partition) 과정에 의해 지배된다.
• 분할된 두 부분 문제가 비슷한 크기로 비슷한 크기로 나눠진다는 보장이 없기 때문에, 이를 비슷한 크기로 나누는 좋은 기준을 선택하는 것은 퀵정렬에서 중요한 요소이다.
• O(n) 시간이 걸리는 과정을 재귀 호출 전에 진행 (분할)
• 문제의 수가 항상 절반으로 나누어 진다는 보장이 없기 때문에 필요한 단계수를 정확히 계산하기 힘들다. 최악의 경우 n, 평균적인 경우 logn만큼의 단계가 필요하다.
• 시간 복잡도
  • 최악 : O(n^2)
  • 평균 : O(nlogn)