자바 알고리즘 인터뷰 22. 분할 정복

분할 정복 알고리즘은 영어로 Divide and Conquer 줄여서 DAC 알고리즘이라고 한다.

 

분할 정복 알고리즘은 이름에서도 나오듯이 분할 그 다음 정복이라는 단계로 이어진다. 즉 2단계로 구성이 된다.

 

분할 정복 알고리즘을 수도 코드로 표현한 결과는 아래와 같다.

DAC(a, i, j)
{
    if(small(a, i, j))					
      return(Solution(a, i, j)) //분할정복을 하기 전에 답이 나오는 경우
    else 
      mid = divide(a, i, j)             
      b = DAC(a, i, mid)                 
      c = DAC(a, mid+1, j)            
      d = combine(b, c)                 
   return(d)
}

 

1.  퀵 정렬

 

2. 병합 정렬

 

3. Cooley-Tukey FFT 알고리즘

 

4. Karatsuba 알고리즘

x = x_1*2^(n/2)+x_r

y = y_1*2^(n/2)+y_r

xy = (x_1*y_1) * 2^(n) + [(x_1+x_r)(y_1+y_r)-x_1*y_1-x_r*y_r]*2^(n/2)+x_r*y_r

와 같은 방법으로 큰 수의 곱을 계산하는 알고리즘인데 이 과정에서 분할 정복 방법론이 포함된다.