분할정복.pdf

분할정복 소스코드.pdf

분할 정복은 문제를 중복되지 않은 작은 문제로 나누어서 풀고, 다시 합쳐서 정답을 구하는 방법이다.

퀵소트, 머지소트 등의 예시가 있다.

(1) 이분 탐색 (Binary Search)

• 정렬되어있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘
• 리스트 크기가 N일 때 정렬되어있다고 가정했을 때 O(logN)의 시간복잡도가 된다.
• N + N/2 + N/4 + N/8 + … + 1 과 같이 연산하고, logN씩 나누어서 연산하므로 logN번의 탐색이 되는 것이다.

L = 0, R = 8, M = 4 로 시작하여 배열에서 4를 찾아보자. M 값인 7은 4보다 크기 때문에 왼쪽에 4가 있음을 알 수 있다. 그래서 R을 M-1로 바꾸고 다시 반복한다.

이제는 M이 4보다 작다. 따라서 L을 M+1로 이동한다.

이렇게 4를 찾을 수 있다. 만약 없는 수를 찾게 되면 아래와 같이 L > R인 경우가 생긴다.

while (left <= right) {
	int mind = (left + right) / 2; 
	if (a[mid] == x) {
		position = mid;
		break;
	}
	else if (a[mid] > x)
		right = mid - 1;
	else
		left = mid + 1; 
}

10815 숫자카드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\\n'
using namespace std; 

int n, m;
int num[500000]; 

bool binarySearch( int target) {
	int left = 0, right = n - 1; 
	
	while (left <= right) {
		int mid = (left + right) / 2; 
		if (num[mid] == target)
			return 1;
		else if (num[mid] > target)
			right = mid - 1;
		else
			left = mid + 1; 
	}
	return 0; 
}

int main() {
	ios_base::sync_with_stdio(false); 
	cout.tie(NULL); 
	cin.tie(NULL); 

	cin >> n; // 숫자 카드 수
	for (int i = 0; i < n; i++) cin >> num[i]; 
	sort(num, num + n);

	cin >> m;
	for (int i = 0; i < m; i++) {
		int target; cin >> target; 
		cout << binarySearch(target) << " "; 
	}
	cout << endl;
	return 0; 
}