[문제해결전략] Chapter 19 큐와 스택, 데크

chellchell·2020년 8월 9일

문제해결전략

목록 보기

11/17

19.6문제: 외계 신호 분석(ID:ITES)

문제

수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000] 범위 안에 들어가는 자연수 수열로 주어지는데, 이 전파가 과연 단순한 노이즈인지 아니면 의미 있는 패턴을 가지고 있는 것인지를 파악하고 싶습니다. 수환이는 전파의 부분 수열 중에 합이 K인 것이 유독 많다는 것을 눈치챘습니다. 부분 수열이란 연속된 수열의 일부를 말합니다. 예를 들어 수열 {1,4,2,1,4,3,1,6} 에서 합이 7 인 부분 수열은 모두 5개 있습니다. {1,4,2} , {4,2,1} , {2,1,4}, {4,3}, {1,6} 이 부분 수열들은 서로 겹쳐도 된다는 데 유의합시다.
K가 외계인에게 의미 있는 숫자일까요? 수환이의 가설을 확인하기 위해, 길이 N인 신호 기록이 주어질 때 합이 K인 부분 수열이 몇 개나 있는지 계산하는 프로그램을 작성하세요.

입력 생성

입력의 크기가 큰 관계로, 이 문제에서는 신호 기록을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.

A[0] = 1983

A[i] = (A[i-1] * 214013 + 2531011) % $2^{32}$
이 때 i(1 <= i <= N)번째 입력 신호는 A[i-1] % 10000 + 1입니다. 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다. 이 규칙에 따르면 첫 5개의 신호는 각각 1984, 8791, 4770, 7665, 3188입니다.

입력

입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C 줄에 각 2개의 정수로 K(1 ≤K≤5,000,000) 과 N(1 ≤ N ≤ 50,000,000) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 첫 N 개의 신호 중 합이 K 인 구간의 수를 출력합니다.

예제 입력
3
8791 20
5265 5000
3578452 5000000
예제 출력
1
4
1049

First Thoughts

i번째부터 그 이후로 하나씩 증가

신호를 생성하는 과정을 생략하고 신호가 이미 주어져 있다고 가정하자. 그리고 그 신호들이 배열에 저장되어있어 i번째 수를 기준으로 i+1번째 수부터 하나씩 더해가는 과정을 반복한다. 그 합을 구하다보면 언젠가는 기준값 K를 넘어가는 시점이 있을 것이다. 그 지점에서 break를 한다.

int sum(int N, int K) {
	int i, j;
	long long total = 0;
	int result = 0;
	for (i = 0; i < N; i++) {
		total= 0;
		for (j = i; j < N; j++) {
			total += A[j];
			if (total == K) {
				result += 1;
			}
			else
				break;
		}
	}
	return result;
}

My Code

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int make_count(int N, int K) {
	int i;
	queue <long long> signal;
	long long a = 1983;
	int sum = 0;
	int result = 0;
	for (int i = 0; i < N; i++) {
		long long r = a % 10000 + 1;
		signal.push(r);
		sum += r;
		
		while (sum > K) {
			sum -= signal.front();
			signal.pop();
		}
		if (sum == K)
			result += 1;
		a = (a * 214013 + 2531011) % (long long)pow(2, 32);
	}
	return result;
}
int main() {
	int C;
	int i;
	int K, N;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> K >> N;
		cout<<make_count(N,K)<<endl;
	}
}

Answer Code

#include <iostream>
#include <queue>
using namespace std;
struct RNG {
	unsigned seed;
	RNG():seed(1983){}
	unsigned next() {
		unsigned ret = seed;
		seed = ((seed * 214013u) + 2531011u);
		return ret % 10000 + 1;
	}
};
int countRanges(int k, int n) {
	RNG rng;
	queue<int> range;
	int ret = 0, rangeSum = 0;
	for (int i = 0; i < n; i++) {
		int newSignal = rng.next();
		rangeSum += newSignal;
		range.push(newSignal);
		while (rangeSum > k) {
			rangeSum -= range.front();
			range.pop();
		}
		if (rangeSum == k)
			ret++;
	}
	return ret;

}
int main() {
	int C;
	int i;
	int n, k;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> k>>n;
		cout << countRanges(k,n) << endl;
	}
}

Difference & Faults

문제 이해

개인적으로 문제에 써져있는 "입력 생성"과정을 이해하는데 애를 먹었다. i번째 신호가 A[i-1]*214013+2531011)% $2^{32}$ 이라는 건지 A[i-1]%10000+1이라는 건지...그래서 예시로 든 5개의 신호를 직접 계산해보니 말그대로 i번째 신호는 A[i-1]%10000+1이었던 것이다. 즉 A에 있는 숫자들을 이용하여 신호를 생성하는 것이다.

또한 부분 수열에 관한 정의인데 앞의 문제에서 풀었던 "최대 증가 부분 수열(ID:LIS)"과 "합친 LIS(ID:JLIS)" 에서는 부분 수열을 '0개 이상의 숫자를 지우고 남은 수열'이라고 정의한다. 근데 이 문제에서의 부분수열은 이어지는 수열로서 삭제는 생각을 안한다. 이 부분에서 오해를 한거 같다.

런타임

앞에 첫 생각대로 작성한 코드를 보면 논리적 오류는 없을 것이 분명하다. 하지만 2중 for문을 사용하니 런타임이 걸린다. 어떻게 해야할까 고민하던 중 이 단원의 제목이 "큐와 스택, 데크"인 점과 앞의 문제 "짝이 맞지 않는 괄호(ID:BRACKETS2)"가 생각났다. 그래서 큐를 이용하여 숫자를 계속 입력받고 동시에 그 합도 함께 계산을 한다. 그 합을 계산하면서 기준 값 K를 넘어가면 큐의 front값을 삭제하도록 하였다.

입력 생성

책의 풀이는 입력을 생성하는 과정을 구조체로 저장하여 구조체 내 함수를 호출하면서 입력하도록 하였다. 나는 모든 과정을 한 함수가 수행하도록 하였다. 참고로 seed를 계산할 때 상수 옆에 붙는 u는 접미사로 unsigned int 임을 의미한다. 아래는 정수 리터럴 접미사를 표로 정리한 것이다.

접미사	자료형
생략	int
l,L	long
u,U	unsigned int
ul,UL	unsigned long
ll, LL	long long
ull, ULL	unsigned long long

Impressions

문제를 풀 때 입력을 받으며 결과를 계산하든 입력을 다 받고 계산을 하든, 그 차이에 대해 주의깊게 생각해본적은 없다. 근데 이런 사소한 방법의 차이가 시간 복잡도에 많은 영향을 준다는 것에 놀랐다. 또한 입력을 직접으로 받지로 그 입력을 생성하는 과정 또한 문제에 포함되어있는것도 신기했다.

Summary

1학기 때 배운 자료구조들을 응용하여 문제를 풀 수 있는 단원이었다. 복습도 되었지만 만약에 내가 이 단원이 큐와 스택에 관한 내용임을 몰랐을 때는 어떻게 했을까라는 의문도 든다. 내가 수강했던 교수님이 큐와 스택을 수업하실 때 면접에서 자주 물어보는 자료구조라고 하였다. 그만큼 이 자료구조를 왜 사용하고 어느 기능이 있는지를 잘 숙지할 줄 알아야한다고 하셨다. 이 단원의 문제들을 다 풀고 보니 수행해야하는 과정을 보면 분명 스택과 큐를 사용하면 효율적이라는 것을 느낄 수 있다.