04 - 2. 선형 시간 선택, 분할 정복 기법 C++ 표준 라이브러리 함수

04 - 1에서 살펴본 분할 정복 알고리즘은 문제를 정확하게 두개의 부분 문제로 나누었다.

그러나 각 단계에서 문제를 두개 이상으로 분할하는 것이 더 유리한 경우도 있다.

이러한 문제 중 하나인 선형 시간 선택(Linear Time Selection)에 대해 알아보도록 하자.

 

예를 들어 정렬되지 않은 원소의 집합 S가 주어졌을 때, 여기서 i번째로 작은 원소를 찾으려 한다.

가장 단순한 해법은 전체 S를 정렬하고, 이 중 i번째 원소를 선택하는 것이다. 이 경우 시간 복잡도는 O(nlogn)이다.

반면, 분할 정복 방법을 사용하면 O(n)의 시간 복잡도로 구할 수 있다.

 

선형 시간 선택

 

a. 입력 벡터 V가 주어지면 여기서 i번째로 작은 원소를 찾으려고 한다.

 

b. 입력 벡터 V를 V1, V2, ... , V(n/5)로 분할한다. 각각의 부분 벡터 Vi는 다섯개의 원소를 가지고 있고, 마지막 V(n/5) 벡터

는 다섯개 이하의 원소를 가질 수 있다.

 

c. 각각의 V(i)를 정렬하고, 중앙값 m(i)로 이루어진 집합 M의 중앙값 q를 찾는다.

 

d. q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할한다.

 

e. L은 q보다 작은 원소만, R은 q보다 큰 원소만 포함하게 된다. L에 (k - 1)개의 원소가 있다고 가정하면,

- i = k인 경우, q는 V의 i번째 원소이다.

- i < k인 경우, V = L로 설정하고 a단계로 이동한다.

- i > k인 경우, V = R로 설정하고 a단계로 이동한다.

 

 

아래 코드에서 linear_time_select() 함수는 입력 벡터 V에 대해 분할 연산을 수행하고, 분할된 부분 벡터 중 하나에 대해서만 재귀적으로 자기 자신을 호출한다. 매번 재귀 호출이 일어날 때마다 벡터의 크기는 적어도 30% 줄어든다.

따라서 이 알고리즘에 의한 재귀 방정식을 풀어 시간 복잡도를 구해보면 O(n)이 된다.

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

// 두 반복자 사이의 중간 값을 찾는 함수
template <typename T>
typename vector<T>::iterator find_median(
	typename vector<T>::iterator begin, 
	typename vector<T>::iterator last
) 
{
	// 정렬
	sort(begin, last);
	
	// 가운데 원소 반복자 반환
	return begin + (distance(begin, last) / 2);
}

// 피벗 위치 반복자를 인자로 받는 형태의 분할 함수
template <typename T>
auto partition_using_given_pivot(
	typename vector<T>::iterator begin, 
	typename vector<T>::iterator end, 
	typename vector<T>::iterator pivot
) 
{
	typename vector<T>::iterator left_iter = begin;
	typename vector<T>::iterator right_iter = end;

	while (true) {
		while (*left_iter < *pivot && left_iter != right_iter) left_iter++;
		while (*right_iter >= *pivot && left_iter != right_iter) right_iter--;

		if (left_iter == right_iter) break;
		else
			iter_swap(left_iter, right_iter);
	}

	if (*pivot > *right_iter) iter_swap(pivot, right_iter);
	
	return right_iter;
}

// 선형 시간 검색 알고리즘
template <typename T>
typename vector<T>::iterator linear_time_select(
	typename vector<T>::iterator begin,
	typename vector<T>::iterator last,
	size_t i
)
{
	auto size = std::distance(begin, last);

	if (size > 0 && i < size) {
		// 다섯개의 원소로 구분하여 만들 부분 벡터 Vi의 개수 계산
		int num_Vi = (size + 4) / 5;
		size_t j = 0;

		// 각각의 Vi에서 중앙값을 찾아 벡터 M에 저장
		vector<T> M;
		for (; j < size / 5; j++) {
			auto b = begin + (j * 5);
			auto l = begin + (j * 5) + 5;

			M.push_back(*find_median<T>(b, l));
		}

		if (j * 5 < size) {
			auto b = begin + (j * 5);
			auto l = begin + (j * 5) + (size % 5);

			M.push_back(*find_median<T>(b, l));
		}

		// Vi의 중앙값으로 구성된 벡터 M에서 다시 중앙값 q를 찾음
		auto med = (M.size() == 1) ? M.begin() : linear_time_select<T>(M.begin(), M.end() - 1, M.size() / 2);

		// 분할 연산을 적용하고 피벗 q의 위치 k를 찾음
		auto partition_iter = partition_using_given_pivot<T>(begin, last, med);
		auto k = std::distance(begin, partition_iter) + 1;

		if (i == k) return partition_iter;
		else if (i < k) return linear_time_select<T>(begin, partition_iter - 1, i);
		else if (i > k) return linear_time_select<T>(partition_iter + 1, last, i - k);
	}
	else
		return begin;
}

// 테스트용 병합 정렬 함수
template <typename T>
vector<T> mg(vector<T>& arr1, vector<T>& arr2) {
	vector<T> merged;

	auto iter1 = arr1.begin();
	auto iter2 = arr2.begin();

	while (iter1 != arr1.end() && iter2 != arr2.end()) {
		if (*iter1 < *iter2) {
			merged.emplace_back(*iter1);
			iter1++;
		}
		else {
			merged.emplace_back(*iter2);
			iter2++;
		}
	}

	if (iter1 != arr1.end()) {
		for (; iter1 != arr1.end(); iter1++)
			merged.emplace_back(*iter1);
	}
	else {
		for (; iter2 != arr2.end(); iter2++)
			merged.emplace_back(*iter2);
	}

	return merged;
}

template <typename T>
vector<T> mg_sort(vector<T> arr) {
	if (arr.size() > 1) {
		auto mid = size_t(arr.size() / 2);
		auto left_half = mg_sort(vector<T>(arr.begin(), arr.begin() + mid));
		auto right_half = mg_sort(vector<T>(arr.begin() + mid, arr.end()));

		return mg<T>(left_half, right_half);
	}

	return arr;
}

void pv(vector<int> v) {
	for (auto i : v) cout << i << " ";
	cout << endl;
}

void run_linear_select_test() {
	vector<int> s1;

	random_device rd;
	mt19937 rand(rd());
	uniform_int_distribution<mt19937::result_type> uniform_dist(1, 1000);

	for (int i = 0; i < 10; i++) s1.push_back(uniform_dist(rand));
	
	cout << "입력 벡터" << endl;
	pv(s1);
	cout << endl;

	cout << "정렬된 벡터" << endl;
	pv(mg_sort(s1));
	cout << endl;

	while (true) {
		size_t s;
		cout << "몇번째? ";
		cin >> s;

		if (s <= 0) break;
		cout << *linear_time_select<int>(s1.begin(), s1.end() - 1, s) << endl;
	}
}

 

 

 

 

---

 

 

분할 정복 기법과 C++ 표준 라이브러리 함수 (algorithm 헤더파일)

C++ 라이브러리는 미리 정의된 다수의 알고리즘 함수를 제공한다.

 

STL 함수	함수 설명
bool std::binary_search(iterator first, iterator last, int val)	이진 검색을 이용하여 컨테이너에서 원소 하나를 찾음
std::search()	컨테이너에서 일련의 원소를 찾음
std::upper_bound()	컨테이너에서 주어진 값보다 큰 원소가 나타나기 시작하는 위치의 반복자 반환
std::lower_bound()	컨테이너에서 주어진 값보다 작은 원소가 나타나기 시작하는 위치의 반복자 반환
std::partition()	분할 연산을 수행하고, 주어진 피벗보다 작은 원소는 피벗 왼쪽으로, 큰 원소는 피벗 오른쪽으로 옮김
std::partition_copy()	분할 연산을 수행하고, 그 결과를 별도의 두 배열로 반환
std::is_partitioned()	주어진 피벗을 기준으로 분할이 되어 있는지 검사
std::stable_partition()	분할 연산을 수행하며, 각 파티션 원소는 원본 순서 유지
std::sort()	컨테이너 원소 정렬
std::stable_sort()	컨테이너 원소를 정렬하되, 서로 순위가 같은 원소에 대해 원본 순서 유지
std::partial_sort()	컨테이너 전체가 아닌 일부 구간에 대해 정렬
std::merge()	두개의 컨테이너를 합친다. 이때 두 컨테이너의 원소 순서는 그대로 유지됨
std::nth_element()	컨테이너에서 n번째로 작은 원소 반환
std:::accumulate()	컨테이너 원소의 누적 합 계산. 이 함수는 다른 외부 함수를 지정하여 누적 합이 아닌 다른 연산을 수행할 수도 있다.
std::transform()	컨테이너와 함수가 주어지면, 컨테이너의 모든 원소에 대해 해당 함수를 적용하여 값을 수정
std::reduce()	지정한 범위의 원소에 대해 리듀스 연산을 수행하고 결과 반환 * std::accumulate() 함수와 유사한 역할을 하지만 병렬 처리를 지원하기 때문에 일반적으로 실행 속도가 더 빠름

 

 

 

---