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

분할 정복(Divide and Conquer)이란?

주어진 문제의 입력을 나눌 수 없을 때까지 분할(Divide)하여 문제를 해결(Conquer : 정복)한 뒤, 다시 병합(Combine)하는 방식의 알고리즘으로, 이진 탐색(Binary Search) 알고리즘, 병합 정렬(Merge Sort) 알고리즘, 퀵 정렬(Quick Sort) 알고리즘 등에 사용된다.

Divide : 문제가 분할이 불가능할 때까지, 2개 이상의 문제로 나눈다.

Conquer : 문제를 해결한다.(정렬, 탐색 등)

Combine : Conquer한 문제들을 병합하여 원래 문제의 답을 얻는다.

분할 정복(Divide and Conquer)의 특징

1. 분할된 문제들은 크기만 작아질 뿐, 원래 문제와 성격이 동일하다.

 

2. 대개 재귀적인 방식으로 구현하나, 빠른 실행이나 부문제 해결 순서 선택을 위해, 스택(Stack), 큐(Queue)등의

  자료구조를 이용하여 구현하기도 한다.

 

3. 문제를 매번 절반으로 나눌 수 없을 때까지 분할하는 시간 복잡도는 O(logN)이다.

 

 

분할 정복(Divide and Conquer)을 이용한 알고리즘

1.이진 탐색(Binary Search)

입력이 정렬된 리스트에 대해서만 적용 가능하고, 삽입/삭제 연산 시 데이터의 정렬 상태를 유지해 줘야 한다.

 

값	1	4	7	10	13	16
인덱스	0	1	2	3	4	5

left =0

right =5

mid = 2 //(0+5)/2

search =4 //찾는 값

찾는 값이 mid의 값과 같다면 즉시 mid를 반환,

mid보다 작다면 mid 왼쪽 그래프에 대해 다시 탐색

mid보다 크다면 mid 오른쪽 그래프에 대해 다시 탐색

값	1	4
인덱스	0	1

left =0

right =1

mid = 0 // (0+1)/2

search = 4 //찾는 값

찾는 값이 mid의 값보다 크기 때문에 mid 오른쪽 그래프에 대해 다시 탐색

 

값	4
인덱스	1

left =1

right =1

mid =1 //(1+1)/2

search = 4 //찾는 값

찾는 값이 mid의 값과 같기 때문에 mid를 반환한다.

여기서 만약 찾는 값이 3이라면, mid의 값과 찾는 값이 다르고, 더 이상 리스트를 분할할 수 없기 때문에

리스트에 찾는 값은 없다고 볼 수 있다.

 

코드(c++) 직접 구현

#include <iostream>
using namespace std;

int binary(int low, int high, int *arr,int search) {
	int mid = (low + high) / 2;
	//값을 찾으면 해당 인덱스를 반환
	if (arr[mid] == search)
		return mid;
	//더 이상 나눌 수 없으면서 값이 없으면 -1을 반환
	else if (low >= high)
		return -1;
	else {
		//찾는 값이 리스트의 가운데 값보다 작으면 왼쪽 그래프에 대해 다시 이진 탐색
		if (arr[mid] > search)
			return binary(low, mid - 1, arr, search);
		//찾는 값이 리스트의 가운데 값보다 크면 오른쪽 그래프에 대해 다시 이진 탐색
		else
			return binary(mid + 1, high, arr, search);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int sortedArray[7] = { 1,4,7,10,13,16,19 };
	int search[4] = { 4,16,20,5 };
	for (int i = 0; i < 4; i++) {
		cout <<search[i]<<"는 어디에? : "<< binary(0,7,sortedArray,search[i]) << '\n';
	}
	return 0;
}

코드(c++) algorithm 헤더 파일의 binary_search(start,end,key) 함수 활용

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int sortedArray[7] = { 1,4,7,10,13,16,19 };
		int search[4] = { 4,16,20,5 };
		for (int i = 0; i < 4; i++) {
			cout << search[i] << "이 있는가? : ";
			cout <<binary_search(sortedArray, sortedArray + 7, search[i]) << '\n';
		}

	return 0;
}

2. 2021.07.21 - [알고리즘/알고리즘] - [알고리즘] 병합/합병 정렬(Merge Sort)    

3. 2021.07.19 - [알고리즘/알고리즘] - [알고리즘] 퀵 정렬(Quick Sort)