Algorithm - Divide and Conquer(분할 정복)

Divide and Conquer algorithm :

분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. (원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제들로 나눈다)

 

Divide and Conquer 알고리즘 설계 요령 (도식화) :

- Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. / 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.

- Conquer : 나누어진 문제가 여전히 분할이 가능하면, 다시 divide를 수행. 그렇지 않다면 문제를 푼다. / 가장 작은 단위의 하위 문제를 해결하여 정복.

- Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. / 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

 

분할 정복 장단점 :

ㆍ분할된 작은 문제는 원래 문제와 성격이 동일함 = 입력 크기만 작아짐

ㆍ분할된 문제는 서로 독립적임 (중복 제거x) = 순환적 분할 및 결과 결합 가능

ㆍTop-down 재귀 방식으로 구현하기 때문에 코드가 직관적임

ㆍ문제를 나누어 해결한다는 특성상 병렬적으로 문제를 해결 할 수 있음.

ㆍ재귀 함수 호출로 overhead가 발생할 수 있음

ㆍStack에 다량의 데이터가 보관되는 경우에도 overflow 문제가 생길수 있음

Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다 함. -> Divide를 잘 설계하는게 중요함.

분할 정복 알고리즘은 재귀 알고리즘이 많이 사용됨 -> 이게 분할 정복 알고리즘의 효율성을 깎아내릴수 있음. 

 

분할 정복 알고리즘은 보통 재귀 함수로 구현하지만, 함수 호출 오버헤드 때문에 실행 속도가 늦어질 수 있어서 빠른 실행이나 부문제 해결 순서 선택을 위해, 재귀 함수대신 Stack, Queue 등의 자료구조로 분할 정복법 구현 가능.

 

분할 정복의 응용 :

Quick sort, Merge sort, 고속 푸리에 변환

ㆍ병합 정렬 : 

폰 노이만이 개발한 알고리즘. 시간 복잡도는 O(nlogn), 공간 복잡도는 O(n). 

알고리즘 - ①. 정렬할 데이터 집합의 크기가 0 또는 1이면 이미 정렬된 것으로 본다. / ②. 그렇지 않다면 데이터 집합을 반으로 나눈다. / ③. 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬. / ④. 데이터 집합이 다시 하나가 될 때까지 ③을 반복.

두 데이터를 합치는 방법 - ①. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다. / ②. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제. / ③. 원래 두 데이터 집합의 요소가 모두 삭제될 때까지 ②를 반복. 

ㆍ거듭 제곱 (Exponentiation) :

n 거듭 제곱은 자신을 n번 곱해야 하므로 O(n)의 시간이 소요됨. 

C의 8제곱은 C*C*C*C*C*C*C*C 로 정의 되지만

((C^2)^2)^2 <-로 개선 가능

ㄴ> C^8을 구할때 C를 8번 곱하지 않고, C^2를 구한 뒤 제곱을 두번 더 반복하면 세번의 연산만으로 같은 결과를 얻을 수 있음. / 지수가 짝수일때는 지수를 반으로 나눠서 곱한다. / 홀수일때는 지수에서 1을 빼고 반으로 나누어서 곱하고 밑을 한번 더 곱하면 됨. => 수행시간 O(log2N)

ㆍ피보나치 수열 (Fibonacci Sequence)

F(n) = { n = 0 , n = 1 , F(n-1) + F(n-2) ( n > 1 ) }  ==> O(2^n)

[ F(2) F(1) ]  =  [ 1  1 ]   (2차 정사각 행렬 사용)

[ F(1) F(0) ]      [ 1  0 ] 

[ F(n+1)   F(n)   ]    =    [ 1   1 ] ^n  =  [ 1   1 ] ^n/2 [ 1   1 ] ^n/2

[ F(n)      F(n-1) ]          [ 1   0 ]           [ 1   0 ]        [ 1   0 ] 

ㄴ> 거듭제곱 알고리즘과 비슷. 수행 시간은 O(log2N)