Divide and Conqure Algorithm(1)

분할정복 방법의 원리

: 순환적(recursively)으로 문제를 푸는 하향식(top-down) 접근 방법

• 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해 원래 문제의 해를 구하는 방식

  → 문제들을 작은 문제로 분할하다보면 원하는 해가 구해짐

• 특징

  • 분할된 작은 문제는 원래 문제와 동일하다

    → 단 입력 크기만 작아짐

  • 분할된 작은 문제는 서로 독립적

    → 순환적 분할 및 결과 통합이 가능

분할정보 방법의 처리 단계

각 순환 호출마다 세 단계의 처리 과정을 가짐

• 분할: 주어진 문제를 여러 개의 작은 문제로 분할
• 정복: 작은 문제를 순환적으로 분할. 더 이상 분할되지 않을 정도로 크기가 작다면 순환호출 없이 작은 문제의 해를 구함
• 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다 (* 결합단계가 없는 문제도 존재)

적용 알고리즘의 종류 및 분할과정

• 이진탐색

  n개가 있다면 n/2씩 쪼갬. 절반은 처리 대상에서 제거, 나머지 절반을 n/2씩 쪼갬을 반복

• 합병정렬

  n개가 있다면 n/2씩 쪼갬. 양 쪽 모두 충분히 작아질 때까지 n/2씩 쪼갬을 반복

• 퀵 정렬

  n개가 있다면 a와 b(크기가 일정하지 않음)으로 쪼갬. 이를 반복

• 선택 문제

  n개가 있다면 a와 b(크기가 일정하지 않음)으로 쪼갬. 한 쪽은 처리 대상에서 제거, 나머지 절반을 a와 b로 나눔을 반복

이진 탐색

데이터가 나열되어 있다면 그 중 내가 원하는 데이터를 찾아내는 방식.

• 정렬된 상태의 입력데이터에 대한 효과적인 탐색 방법

  → 여기서 정렬은 오름차순으로 정렬되어있다고 가정.

• 탐색 방법

  • 배열의 가운데 원소 A[mid]와 탐색키 x를 비교

    1) 탐색키 = 가운데 원소 → 탐색 성공!(인덱스 mid반환 후 종료)

    2) 탐색키 < 가운데 원소 → 이진탐색(원래 크기 1/2 왼쪽 부분 배열) 순환 호출

    3) 탐색키 > 가운데 원소 → 이진탐색(원래 크기 1/2 오른쪽 부분 배열) 순환 호출

    ⇒ 탐색을 반복할 때마다 대상원소의 개수가 1/2씩 감소

개념의 원리

• 분할

  배열의 가운데 원소를 기준으로 왼쪽 오른쪽 부분 배열로 분할, 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환/종료

• 정복

  탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출

• 결합

  필요 없음(부분배열에 대해서 탐색결과가 직접 반환된다)

알고리즘

BinarySearch(A[], Left, Right, x)
{
	if(Left > Rigth) return -1; // fail
	Mid = (Left+Right)/2; // floor(소수점버림)
	if(x==A[Mid]) return Mid; // success
	else if (x<Mid) BinarySearch(A, Left, Mid-1, x); // 왼쪽 부분배열
		else BinarySearch(A, Mid+1, Right, x); // 오른쪽 부분배열 
}

→ 순환 형태 (비효율

BinarySearch_Iteration(A[], n, x)
{
	Left = 0; Right = n-1;
	while(Left <= Right) {
		Mid = (Left+Right)/2;
		if(x == A[mid]) return Mid; //success
		else if (x<A[Mid])Right = Mid - 1; // 왼쪽 부분배열
			else Left = Mid + 1; // 오른쪽 부분배열
	}
	return -1; // fail
}

이진탐색에서의 분할 및 비교 횟수

입력크기 n일 때 최대 분할횟수와 비교횟수

• 최대 분할횟수 = n/2k = 1 → $k = log n$
• 최대 비교횟수 → 최대분할횟수 + 1

성능 분석

BinarySearch(A[], Left, Right, x)
{
	if(Left > Rigth) return -1; 
	Mid = (Left+Right)/2; 
	if(x==A[Mid]) return Mid; 

	else if (x<Mid) BinarySearch(A, Left, Mid-1, x); 
		else BinarySearch(A, Mid+1, Right, x); 
}

T(n) = 입력크기 n에 대한 탐색 과정에서의 모든 비교횟수의 합

= 맨 바깥수준에서의 비교횟수(상수) + 순환 호출에서의 비교 횟수(n)

= T(n) = T(n/2) + O(1) , T(1) = 1

⇒ O(logn)

특징

• 입력 배열의 데이터가 정렬된 경우에 대해서만 적용 가능
• 삽입/삭제 연산은 부가적인 데이터 이동을 수반
  • 데이터의 정렬 상태 유지를 위해서 평균 n/2개의 데이터 이동이 발생 → 삽입/삭제가 빈번한 응용에서는 부적합