07. Divide and Conquer(1)

안녕하세요. 오늘은 Divide and Conquer. 한국어로는 분할정복이라고 불리는 알고리즘을 소개할까 합니다. 정말 유명한 알고리즘입니다. 다만, Search, DP, Greedy에 비해는 등장빈도가 조금 낮다고 할 수 있습니다.

 

분할하고 정복하기

 

분할 : 주어진 문제를 여러개의 부분 문제로 나눈다

정복 : 분할된 문제를 푼다. 이때 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다.

 

분할정복 문제 자체는 등장빈도가 조금 낮을 수 있다고 말씀드렸지만, 분할이라는 접근은 매우 유용하기 때문에 다른 자료구조나 알고리즘의 basic이 되는 경우가 많습니다. 정복을 설명하면서 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다고 말씀드렸는데요. Resursive function의 base case처럼 바로 답을 구할 수 있는 수준까지도 분할할 수 있는 문제가 존재하기 때문입니다. 여기서 분할정복 알고리즘 문제는 재귀함수와 잘 들어맞는다는 것을 짚고 넘어가면 좋겠습니다.

 

다만 여러개의 문제로 조갠다는 점에서 오히려 복잡해질 수 있습니다. 마치 하나로 포장된 물건을 낱개의 물건으로 포장하려면 귀찮은 것 처럼요. 따라서 문제 전체를 통으로 풀 때보다 이미 풀린 문제를 간단한 연산처리 등으로 합치는 것이 바를 때 분할정복 알고리즘은 유효하게 사용될 수 있다고 말씀드릴 수 있습니다.

 

Merge sort, Binsary Search, Power Operation(n^m)

 

여기서 Binary Search같은 경우는 문제의 크기를 절반으로 분할하는 경우입니다. M번 단계를 거쳐 문제 전체의 크기인

N을 만들어볼까요?

M이 N에 비해 합리적인 수준으로 작다는 것을 알 수 있습니다. 이런 계산을 해본 이유는 무엇일까요?

분할정복 알고리즘은 수행시간을 조심스레 추측해야하는 알고리즘 중 하나입니다. 분할할 때 나누어지는 문제의 개수, 분할 후 문제의 크기, 정복 단계에서 소요되는 시간을 모두 고려해야 하기 때문입니다. Merge sort와 같은 경우 2(분할할 때 나누어지는 문제의 개수), N/2(분할 후 문제의 크기), O(N)(정복 단계에서 소요되는 시간)이 되겠군요. 병합정렬의 시간복잡도는 

인데요. 

 

T(N)을 N개의 원소를 가지고 있는 배열을 Merge sort로 정렬할 때 시간 복잡도, T(1)을 1개의 원소를 정렬하는 시간이라고 생각한다면

가 됩니다. 이를 재귀적으로 대입하다 보면

k는 앞서 살펴본 것처럼 

이죠. 따라서 

입니다. 참고로 Merge sort는 데이터 분포의 영향을 적게 받아 안정적이고 빠른 정렬방법 중 하나이기 때문에 킵해두시는 것을 추천드립니다. k-way Merge Sort에 대해서도 동일하게 시도한다면 비슷한 결과가 나올텐데요. 단 log의 밑이 k가 나올 겁니다. 로그의 밑은 시간복잡도에 영향을 미치지 않죠.(실제 소요시간은 k가 커질수록 오히려 길 수도 있습니다. 그 이유는 위의 식에서 잘 생각해보시면 됩니다. Hint는 무시된 항입니다.)

 처음 식의 N항은 병합을 의미합니다. 부분 수열의 수가 많을수록 kN은 무시할 수 없게되고 비록 재귀 호출의 깊이가 감소하더라도 merge하는 과정에서 비교연산이 더 많이 필요할 수 있기 때문입니다.

 

생각해보면 위와 같이 계산할 수도 있지만 복잡한 문제의 경우에 식이 잘 떠오르지 않을수도 있습니다. 그럴땐 각 단계별로 드는 연산 횟수를 생각하면 쉽게 접근할 수 있습니다. k번 분할했을 단계에서 필요한 연산 횟수는 (1번 분할했을 단계에서 필요한 연산 횟수는 2 * O(N/2)죠.)

 

이 됩니다. 단계는 logN이므로 시간복잡도를 Nlog(N)으로 간단하게 구할 수 있습니다. Bubble sort, Selection sort가 O(N^2)인데요. 그이 비해 상당히 빠른 알고리즘이라고 할 수 있습니다. C++ STL에 속한 sort와 C의 qsort도 분할정복을 base로 한 sort function을 지원하는 것입니다.

void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

/*template <class RandomAccessIterator>*/
void sort (RandomAccessIterator first, RandomAccessIterator last);
  
/*template <class RandomAccessIterator, class Compare>*/
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

 

알고리즘 과목을 수강하신 분들이라면 Master Theorem에 대해 들어보셨을텐데요. 점화식을 푸는 접근법을 제공한다고 생각하시면 됩니다. 앞서 설명드린 각각의 값이 어디에 대응되는지 찾아보시는 것이 좋을 듯 합니다. 

a, b, f(n) = n^d라고 할 때 d가 되겠군요.

 

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If T(n) denotes the total time for the algorithm on an input of size n, and f(n) denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form:

 

 

 

다시 돌아와 Binary Search의 시간복잡도는 O(logN)입니다. 찾아보시면 아시겠지만 분할을 하더라도 별도의 merge과정이 필요없기 때문이죠. Mater Therom을 정리하여 

라고 한다면 a = 1, b = 2, d = 0을 대입하여 O(log n)이 되겠군요. C++의 경우에는 값이 존재하는지 test해주는 함수가 있습니다.

/*template <class ForwardIterator, class T>*/
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);

/*template <class ForwardIterator, class T, class Compare>*/
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

참고로 위의 code에서 lower_bound() function은 찾을 값 이상의 값이 처음 등장하는 곳을 찾아줍니다.

/*template <class ForwardIterator, class T>*/
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
                               
/*template <class ForwardIterator, class T, class Compare>*/
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
                               
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = distance(first,last);
    while (count>0)
    {
        it = first; step=count/2; advance (it,step);
        if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    return first;
}

 

 

분할정복 알고리즘에 대해 간단하게 알아보는 시간을 가졌습니다. 요즘 이렇게 조금씩 간단하게 정리하는 방법이 맞는걸까 고민이 듭니다. 제가 목표로 하는 분량이 많고 백준 online judge에서 문제를 푼다고 시간이 든다는 핑계로 정작 중요한 기초정리를 대충한다는 걱정이 들었습니다. 이 고민에 대해 백준 online judge 문제 풀이 카테고리와 알고리즘 기초 정리 카테고리로 분할하는 방안에 대해서도 생각해보았습니다. 어떤 방향이 더 좋을지 조금 더 고민해보도록 하겠습니다.

 

 

추가로 검색을 용이하게 해드리기 위해 Divide and Conquer Algorithm과 관련된 모든 글은 Divide and Conquer tag를 사용하였습니다. 도움되시길 바라겠습니다.

https://ku320121.tistory.com/tag/divide%20and%20conquer

SONGANG