'Algorithm'에 해당되는 글 1건

  1. 2013.08.11 분할정복법 (Divide and Conquer)



알고리즘 영역에서 분할정복법(Divide-and-Conquer)은 말 그대로 주어진 문제를 분할하여 해결하는 방법을 말한다. 즉, 한 번에 해결하기 어려운 문제를 작은 단위의 부문제들(subproblems)로 쪼개어 해결하는 방법이다. 이름에 하필 '정복(Conquer)'이라는 단어가 들어가는 이유는 문제 해결 방식이 바로 그 유명한 '나폴레옹 황제'가 활용했던 분할정복(Divide and Conquer, 또는 Divide and Rule) 전략과 흡사했기 때문이다. 직접 상대하기 버거운 많은 수의 적군을 조금씩 쪼개어 각개격파한다는 이해하기 매우 쉬운 전술이다.

 

분할정복법은 대개 재귀적으로 구현되기 때문에 마찬가지로 문제를 최소단위까지 쪼개어 해결하는 일반적인 재귀적 풀이법과 어떻게 다른지 감이 안올 수도 있다. 그런 경우를 위해서 일반적인 재귀적 해법과 다른 분할정복법의 한 가지 특징을 꼽자면 다음 그림에서처럼 분할정복법에서는 문제를 한 조각과 나머지부분으로 나누는 것이 아니라, 거의 균등한 크기의 부분 문제로 나눈다는 점이다.

 

 

분할정복 알고리즘에는 보통 다음과 같은 세 가지 과정이 있다.

 

1. 문제를 더 작은 문제(부문제)로 분할 (Divide)

 

2. 각 부문제에서 구한 답을 분할하기 전의 원래 문제에 대한 답이 되도록 합병하는 과정 (Merge)

 

3. 더 이상 쪼갤 필요가 없거나 쪼갤 수 없는 문제에 대해 답을 구하는 과정 (Base case)

 

 

어떤 문제에 분할정복법을 적용할 필요성이 있는지 알아보려면 다음의 두 가지 조건을 검사해보면 된다.

 

1. 문제를 여러 부문제들로 쪼개는 것이 가능한가? (Divide)

 

2. 부문제들의 답을 조합하여 본래 문제의 답을 효율적으로 구할 수 있는가? (Merge & Conquer)

 

 

위 조건 중 2번에서 '효율적'이라는 말을 강조한 이유는 분할정복법을 적용시킬 수 있다고 한들 무식하게 푸는 방법보다 비효율적이면 이 방법을 사용하는 의미가 없기 때문이다. 그 말은 즉, 분할정복법의 장점은 처리 속도라는 것이다. 간단한 예제를 통해서 정말로 처리 속도에 이득이 있는지를 확인해보자. 분할정복법은 퀵 정렬(Quick Sorting), 합병정렬(Merge Sorting), 이진검색(Binary Search), 고속퓨리에변환(FFT), 유클리드 호제법(Euclidean algorithm) 등이 있으나 여기서는 쉽게 이해할 수 있도록 이진검색(Binary Search) 알고리즘을 예로 들겠다. 이진검색(또는 이분검색)이 뭔지 모르는 사람은 우리가 사전에서 단어를 찾을 때 어떤 순서로 페이지를 넘기는지를 떠올려보면 이해하기 쉬울 것이다.

 

아무튼, 본론으로 넘어가서

우리가 알파벳 'A'로 시작하는 단어가 적힌 n장의 카드 중에서 'Apple'이라는 단어가 몇 번째 카드에 적혀있는지를 찾는다고 하자.

 

각각의 카드에는 중복된 단어가 존재하지 않으며 카드의 순서는 알파벳 사전순서로 되어 있다. 작업의 단위는 '카드를 한 장 확인하는 행위'이다.

 

 

이 경우 카드의 첫 장부터 끝 장까지를 모두 확인한다면 운이 좋을 때는 한 번만에 찾겠지만 운이 나쁘면 n번의 확인 작업을 필요로 한다. 'Apple'을 제외한 나머지 영단어들이 카드에 써 있을 확률이 모두 동등하다면 결국 이 방법을 썼을 때 평균적으로 번의 확인 작업을 해야만 한다. 그렇다면 분할정복법인 이진검색을 사용하면 어떨까? 카드에 써진 알파벳은 사전 순서로 나열되어있기 때문에 전체 카드 중에서 중간에 있는 번째 카드를 확인하고, 그 카드가 찾는 단어인 'Apple'보다 더 빠른 단어이면 번째 카드 다음으로 나열된 카드들만을 확인하면 되고 반대로 'Apple'보다 더 나중에 나와야 할 단어였다면 번째 카드 앞에 나열된 카드들만을 확인하면 될 것이다. 따라서 확인해야 할 카드의 수는 절반 이하로 줄었고, 다시 이 카드들에 대해서 방금 적용한 것처럼 중간에 있는 카드를 확인하는 절차를 반복하면 된다. 한 번 확인할 때마다 남은 카드의 수가 최대 절반 이하로 줄기 때문에 이 방법을 적용하여 문제를 해결하는 경우 우리가 해야만 하는 작업의 수는 아무리 많아봤자 번에 불과하다. 카드의 수가 64장만 되어도 위 두 방법에서 수행되는 작업은 각각 최대 64회, 6회로 큰 차이를 보인다. 따라서 분할정복법을 적용할만한 문제라면 그냥 해결하는 것보다 분할정복법을 적용하는 편이 훨씬 이득이라는 것을 알 수 있다.

 

 

이진검색에서는 분할하는 것만으로 문제가 해결된 것 처럼 보인다. 그러나 병합과정은 나눠진 카드에 각각 순서번호가 부여되어있고 이것을 몇번인지 바로 알아낼 수 있는 시점에서 이미 완료된 것이다. 좀 더 복잡한 알고리즘에서는 답을 구하기 위한 합병 과정을 쉽게 눈치챌 수 있을 것이다. 합병정렬(또는 병합정렬), 쉬트라쎈(Strassan)의 행렬곱셈 알고리즘, 카라츠바 빠른곱셈 알고리즘 등을 참고해보면 좋다.

저작자 표시 비영리 동일 조건 변경 허락
신고

'Development > Algorithm' 카테고리의 다른 글

분할정복법 (Divide and Conquer)  (0) 2013.08.11
Posted by Kugi

댓글을 달아 주세요



티스토리 툴바