알고스팟 - 외계 신호 분석

문제 : 외계 신호 분석 (난이도 : 中)

 

https://algospot.com/judge/problem/read/ITES

 

 분석

 이 문제의 핵심은 입력단의 크기이다. 모든 입력단을 처리하기에는 너무 큰 것을 알 수 있다.

따라서 이 문제는 온라인 알고리즘(online algorithm)을 사용해야 한다.

 

온라인 알고리즘(online algorithm):

전체 입력이 한 번에 주어지지 않아도 계산을 할 수 있는 알고리즘을 말한다.

예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워 넣는 방법으로 동작하는데, 처음에 모든 원소가 주어지지 않아도 정렬을 시작할 수 있다.

 

오프라인 알고리즘(ofline algorithm):

반면 선택 정렬은 남아 있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 동작하므로, 모든 원소를 알고 있어야 한다.

 

 일단 입력단의 크기를 무시하고 오프라인 알고리즘으로 설계해보자.

그러면 간단히 이중 for문으로 설계할 수 있을 것이다.

// 오프라인 알고리즘 구성

int simple(const vector<int>& signals, int k)
{
	int ret = 0;
	for (int head = 0; head < signals.size(); head++)
	{
		int sum = 0;
		for (int tail = head; tail < signals.size(); tail++)
		{
			// sum은 [head, tail] 구간의 합
			sum += signals[tail];
			if (sum == k) ret++;
			if (sum >= k) break;
		}
	}
	return ret;
}

시간 복잡도를 계산해보면 head에 대한 for문 N번 수행되고, tail에 대한 for문은 최대 min(N, K)번 수행될 수 있다.

따라서 O(NK) 로 가정할 수 있다.

 

 여기서 간단한 방법으로 최적화를 진행할 수 있다.

head가 늘어났을 때 tail이 줄어드는 일이 없다.

만약 head가 늘어났는데 tail이 줄어든다면 이 후보 구간은 이전 구간의 부분 구간이 된다.

따라서 tail을 head위치가 아닌 전 위치부터 시작하면 된다.

// 최적화

int optimized(const vector<int>& signals, int k)
{
	int ret = 0, tail = 0, rangeSum = signals[0];
	for (int head = 0; head < signals.size(); head++)
	{
		// rangSum이 k 이상인 최초 구간 만날때까지 tail을 옮긴다.
		while (rangeSum < k && tail + 1 < signals.size())
			rangeSum += signals[++tail];
		
		if (rangeSum == k) ret++;

		// signals[head]는 구간에서 빠진다.
		rangeSum -= signals[head];
	}
	return ret;
}

위 알고리즘의 시간은 tail이 0~N까지 증가하므로 분할 상환 분석을 이용하면 O(N) 인 것을 알 수 있다.

 

 이제 이것을 온라인 알고리즘으로 바꿔보자. 

head가 증가하고 나면 지나쳐온 숫자들은 저장할 필요가 없다. 우리가 메모리에 저장해야 하는 것은 후보 구간에 포함된 숫자들 뿐이다. 

// 온라인 알고리즘

int countRange(int k, int n)
{
	RNG rng;
	queue<int> range; // 현 구간 내에 숫자들을 저장하는 큐
	int ret = 0, rangeSum = 0;
	for (int i = 0; i < n; i++)
	{
		// 구간 내 숫자 추가
		int newSginal = rng.next();
		rangeSum += newSginal;
		range.push(newSginal);

		// 구간의 합이 k를 초과하면 구간에서 수를 뺀다.
		while (rangeSum > k)
		{
			rangeSum -= range.front();
			range.pop();
		}

		if (rangeSum == k) ret++;
	}
	return ret;
}

 

 구현

※ 선형 합동 난수 생성기(linear congruential random number generator)의 구현을 유의 깊게 봐보자.

// 선형 합동 난수 생성기
struct RNG
{
	unsigned seed;
	RNG() : seed(1983) {}
	unsigned next() {
		unsigned ret = seed;
		seed = ((seed * 214013u) + 2531011u);
		return ret % 10000 + 1;
	}
};

// 오프라인 알고리즘
int simple(const vector<int>& signals, int k)
{
	int ret = 0;
	for (int head = 0; head < signals.size(); head++)
	{
		int sum = 0;
		for (int tail = head; tail < signals.size(); tail++)
		{
			// sum은 [head, tail] 구간의 합
			sum += signals[tail];
			if (sum == k) ret++;
			if (sum >= k) break;
		}
	}
	return ret;
}

// 최적화
int optimized(const vector<int>& signals, int k)
{
	int ret = 0, tail = 0, rangeSum = signals[0];
	for (int head = 0; head < signals.size(); head++)
	{
		// rangSum이 k 이상인 최초 구간 만날때까지 tail을 옮긴다.
		while (rangeSum < k && tail + 1 < signals.size())
			rangeSum += signals[++tail];
		
		if (rangeSum == k) ret++;

		// signals[head]는 구간에서 빠진다.
		rangeSum -= signals[head];
	}
	return ret;
}

// 온라인 알고리즘
int countRange(int k, int n)
{
	RNG rng;
	queue<int> range; // 현 구간 내에 숫자들을 저장하는 큐
	int ret = 0, rangeSum = 0;
	for (int i = 0; i < n; i++)
	{
		// 구간 내 숫자 추가
		int newSginal = rng.next();
		rangeSum += newSginal;
		range.push(newSginal);

		// 구간의 합이 k를 초과하면 구간에서 수를 뺀다.
		while (rangeSum > k)
		{
			rangeSum -= range.front();
			range.pop();
		}

		if (rangeSum == k) ret++;
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		int n, k;
		cin >> k >> n;
		cout << countRange(k, n) << '\n';
	}
	return 0;
}