[알고리즘] 분할정복

아래 글은 'Introduction to Algorithms(한빛아카데미)'와 분할 정복 블로그 를 보고 정리한 것이다.

대표 문제

• 백준 6549번: 히스토그램에서 가장 큰 직사각형

분할 정복

분할 정복(Divide and Conquer)은 (1) 분할과 (2) 정복, (3) 결합의 세 가지 단계를 거치면서 재귀적으로 문제를 해결한다.

• 분할: 현재의 문제와 동일하되 입력의 크기가 크기, 또는 문제의 크기를 더 작은 부분 문제로 분할한다.
• 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다.
• 결합: 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다.

부분 문제가 재귀적으로 풀 수 있을 만큼 충분히 클 때, 재귀 대상이라고 한다. 부분 문제가 충분히 작아져 더 이상 재귀 호출을 할수 없을 때, 재귀가 "바닥을 쳤다"고 하고 베이스 케이스까지 내려왔다고 이야기한다. 때로는 입력의 크기가 더 작은 완전히 동일한 부분 문제 외에 원래의 문제와 다른 부분 문제를 풀어야 할 때도 있다. 그런 부분 문제는 결합 단계의 일부로 간주한다.

 

세 가지 단계를 거치며 할 일이 많아진 것처럼 보일 수 있지만, 그렇지 않다. 특히 충분히 작아져 풀린 부분 문제들을 합치는게 아주 빠른 경우에는 분할 정복 알고리즘이 효과적이다.

예시) 병합 정렬, 이진 탐색, 거듭제곱 연산

부분 문제의 결합

분할정복 알고리즘에서 부분 문제로 해결되지 않는 문제가 있다. 분할점에 답이 걸쳐저 있는 경우 단순 양쪽으로 분할된 부분 문제들로는 답을 찾을 수 없다. 따라서 매번 문제를 결합할 때마다 가장 중간부터 양쪽으로 문제의 답을 구해보는 방법이 있다. 백준 히스토그램 문제가 대표적인 경우이다.