[Algorithm] Divide & Conquer

분할정복

• 주어진 문제를 크기가 작은 여러개의 부분문제로 분할(Divide)하여 부분 문제를 정복(Conquer)한 후에 그 해들을 결합(Combine), 원래 문제에 대한 해를 구하는 재귀방식의 알고리즘
• 주로 재귀적인 특성을 갖춘 경우가 많다.

• 알고리즘이 재귀 호출에 의한 경우 그 알고리즘의 수행 시간은 순환 방정식에 의해 표현 가능하다.
  가령, T(n)을 입력 크기가 n인 문제에 대한 시간 복잡도 함수라 가정하자.
  만일, 문제 크기가 1일 때, 직접 해를 구할 수 있다면, 그때의 시간 복잡도 함수는 C(상수)로 표현이 가능할 것이다.
  또한 어떤 문제가 크기 n/b인 a개의 부분문제들로 분할된다고 가정하자. 만약 문제를 분할하는데 d(n)의 시간이 걸리고, 부분 문제들의 해를 결합하여 원래의 문제의 해를 만드는데 c(n)의 시간이 걸린다면 크기가 n/b인 하나의 부문 문제를 해결하기 위해서는 T(n/b) 시간이 걸릴 것이고, 시간복잡도 T(n)은 다음과 같이 표현 될 수 있다.

---

배열의 덧셈

• 일반적인 배열의 덧셈을 진행하게 되면, ∑ (Summnation)를 사용하면 된다.
  먼저, 일반적인 방법으로 배열의 앞 부분부터 끝까지 더하게 될 경우, n개의 숫자가 있을 경우 n번의 덧셈을 진행하게 된다.
• 만일, 분할정복 방식을 이용한다면 이야기가 조금 달라진다.
  
  

int sum(int a[], int left, int right)
{
	int mid, sum_left, sum_right;
	if(left == right) return a[left];	// 배열의 원소가 1개인 경우
	else
	{
		mid = (left+right)/2;
		sum_left = sum(a,left,mid);
		sum_right = sum(a,mid+1, right);
		return sum_left + sum_right;
	}
}

• 위 코드를 분석해보자.
  예를 들어, main 함수에서 arr이라는 배열과 배열의 시작점 그리고 끝점을 각각 매개변수로 받아왔다고 가정하자.
  먼저, 재귀함수의 특징인 '탈출구'를 만들어준다. 이 '탈출구'의 역할은 원소가 하나일 경우, 해당 원소를 반환하는 경우이다. 즉, 위에서 이야기한 순환함수에서 n = 1인 경우가 이에 해당한다.
  만일, 원소가 1개가 아니라면, 배열을 작게 잘라(divide) 문제를 분할할 것이다. 분할된 배열은 각각 left와 right로 나뉘고, 그에 해당하는 영역 만큼 다시 sum을 재귀호출하여 문제를 계속해서 작게 만들 것이다.
  이렇게 작아진 원소가 마침내 1개가 된다면, 해당 원소를 반환하고, 반환된 원소는 각각 sum_left와 sum_right가 될 것이다.
  구해진 sum_left와 sum_right는 return sum_left + sum_right를 통해 합쳐지고, 스택 형식으로 호출 된 재귀함수는 해당 함수를 return값을 돌려보낸 뒤 pop 할 것이다.
  이렇게 작게 쪼개진 원소들의 합을 최종적으로 돌려보낸다.
  그림으로 표현하면 다음과 같다.

• 이 과정에서, 시간적인 측면에서는 더욱 효율적일 수 있으나, 앞서 설명한 바와 같이 재귀호출은 Stack 공간의 추가적인 할당이 요구된다. 따라서, 공간 복잡도 측면에서 바라본다면, 반복문이 더욱 효율적이다.

---

두 정수의 곱셈

• 음이 아닌 두 정수 x, y의 곱 x*y는 다음과 같이 재귀정으로 정의가 가능하다.

• 이를 코드로 표현해보면 다음과 같다.

int multiply (int x, int y)
{
	int z;
	
	if(y==0) return 0;
	z = multiply(x, int(y/2);
	if(y%2==0) return 2*z;
	else return x+2*z;
}

• 이는 x,y가 n비트 정수일 때, n번의 재귀 호출 후에 종료된다. 이는 매 호출마다 y가 2로 나뉘어 지는데 이 의미는 비트연산에서, y를 오른쪽으로 한 비트 시프트 하기 때문이다.

---

이진탐색(Binary Search)

• 분할정복을 사용한 대표적인 Search Algorithm이다.
  
  

int BinarySearch(int a[], int left, int right, int x)
{
	int mid;
	
	if(left <= right)
	{
		mid = (left + right)/2;
		
		if(x==a[mid]) return mid;
		else if(x < a[mid]) return BinarySearch(a, left, mid - 1, x);
		else return BinarySearch(a, mid+1, right, x);
	}
	
	return 0;
}

---

병합정렬(Merge Sort) / 퀵 정렬(Quick Sort)

• 분할정복을 사용한 대표적인 Sort Algorithm이다.
  이미 다룬 바 있으므로, 참고바란다.
  https://waterglass0105.tistory.com/20

Sort