알고리즘 - 분할 정복(Divide and Conquer)

전체의 큰 문제를 서로 다른 작은 문제로 나누어 풀고 합쳐서 전체 문제의 답을 구하는 알고리즘.

 

동적 계획법과 같아보이지만, 분할 정복은 "문제의 영역이 겹치지 않도록 나눈" 작은 문제로 푼다는 점이다.

 

1. 문제를 나눈다. 겹치지 않고 빠지는 경우가 없도록 나눈다.

2. 더이상 나눌수 없을때까지 1을 반복.

3. 분할이 끝나면 작은 문제들을 푼다.

4. 푼 문제들을 합쳐간다.

5. 전체 문제가 될때까지 4를 반복.

 

대표적인 문제

합병 정렬,  a^n 구하기.

 

a^n 구하기

 

1. n이 홀수일때 a^n을 a*a^(n-1) 로 나눈다.

2. n이 짝수일때 a^n을 a^(n/2)*a^(n/2) 로 나눈다.

 

더 나눌수 없을떄 까지 나누어 놓고 계산해서 점점 합쳐간다.