[알고스팟] 외계 신호 분석(ITES)

[알고스팟] 외계 신호 분석(ITES)

목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 외계 신호 분석(ITES)를 풀어보자

문제 URL

풀이

외계 신호 분석(ITES) 문제는 큐와 온라인 알고리즘을 이용하여 푸는 문제입니다. 온라인 알고리즘이란 무엇이냐. 오프라인 알고리즘의 경우 입력의 값이 모두 나왔을 때, 알고리즘을 일괄적으로 적용하여 문제를 푸는 것을 말하고, 온라인 알고리즘은 입력이 생성될 때마다, 알고리즘을 적용하여 문제를 푸는 방식을 말합니다. 일반적으로 예를 들어서 어떤 배열의 누적합을 구하는 경우, 이미 만들어져 있는 배열을 토대로 다음과 같이 누적합 만들 수 있습니다.

arr = [1, 2, 3]
acc = 1 + 2 + 3 = 6

그런데, 이렇게 생각할 수도 있습니다. 배열의 원소가 어떤 특정한 객체에 의해서 반복 호출 마다, 1, 2, 3, 4.... 이런식으로 출력 값을 반환하게 만든 후에, 우리는 누적합을 다음과 같이 구할 수 있습니다.

for i in 0 .. 3:
    e = rng.next()
    acc += e

이 경우 생성기를 호출하여 그 때마다, acc의 누적합을 계산하는 것이지요. 첫 번째 경우는 입력 arr을 만들어놓은 상태에서 알고리즘을 적용하여 푸는 오프라인 알고리즘의 예이고, 두 번째 경우가 출력 스트림에 의해서 그 때 그 때 알고리즘을 적용하여 푸는 온라인 알고리즘의 예입니다. 

이 문제 역시 신호를 K만큼 생성해서, 배열로 저장한 후 각 부분합을 구해 N과 같은 부분합이 몇 개인지 구하는 방식으로 풀 수 있습니다. 다만, 제한 시간 내에는 도저히 풀 수가 없기 때문에 각 신호가 생성될 때마다, 부분합을 구해서 N과 같은 부분합이 몇 개 있는지 찾아내는 온라인 알고리즘으로 구해야 합니다. 이제 우리가 생각해야 할 부분은 바로 신호 생성기와 부분합 온라인 알고리즘 적용하는 공식이지요.

먼저 신호 생성기를 만들 때 고려해야 할 부분은 다음과 같습니다.

1. A[0] = 1983
2. A[i] = (A[i-1] * 214013 + 2531011) % (2^32)
3. out = A[i-1] % 10000 + 1

이제 처음에 seed를 주어서, next()가 호출될 때 마다, 2번으로 해당 seed를 업데이트하고, out을 반환시키는 생성기를 만들면 됩니다. 신호 생성기 코드는 다음과 같습니다.

struct RNG {
	unsigned signal;

	RNG() : signal(1983u) {}
	unsigned next() {
		unsigned out = signal % 10000u + 1;
		signal = (signal * 214013u +2531011u);
		return out;
	}
};

next()의 signal을 생성하는 부분의 코드는 c++의 unsinged 타입의 지원을 받아서 간결하게 작성한 것입니다. unsiged(unsigned int)는 0~2^32-1 만큼 표현하기 떄문에, 2^32 만큼 나머지 연산을 해줄 필요가 없지요.  Java, C# 같이 signed 타입만 지원하는 경우는 int의 범위보다 큰 long으로 지정하고 pow(2, 32) 만큼 나머지 연산을 수행해 주어야 합니다. 다음 처럼 말이죠.(실제로 돌려보지는 않아서, 맞는지는 장담할 수 없습니다만...)

class RNG{
    private long siganl;
    public RNG(){
        this.signal = 1983l;
    }
    public long next() {
        long out = signal % 10000 + 1;
        signal = (signal * 214013 + 2531011) % (long)Math.pow(2, 32);
        return out;
    }
}

이제 부분합을 온라인 알고리즘을 이용하여 만들어봅시다. 알고리즘의 뼈대는 다음과 같습니다.

1. K만큼 다음을 순회 합니다.
   1. 신호 생성기로부터 다음 신호를 받습니다.
   2. 부분합을 저장하는 rangeSum에 signal 값을 더해줍니다.
   3. 큐에 signal을 추가합니다.
   4. 만약 rangeSum이 N보다 크다면 다음을 반복합니다.
      1. 큐의 첫 데이터를 rangeSum에 빼줍니다.
      2. 큐에서 첫 데이터를 삭제합니다.
   5. 4번을 거치고 rangeSum == N 이라면, 개수를 세어 줍니다.

문제에서, 첫 5개의 신호는 1984, 8791, 4770, 7665, 3188 이라고 정의되어 있습니다. 이것을 토대로 8791이 몇 개인지 저 알고리즘으로 세보도록 하죠.

입력

N = 8791, K = 5

첫 번째 신호 생성

signal = rng.next() //1984
rangeSum = 1984(0 + signal)
q = [1984]

첫 번째 신호때는, rangeSum보다 작기 때문에, 4번을 거치지 않습니다. 역시 rangeSum도 N과 같지 않기 때문에 개수는 세지 않지요.

두 번째 신호 생성

signal = rng.next() //8791
rangeSum = 10775(1984 + 8791)
q = [1984, 8791]

이제 rangeSum 이 N보다 크기 떄문에, 첫 번째 신호를 빼주고, 그것을 rangeSum에 적용합니다.

rangeSum -= q.front() (10775 - 1984 = 8791)
q = [8791]

이제 다시 N보다는 크지 않기 때문에 더 이상 진행하지 않고 N과 비교합니다. 이 때, N과 같기 떄문에 개수를 세어줍니다. 이 후에는 각 K번째 신호 생성에 대해서 동작만 정의하도록 하겠습니다. 왜 이렇게 되는지 한 번 스스로 생각해보는 시간을 가지면 더 좋을 것 같습니다.

세 번째 신호 생성

signal = rng.next() //4770
rangeSum = 13561(8791 + 4770)
q = [8791, 4770]

rangeSum -= q.front() (13561 - 8791 = 4770)
q = [4770]

네 번째 신호 생성

signal = rng.next() //7665
rangeSum = 12435(4770 + 7665)
q = [4770, 7665]

rangeSum -= q.front() (12435 - 4770 = 7655)
q = [7665]

다섯 번째 신호 생성

signal = rng.next() //3188
rangeSum = 10783(7665 + 3188)
q = [7665, 3188]

rangeSum -= q.front() (10783 - 7665 = 3188)
q = [3188]

결국 이 5개의 신호 중 부분합이 8791인 것은 1개 있다고 볼 수 있지요. 실제로 첫 번째 입력 N=8791, K=20 일 때 조차(우리가 했던 예제 입력은 N=8791, K=5입니다.) 출력은 1밖에 나오지 않습니다. 입력을 모두 만들어놓고, 문제를 푸는 것이 효율적인가 아니면 입력이 생성될 때마다, 문제를 푸는 것이 효율적인 것인가에 대해서는 문제마다 다르겠지만, 제한 시간이 적고 입력이 크다면 온라인 알고리즘을 이용하는 것을 추천드립니다. 다음은 코드입니다.

코드

#include<iostream>
#include<queue>

using namespace std;

struct RNG {
	unsigned signal;
        //문제 입력에 따라 초기값을 1983 적용
	RNG() : signal(1983u) {}
	unsigned next() {
                //현재 신호를 10000으로 나눈 나머지에 1을 더해서 출력신호 생성
		unsigned out = signal % 10000u + 1;
                //다음 신호 생성
		signal = (signal * 214013u +2531011u);
		return out;
	}
};

int solution(unsigned N, unsigned K) {
	int answer = 0;
	unsigned rangeSum = 0;
	RNG rng;
	queue<int> q;
        //K만큼 순회
	for (int i = 0; i < K; i++) {
                //1. 신호 생성
		auto signal = rng.next();
                //2. 부분합 누적
		rangeSum += signal;
                //3. 큐에도 신호 저장
		q.push(signal);
                //4. 현재 부분합이 N보다 크다면 다음을 반복
		while (rangeSum > N) {
                        //현재 큐의 가장 첫 신호를 부분합에서 제거
			rangeSum -= q.front();
                        //큐에서 제거
			q.pop();
		}
                //5. 4번을 거친 후, 현재 부분합이 N과 같다면 개수 세어줌
		if (rangeSum == N)
			answer += 1;
	}
	
	return answer;
}


int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		unsigned N, K;
		cin >> N >> K;
		cout << solution(N, K) << endl;
	}
	return 0;
}