CS/알고리즘

[알고리즘] 분할 정복 - 선형 시간 선택

nowkoes 2023. 5. 19. 16:32

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

선형 시간 선택

개요

　선형 시간 선택(Linear time selection)은 데이터 관리의 효율성을 극대화하기 위해 컴퓨터 과학에서 도입된 알고리즘이다. 이 알고리즘은 평균적으로 선형 시간 복잡도 O(n)을 통해, 정렬되지 않은 데이터 집합에서 k번 째로 작거나 큰 요소를 신속하게 식별할 수 있다.대규모 데이터 셋에서 중요한 순위를 차지하는 값을 파악해야 하는 경우, 예를 들어 데이터의 중앙값을 추출하는 등의 상황에서, 선형 시간 선택 알고리즘이 매우 효율적이라 할 수 있다.

특징

　선형 시간 선택의 두드러진 특징 중 하나는 그 성능이다. 평균적인 시간 복잡도가 O(n)인 선형 시간 선택은 대량의 데이터를 처리하는 데 있어 매우 효율적이다. 또한, 이 알고리즘은 전체 데이터 집합을 미리 정렬할 필요가 없이 원하는 순위의 요소를 즉시 찾아낼 수 있다는 점에서 큰 장점을 가지고 있다. 추가로, 이 알고리즘은 추가적인 메모리를 요구하지 않는다는 특징을 갖고 있다.

 

　반면, 이 알고리즘이 가지는 한 가지 중요한 제약 사항이 있다. 피벗 원소가 매우 불균형적인 최악의 시나리오에서는 이 알고리즘의 시간 복잡도가 O(n^2)에 이를 수 있다. 이는 이 알고리즘이 데이터 집합의 구조나 특성에 따라 다른 성능을 보일 수 있음을 의미한다.

 

　선형 시간 선택 알고리즘은 퀵선택 알고리즘과 중앙값의 중앙값 알고리즘 등이 있다. 이번 시간에는 중앙값의 중앙값 알고리즘을 구현해보도록 하자. 먼저 이 알고리즘의 작동 순서는 다음과 같다.

 

  1. 입력 벡터 V가 주어지면 여기서 i번째로 작은 원소를 찾으려고 함
  2. 입력 벡터 V를 V1, V2, ... , Vn/5로 분할한다. 각각의 부분 벡터 Vi는 다섯 개의 원소를 갖고 있고, 마지막 Vn/5은 다섯 개 이하의 원소를 가질 수 있음
  3. 각각의 Vi를 정렬
  4. 각각의 Vi에서 중앙값 mi를 구하고, 이를 모아 집합 M을 생성
  5. 집합 M에서 중앙값 q를 찾음
  6. q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할
    1. i = k면 q는 V의 i번 째 원소
    2. i < k면 V = L로 설정하고 0단계로 이동
    3. i > k면 V = R로 설정하고 0단계로 이동

 

단계 1 ~ 5 (벡터를 분할하고 중앙값을 찾는 과정)
단계 6 (벡터를 q를 기준으로 분할하는 과정)

구현

#include <iostream>
#include <vector>

template <typename T>
auto partition(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	auto pivot = *begin;
	auto left = begin + 1;
	auto right = end;

	while (true)
	{
		while (*left <= pivot && left != right)
			left++;

		while (*right >= pivot && left != right)
			right--;


		if (left == right)
			break;
		else
			std::iter_swap(left, right);
	}

	if (pivot > *right)
		std::iter_swap(begin, right);

	return right;
}

template <typename T>
void quick_sort(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	if (std::distance(begin, end) >= 1)
	{
		auto partition_iter = partition<T>(begin, end);

		quick_sort<T>(begin, partition_iter - 1);
		quick_sort<T>(partition_iter, end);
	}
}

　각각의 벡터를 정렬할 정렬 함수 quick_sort() 함수다. 지난 시간에 사용했던 코드를 그대로 가져왔다.

 

template <typename T>
auto find_median(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	quick_sort<T>(begin, end);
	return begin + (std::distance(begin, end) / 2);
}

　중앙값을 찾는 find_median() 함수다. 중앙값을 찾기 전에 quick_sort() 함수를 이용해 정렬해주고, 중앙값의 위치를 갖는 반복자를 반환한다.

 

template <typename T>
auto partition_pivot(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end,
	typename std::vector<T>::iterator pivot)
{
	auto left = begin;
	auto right = end;

	while (true)
	{
		while (*left < *pivot && left != right)
			left++;

		while (*right >= *pivot && left != right)
			right--;

		if (left == right)
			break;

		else
			std::iter_swap(left, right);
	}

	if (*pivot > *right)
		std::iter_swap(pivot, right);

	return right;
}

　피벗 위지 반복자를 인자로 받는 형태의 분할 함수 partition_piviot() 함수다. 피벗 위치는 함수 인자로 주어지므로, 벡터의 시작과 마지막 원소를 가리키는 반복자를 정의한 후, 피벗보다 크거나 작은 원소를 찾아가게 작성하였다.

 

template <typename T>
typename std::vector<T>::iterator linear_time_select(
	typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end,
	size_t i)
{
	auto size = std::distance(begin, end);

	if (size > 0 && i < size)
	{
		auto vi = (size + 4) / 5;
		size_t j = 0;

		std::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));
		}

		auto median = (M.size() == 1) ? M.begin() :
			linear_time_select<T>(M.begin(), M.end() - 1, M.size() / 2);
		auto partion_it = partition_pivot<T>(begin, end, median);
		auto k = std::distance(begin, partion_it) + 1;

		if (i == k)
			return partion_it;

		else if (i < k)
			return linear_time_select<T>(begin, partion_it - 1, i);

		else if (i > k)
			return linear_time_select<T>(partion_it + 1, end, i - k);
	}

		else
			return begin;
}

　선형 시간 검색 알고리즘이다. 다섯 개 원소로 구분하여 만들 부분 벡터의 개수를 계산하고, 각각의 벡터에서 중앙값을 찾아 벡터 M에 저장한다. 그후 Vi의 중앙값으로 구성된 벡터에서 다시 중앙값 q를 찾고, 분할 연산을 적용하여 피벗 q의 위치 k를 찾아 비교하며 재귀적으로 호출하게 작성하였다.

 

int main()
{
	std::vector<int> v1{ 45,1,3,1,2,3,45,5,1,2,44,5,7 };

	std::cout << "Input vector: ";
	for (const auto& val : v1)
		std::cout << val << ' ';
	std::cout << "\n";

	std::cout << "3rd element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 3) << "\n";
	std::cout << "5th element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 5) << "\n";
	std::cout << "11th element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 11) << "\n";
}

출력

　벡터를 정렬하지 않았지만, 원하는 값을 잘 찾아내는 것을 확인할 수 있다.

 

총합본

더보기 
#include <iostream>
#include <vector>

template <typename T>
auto partition(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	auto pivot = *begin;
	auto left = begin + 1;
	auto right = end;

	while (true)
	{
		while (*left <= pivot && left != right)
			left++;

		while (*right >= pivot && left != right)
			right--;


		if (left == right)
			break;
		else
			std::iter_swap(left, right);
	}

	if (pivot > *right)
		std::iter_swap(begin, right);

	return right;
}

template <typename T>
void quick_sort(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	if (std::distance(begin, end) >= 1)
	{
		auto partition_iter = partition<T>(begin, end);

		quick_sort<T>(begin, partition_iter - 1);
		quick_sort<T>(partition_iter, end);
	}
}

template <typename T>
auto find_median(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end)
{
	quick_sort<T>(begin, end);
	return begin + (std::distance(begin, end) / 2);
}

template <typename T>
auto partition_pivot(typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end,
	typename std::vector<T>::iterator pivot)
{
	auto left = begin;
	auto right = end;

	while (true)
	{
		while (*left < *pivot && left != right)
			left++;

		while (*right >= *pivot && left != right)
			right--;

		if (left == right)
			break;

		else
			std::iter_swap(left, right);
	}

	if (*pivot > *right)
		std::iter_swap(pivot, right);

	return right;
}

template <typename T>
typename std::vector<T>::iterator linear_time_select(
	typename std::vector<T>::iterator begin,
	typename std::vector<T>::iterator end,
	size_t i)
{
	auto size = std::distance(begin, end);

	if (size > 0 && i < size)
	{
		auto vi = (size + 4) / 5;
		size_t j = 0;

		std::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));
		}

		auto median = (M.size() == 1) ? M.begin() :
			linear_time_select<T>(M.begin(), M.end() - 1, M.size() / 2);
		auto partion_it = partition_pivot<T>(begin, end, median);
		auto k = std::distance(begin, partion_it) + 1;

		if (i == k)
			return partion_it;

		else if (i < k)
			return linear_time_select<T>(begin, partion_it - 1, i);

		else if (i > k)
			return linear_time_select<T>(partion_it + 1, end, i - k);
	}

		else
			return begin;
}

int main()
{
	std::vector<int> v1{ 45,1,3,1,2,3,45,5,1,2,44,5,7 };

	std::cout << "Input vector: ";
	for (const auto& val : v1)
		std::cout << val << ' ';
	std::cout << "\n";

	std::cout << "3rd element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 3) << "\n";
	std::cout << "5th element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 5) << "\n";
	std::cout << "11th element: " << *linear_time_select<int>(v1.begin(), v1.end() - 1, 11) << "\n";
}

요약

선형 시간 선택
1. 정의: 주어진 벡터에서 정렬을 행하지 않고 k번 째로 큰/작은 원소를 찾는 알고리즘
2. 종류
　- 퀵 선택, 중앙값의 중앙값 알고리즘 등
3. 특징
　a. 평균 O(n) 시간 복잡도
　b. 추가 메모리 요구x
　c. 최악의 경우 O(n^2) -> 피벗이 불균형할 때
반응형
저작자표시 비영리 변경금지

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] 그리디 알고리즘 - 개요 및 최단 작업 우선 스케줄링  (0) 2023.05.22
[알고리즘] 분할 정복 - 맵리듀스  (0) 2023.05.20
[알고리즘] 분할 정복 - 퀵 정렬  (0) 2023.05.16
[알고리즘] 분할 정복 - 병합 정렬  (2) 2023.05.11
[알고리즘] 알고리즘 개요 및 이진 탐색  (0) 2023.05.09

'CS/알고리즘'의 다른글

  • 현재글[알고리즘] 분할 정복 - 선형 시간 선택

관련글

댓글

티스토리툴바