[알고리즘] 분할정복(Divide&Conquer) 이란?

 

 

 

 

분할정복(Divide&Conquer)이란?

 

재귀호출 방식의 완전탐색의 단점을

보완하는 방식으로

 

전체를 부분으로 분할(Divide) 한 뒤 

다시 부분을 전체로 병합(Merge)하는 과정을 거쳐

문제를 해결하는 방식이다.

 

 

 

[알고리즘] 재귀호출(recursive call)이란?

 

 

 

재귀호출(Recursive Call)은

발생 가능한 모든 조합을 완전탐색하는 방식으로

 

 

 

 

n부터 1까지 모든 함수가 호출된다.

 

하지만 이런 재귀호출 방식은

특정한 규칙이 있는 문제라면 비효율이다. 

 

 

분할정복(Divide&Conquer)

 

1부터 n까지 합을 구하는 함수  SUM 함수가 있다. 우선, 재귀호출 방식으로 접근해보자.

 

예시)  1부터 5까지 합을 구하라.

 

첫 번째 호출  : SUM(5) = SUM(4) + 5

두 번째 호출  : SUM(4) = SUM(3) + 4

세 번째 호출  : SUM(3) = SUM(2) + 3

네 번째 호출  : SUM(2) = SUM(1) + 2

다섯번째 호출  : SUM(1) = 1

 

이제 이를 분할정복 방식으로 접근해보자.

1 + 2 + 3 + ... +  n을 반으로 나누면 1 + 2 + 3+ ... + n/2 + ( n/2+1 ) +  ( n/2+2 ) + ( n/2+3 )... + ( n/2+ n/2 ) 이다.

 

덧셈에는 교환법칙이 성립하므로 식을 변형하면

 

= 1 + 2 + 3+ ... + n/2 + n/2*n/2 + 1 + 2 + 3+ ... + n/2

= 2*( 1 + 2 + 3+ ... + n/2 )  + n/2^2

= 2*SUM(n/2) + n/2^2 

 

이렇게 n/2로 분할접근이 가능한 계산은 재귀호출로 계산하면 효율이 떨어진다. 

이제 이를 파이썬 코드로 작성해보자.

 

def SUM(n):
    if n==1 : return 1 // n이 1인 경우 
    elif n%2==1 : return SUM(n-1) + n // n이 홀수인 경우
    return 2*SUM(n/2) + (n/2)*(n/2) // n이 짝수인 경우

print("결과 : " , SUM(4))

 

첫 번째 호출  : SUM(5) = SUM(4) + 5

두 번째 호출  : SUM(4) = 2*SUM(2) + 4

세 번째 호출  : SUM(2) = 2*SUM(1) + 1

네 번째 호출  : SUM(1) = 1

 

단 네 번의 호출만으로 값을 구할 수 있고 n이 커지면 커질수록 효율은 증가한다. 이렇듯 분할정복은 분할하여 접근할 수 있는 규칙성이 있는 문제의 경우, 재귀호출을 이용한 완전탐색이 아닌 분할정복으로 접근하여 효율을 높힐 수 있다.

 

 

 

---

 

 

참고자료

알고리즘 문제 해결 전략 세트 : 네이버 도서