[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 1.일반론

1. 설계전략
 ⓐ 분할(Divide)
  - 문제를 풀기 쉽도록 여러개의 작은 하위 문제들(Sub Problems)로 나눈다.
 ⓑ 정복(Conquer)
  - 더 작은 하위 문제들을 회귀적으로 푼다.
 ⓒ 통합(Merge)
  - 본 문제에 대한 답을 구하기 위해 하위 문제들의 답을 합친다.

2. 문제 : 배열의 최대 값과 최소 값 찾기
 - 일반 해결법
  ⓐ 배열의 값을 일일이 비교하며 최대값을 구한다.
  ⓑ 최대값을 제외한 모든 값을 비교하며 최소값을 구한다.
   > 효율
    - 배열의 크기 : n
    - 비교 횟수 : n - 1
    - 총 비교 횟수 : n-1(최대값 비교횟수) + n-2(최소값 비교횟수) = 2n - 3
 - 분할 정복을 이용한 해결법
  ⓐ 배열을 반으로 나눈다.
  ⓑ 양쪽 절반들의 최대값과 최소값을 구한다.
  ⓒ 배열 전체의 최대값과 최소값을 구하기 위해 두 개의 최대 값들과 두개의 최소 값들을 비교한다.

  > 코드
  void findMaxMin(int i, int j, int low, int high){
   int mid, min1, min2, max1, max2;
   if ( i == j ){ low = a[i] ; high = a[i]; }  //base case
   else if ( i == j-1 ){
    if ( a[i] < a[j] ){ low = a[i]; high = a[j]; }
    else{ low = a[j]; high = a[i]; }
   }else{
    mid = rounddown((i+j)/2);   //정확히 반으로 안나눠 질시 소수점을 버린다.
    findMaxMin(i,mid,min1,max1);
    findMaxMin(mid+1, j, min2, max2); 
    low = MIN(min1, min2);
    high = MIN(max1, max2);
   }
  } 

  > 분석 : 알고리즘에 대한 실행 트리로 비교 횟수를 구하자.
  

반으로 나눌시 원소가 개수가 3개 이상일 경우는 최대값과 최소값을 구하기 위해 2번의 연산이 필요하다.
(좌측의 최대과 우측의 최대 비교)
(좌측의 최소와 우측의 최소 비교)

반으로 나눌시 원소의 개수가 2개 일경우 때는 단 한번의 비교로 최대값과 최소값을 모두 알 수 있다. 

원소가 하나일 때는 비고할 필요가 없다.

   위 트리에서 비교 횟수를 합하면 2 * ( n/2 -1 ) + n/2 = 3/2n -2 이다.
   이는 일반적인 방법보다 더 효율적인 방법이라고 할 수 있다.

   모든 개선은 트리의 가장 낮은 수준(level)에서 이뤄진다. 점화식을 이용하여 비교 횟수를 계산/비교 할 수 있다.
 
3. 균형 취하기(balancing)
 일반적으로 문제를 거의 같은 크기의 하위 문제로 나누는 것이 좋다. 위 문제에서 우리가 배열의 한 요소를 S1에 넣고, 나머지 요소들을 S2에 넣는다면 실행트리는 다음과 같이 될 것이다.

 
총 비교 횟수 = 2(n-2) + 1
                  = 2n - 3