BOJ 백준 16455 : K번째 수 찾는 함수

시작하면서

　이번 문제는 Medians and Order Statistics 문제이다. Introduction To Algorithms 책으로 개념 공부를 했고, 해당 문제를 이 문제에 적용해보고자 한다. (개념 공부 링크)

BOJ 16455 - K번째 수 찾는 함수

​

개념

　개념에 대해 정리한 링크로 대체한다.

중앙값과 순서 통계량(Medians and Order Statistics)

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 3가지이다.

• N : 배열의 크기

• K : 찾아야 하는 수의 기준

• 시간 제한 : 0.1초

　이 문제에서 중요한 점은 “시간 제한”이다. 최대 5,000,000 크기의 배열이므로 일반적인 정렬 알고리즘을 사용해서 O(nlogn)의 복잡도로 문제를 해결하면 예상되는 시간은 다음과 같다.

• 기준 : 1초당 1억개의 연산을 한다고 가정
• log(5000000) = 6.6989700043360188047862611052755‬

이렇게 기준을 잡았을 때 O(nlogn) = O(500000 * 6.6989…‬) = 33,494,850.0216800940239… = 약 0.3초가 되므로 시간 제한을 초과하게 된다고 예상할 수 있다.

​

　공부한 Quick Selection은 시간 복잡도가 O(n)이므로 O(5000000) = 약 0.05초가 되므로 시간 제한에 걸리지 않는다고 예상할 수 있다.

​

문제 아이디어

　개념 공부했던 내용을 바탕으로 알고리즘을 구현해서 진행하려고 한다. (개념 공부 링크 참조)

​

해결

#include <iostream>
#include <vector>

void swap(int* a, int* b);
int RandomizedSelect(std::vector<int>& v, int p, int r, int i);
int RandomizedPartition(std::vector<int>& v, int p, int r);
int Partition(std::vector<int>& v, int p, int r);

int kth(std::vector<int>& a, int k)
{
	int ans = 0;

	ans = RandomizedSelect(a, 0, a.size() - 1, k);

	return ans;
}

void swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

int RandomizedSelect(std::vector<int>& v, int p, int r, int i)
{
	if (p == r)
	{
		return v[p];
	}

	int q = RandomizedPartition(v, p, r);
	int k = q - p + 1;

	if (i == k)
	{
		return v[q];
	}
	else if (i < k)
	{
		return RandomizedSelect(v, p, q - 1, i);
	}
	else
	{
		return RandomizedSelect(v, q + 1, r, i - k);
	}
}

int RandomizedPartition(std::vector<int>& v, int p, int r)
{
	int i = rand() % (r - p + 1) + p;
	swap(&v[r], &v[i]);
	return Partition(v, p, r);
}

int Partition(std::vector<int>& v, int p, int r)
{
	int x = v[r];
	int i = p - 1;

	for (int j = p; j < r; j++)
	{
		if (v[j] <= x)
		{
			i = i + 1;
			swap(&v[i], &v[j]);
		}
	}

	swap(&v[i + 1], &v[r]);

	return i + 1;
}

​

마치며

　원래는 K번째 수 문제를 풀려고 했었다. 하지만 해당 문제는 정렬을 여러번 진행해야해서 개념의 취지와 맞지 않았다.

Quick Selection은 N이 굉장히 크고, 접근하려는 빈도가 낮을 때 사용하는 것이 좋아보인다. (정렬되지 않은 배열에서 K번째 크거나 작은 수 찾기)