[알고리즘] 분할정복, Divide-and-Conquer

divide-and-conquer의 핵심은 재귀호출이다.

  전체를 풀 때와 부분을 풀 때의 풀이가 같은 경우 큰 문제를 작은 문제로 쪼개서 해결하는데, 이 때 top-down 방식과 bottom-up방식이 있다. 

 

 

top-down: 처음부터 큰 문제를 방문 후 작은 문제를 호출, 재귀(recursive)방식 사용
bottom-up: 작은 문제들부터 해결 후 이를 바탕으로 더 큰 문제들을 해결, 반복(iterative) 방식 사용

  top-down과 bottom-up 모두 문제를 쪼갠다는 점에서 비슷해보일 수 있지만 시도 자체가 다르다. top-down은 처음부터 큰 문제를 해결하려고 시도하지만, bottom-up은 큰 문제부터 해결하려하지 않고 작은 문제부터 시작한다.

 

  divide-and-conquer은 위의 두 방법 중에서 top-down 접근 방식을 사용한다. 이것이 바로 divide-and-conquer의 핵심이 재귀호출인 이유이다.  이름에서도 알 수 있듯이, 문제를 여러 개의 작은 문제로 분할(Divide)하고, 정복(Conquer), 즉 해결한다. 

 

  divide-and-conquer은 서로 상관관계가 없는 문제를 해결하는데 적합하다. (반면, dynamic programming은 서로 상관관계가 있는 문제를 해결하는데에 적합.) 여기서 상관관계가 없다는 것은 쪼개진 문제들간의 내용이 서로 연관이 없다는 것이다. 예를들면 배열을 반으로 쪼개 왼쪽 배열, 오른쪽 배열 이렇게 두 문제로 풀 때, 왼쪽 배열 풀이 결과가 오른쪽 배열 풀이에 영향을 주지 않는다는 것이다. 서로 독립적이다. (눈치 챘겠다시피, dynamic programming으로 해결하는 문제는 계산 값이 서로 연관되어있다.)

 

  사실 직접 코드를 보지 않는 이상 위 글만 보고 무슨 내용인지 이해하기는 힘들다. 코드를 보면서, 서로 상관관계가 있는지, 없는지 직접 확인하고, 어떤 의미에서 top-down인지, 왜 재귀인지 알아보는게 좋을 듯하다. divide-and-conquer를 사용하는 대표적인 알고리즘으로는 binary search, merge sort, quick sort, matrix multiplication 등이 있다. 이번 divide-and-conquer 카테고리에서 이 알고리즘들에 대해 하나씩 알아보자.

 

[알고리즘] 이진탐색, Binary Search | 설계 및 분석

 

[알고리즘] 합병 정렬, Merge Sort | 설계 및 분석

 

[알고리즘] 퀵 정렬, Quick Sort | 설계 및 분석