[ 알고리즘 개념 ] 분할정복 (Divide and Conquer)

분할정복

 

분할정복은 방대해서 있는 그대로 해결할 수 없는 거대한 문제를 잘게 나누어서 각각의 작은 문제를 해결한 후 이 결과를 다시 합병하여 최종 결과를 내는 방법이다.

합병정렬이나 퀵 정렬 등 정렬문제에서도 사용되고, 슈트라센 알고리즘(Strassen Algorithm) 이나 고속 푸리에 변환(FFT) 문제 등 다방면의 문제 해결에서 사용된다.

 

분할정복을 설계할 때는 공통적으로 세 가지 과정을 거친다.

 

(1) Divide (분할) - 문제를 잘게 쪼개기 ★(중요)

(2) Conquer (정복) - 소문제를 해결하기

(3) Combine (병합) - 각각의 결과를 병합하여 최종 결과 도출하기

 

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

BOJ의 2630번 색종이 만들기의 경우 분할정복풀이의 단적인 예이다.

 

 

(1) 정사각형의 색종이를 색깔이 똑같은 원소로만 이루어질 때까지 더 작은 정사각형으로 잘게 나누고

(2) 각각의 작은 정사각형의 색깔을 반환하고

(3) 반환된 결과를 모아서 출력한다.

 

이 문제를 비롯하여 분할정복 문제를 풀이할 때 가장 신경써야 할 부분은 (1) 분할(Divide) 이다.

보통 분할 과정은 재귀호출을 이용하게 되는 경우가 많은데 자칫하면 시간복잡도가 필요 이상으로 높아질 수 있기 때문이다. 분할만 효율적으로 설계한다면 (2) Comquer, (3) Combine 은 쉽게 해결할 수 있다.