백준 알고리즘 중급 - 분할정복

Divide & Conquer

분할 정복에 대해 간단하게 정리해보자.

-

* 분할 정복 (Divide & Conquer) : 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 푸는 것.

 - '나눠서 푼다'는 점에서 DP와 같지만, DP는 문제가 겹쳐서 메모를 이용해야 하고, 분할 정복은 문제가 겹치지 않는다.

 

* 이분 탐색 (Binary Search) : 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘. 크기가 N일 때, O(logN).

 - 중간값과 비교해서 범위를 조금씩 좁혀 가면 된다. 예제를 한번 풀어보자.

 - 숫자 카드 (low) : 숫자 카드 중에 구하려는 값이 있는지 판별하는 문제다.

10815번: 숫자 카드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;

bool dnc(int k, int left, int right) {
	while (left <= right) {
		int mid = (left + right) / 2;
		if (a[mid] == k) {
			return true;
		}
		else if (a[mid] < k) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;

	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		a.push_back(t);
	}

	sort(a.begin(), a.end());

	int m;
	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> t;
		b.push_back(t);
	}

	int len = a.size() - 1;
	for (int i = 0; i < m; i++) {
		cout << dnc(b[i], 0, len) << ' ';
	}
	cout << '\n';

	return 0;
}

 - 조건에 오름차순으로 입력된다는 조건이 따로 없다면 무조건 정렬을 먼저 해주고 탐색을 진행한다.

 

* 상한과 하한 (Upper & Lower) : 확실히 개념을 잡고 넘어가자.

 - 상한 : 큰 수 중 첫번째 / 하한 : 같거나 큰수 중 첫번째

 ex ) 1 3 (lb) 3 3 4 (ub) 5 5 5 5 9 9 9 9 : 3의 ub와 lb

      1 3 3 3 4 5 5 5 5 9 (ub, lb) 9 9 9 : 6의 ub와 lb

 - 이 또한 이분 탐색으로 구할 수 있다. 예제 하나 풀어보자.

 - 숫자카드 2 (low) : ub와 lb를 이용해 숫자의 개수를 구하는 문제다.

10816번: 숫자 카드 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;

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

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;

	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		a.push_back(t);
	}

	sort(a.begin(), a.end());

	int m;
	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> t;
		b.push_back(t);
	}

	int len = a.size() - 1;
	for (int i = 0; i < m; i++) {
		cout << upper(b[i], 0, len) - lower(b[i], 0, len) << ' ';
	}
	cout << '\n';

	return 0;
}

 - ub에서 lb를 빼면 수의 개수를 구할 수 있다는 걸 기억해두자.

 - 보통은 STL을 이용해서 많이 사용한다.

 

* 머지 소트 (Merge Sort) : n개를 반씩 나눠서 정렬한 뒤에 다시 합치는 알고리즘이다.

 - 배열 합치기 (mid) : 정렬된 두 배열을 합쳐서 다시 정렬하는 문제다.

11728번: 배열 합치기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
void merge(int start, int end) {
	int mid = (start + end) / 2;
	int i = start, j = mid + 1, k = 0;
	while (i <= mid && j <= end) {
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}
	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];
	for (int i = start; i <= end; i++) {
		a[i] = b[i-start];
	}
}

void mergesort(int start, int end) {
	if (start == end) {
		return;
	}
	int mid = (start + end) / 2;
	mergesort(start, mid);
	mergesort(mid + 1, end);
	merge(start, end);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;

	int t;
	for (int i = 0; i < n + m; i++) {
		cin >> t;
		a.push_back(t);
		b.push_back(0);
	}

	mergesort(0, n + m - 1);

	for (int i = 0; i < n + m; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}

 - 일단 두 배열에 들어갈 수를 한 배열에 몰아 넣고, 반으로 쪼개준다. 정렬된 두 배열이므로 앞자리부터 차례로 비교해서 작은 수를 넣으면 된다. 조건을 만족하지 못 하는 남은 수는 그대로 순서대로 넣어준다. 이를 반복하면 된다.

 

* 퀵 소트 (Quick Sort) : 평균적인 상황에서 최고의 성능을 자랑하는 알고리즘. 최악의 경우는 O(N^2)

 - 어차피 STL 쓸거지만, 원리는 잘 이해해놓고 넘어가자. 예제를 그냥 만들었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a;

int choosePivot(int low, int high) { // 피벗 고르는 함수. 범위 안이면 뭐든 상관 없음.
	return (low + high) / 2;
}

int partition(int low, int high) {
	int pivotIndex = choosePivot(low, high); // 피벗의 위치
	int pivotValue = a[pivotIndex]; // 피벗값
	swap(a[pivotIndex], a[high]); // 피벗을 제일 뒤로 swap
	int storeIndex = low; // 저장할 위치를 지정할 인덱스
	for (int i = low; i < high; i++) {
		if (a[i] < pivotValue) { // 현재 위치의 값이 피벗보다 작으면 
			swap(a[i], a[storeIndex]); 위치 지정 인덱스와 swap
			storeIndex += 1; // 위치 지정 인덱스 이동
		}
	}
	swap(a[storeIndex], a[high]); // 현재 인덱스 값과 맨 뒤의 값 번경
	return storeIndex;
}

void quicksort(int low, int high) {
	if (low < high) {
		int pivot = partition(low, high); // 피벗 설정
		quicksort(low, pivot - 1); // 피벗 앞
		quicksort(pivot + 1, high); // 피벗 뒤
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;

	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		a.push_back(t);
	}

	quicksort(0, a.size() - 1);
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}

- 배열 길이 n을 입력하고 n개만큼 수를 입력하면 퀵 소트를 해주는 알고리즘이다. 주석을 참고해서 헷갈릴 때마다 확인하도록 하자.

-

머지 소트를 제외하고는 모두 STL로 사용 가능하다.

그래도 어떻게 돌아가는지는 알고 있자.

필요할 때마다 찾아보길.

정리 끝.