Divide and Conquer Algorithm Design Pattern에 대해서

기본적으로 문제를 해결 가능할 적도로 작은 부분들로 나누어 각각을 공략하여

결국은 최초의 문제를 해결한다는 방법이다.

 

기본적으로 recursive한 패턴이 알고리즘 설계에 편하지만 

경우에 따라 call stack overflow를 초래할 수 있으므로

interative한 패턴도 생각해 두는 것이 좋다.

 

예시를 보면서 패턴에 대해서 이해해보자.

 

아주 큰 정수 2개를 곱하는 연산을 하는 알고리즘을 만들어보도록 하자.

 

먼저 23 * 14를 다음과 같이 표현해보자.

(23=2*10^1+3*10^0)

(14=1*10^1+4*10^0)

(23*14=[2*10^1+3*10^0]*[1*10^1+4*10^0])

(=[2*1]*10^2+[2*4+1*3]*10^1+[3*4]*10^0)

 

그리고 2*1과 3*4란 곱하기 연산의 결과를 활용하기 위해서 아래와 같이 표현하자.

(2*4+1*3=[2+3]*[1+4]-2*1-3*4)

 

이렇게 되면 낮은 차수 수들의 3번의 곱하기 연산으로 연산 결과를 획득 할 수 있다.

 

한 가지 예시를 더 생각해보며 일반화 해보자.

(2048=20*10^2+48)

(4037=40*10^2+37)

(2048*4037=[20*40]*10^4+[20*37+48*40]*10^2+[48*37])

(20*37+48*40=[20+48]*[40+37]-[20*40]-[48*37])

 

위 예시를 한자리 숫자 까지 나누어 연산을 진행한다고 하면 다음과 같은 그래프를

확인할 수 있을 것이다.

 

 

알고리즘의 시간 복잡도를 T, 각 분할한 부분문제의 개수를 b, 부분문제를 병합하는 시간을 f라고 하자.

이때 다음과 같은 점화식을 생각해 볼 수 있다.

(T_n=b*T_{n/b}+f_n) 

이때, 모든 문제가 같은 깊이까지 분할되는 것은 아니므로 (a \leq b)를 사용하여

식을 수정하면  다음과 같다.

(T_n=a*T_{n/b}+f_n)

 

이 점화식을 풀어보면 

(T_n=f_n+a*T_{n/b})

(=f_n+a*f_{n/b}+a^2*T_{n/b^2})

(=f_n+a*f_{n/b}+a^2*f_{n/b^2}+\cdots +a^{log_b{n}}*f_1)

(=\sum_{i=0}^{log_b{n}}a^i*f_{n/b^i} )

 

위와 같은 방식으로 시간 복잡도를 계산할 수 있다.

이를 케이스별로 연산한 Master Theorem을 확인해볼 수 있다.

 

Divide And Conquer는 recursive한 패턴으로 

알고리즘을 작성할때 편의성이 좋고 최적의 답에 접근하기 좋다는

장점이 있지만 케이스에 따라서 방대한 call stack으로

알고리즘을 실행시키는 것 조차 실패할 수 있다.