[알고리즘 기법] 분할정복법 ( Divide and Conquer )

 

◇  설명

  ◎  분할 정복법  ( Divide and Conquer )

    -  복잡한 큰 문제를 해결하기 위해 둘 이상의 작은 문제로 나눈 뒤, 각 문제에 대한 답을 재귀 호출을 이용해 계산하고,
       각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 알고리즘 설계 기법
    -  일반 재귀 호출과 약간의 차이가 있음
     ∎  분할 정복  --  문제를 절반씩으로 나눔 ( 거의 같은 크기의 부분 문제로 나눔 )
     ∎  재귀 호출  --  문제를 한 조각과 나머지로 쪼갬
    -  큰 문제를 작은 부분 문제들로 나눈다는 것은 동적계획법과 비슷하지만, 차이가 있음
     ∎  분할 정복  --  부분 문제들이 서로 독립적이다. 연관이 없다
     ∎  동적 계획법  --  부분 문제들이 같은 부분 문제에 의존함 ( -> 중복 계산이 많아짐 )

  ◎  분할 정복을 사용하는 알고리즘들의 구성 요소
    1.  문제를 더 작은 문제로 분할하는 과정 ( divide )  --  문제를 어떻게 분할할지
    2.  각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 ( merge )
    3.  더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 ( base case )

 

◇  코드

  ex)  1부터 n까지의 합 ( 수열의 빠른 합과 행렬의 빠른 합 )

	public static int sum( int n ) {  // 일반적 재귀 호출
		if( n == 1 ) return 1;
		return n + sum( n - 1 );
	}
	
	public static int sumFast( int n ) {  // 분할 정복 
		if( n == 1 ) 		return 1;
		if( n % 2 == 1 ) 	return sumFast( n-1 ) + n;
		return 2 * sumFast( n / 2 ) + (n/2)*(n/2);
	}

  ex)  거듭 제곱

	public static long power( int k ) {
		if( k == 0 ) return 1;  // if( k == 1 ) return a % c;
		long tmp = power( k / 2 );
		long res = ( tmp * tmp ) % c;
		if( k % 2 == 1 ) return ( res * a ) % c;
		return res;
	}

  ex)  병합 정렬, 퀵 정렬
      ( hyunjiishailey.tistory.com/161?category=381527 )

 

◇  출처

  -  설명  --  알고리즘 문제 해결 전략 ( 구종만 )
  -  코드  --  〃, 등등