알고리즘 문제 해결 전략2 19장 큐와 스택, 데크 (2)

19.4 문제:짝이 맞지 않는 괄호

모든 괄호는 짝이 있어야 함.

모든 괄호 쌍은 먼저 열린 뒤 닫힘

한 괄호 쌍이 다른 괄호쌍과 서로 교차해 있으면 안됨.

 

19.5 풀이:짝이 맞지 않는 괄호

두 가지 예외를 추가로 처리하는 것을 눈여겨봅시다. 스택에서 여는 괄호를 꺼내려고 하는데 스택이 비어 있는 경우, 그리고 전부 다 잘 처리하고 마지막에 열린 괄호가 남아 있는지 확인하는 것 모두 이 문제를 처음 작성하는 사람이 간과하기 쉬운 부분임. 

 

bool wellMAtched(const string& formula) {
	const string opening("({["), closing(")}]");
	stack<char> openStack;
	for (int i = 0; i < formula.size(); ++i)
	{
		if (opening.find(formula[i]) != -1)
			openStack.push(formula[i]);
		else {
			if (openStack.empty()) return false;
			if (opening.find(openStack.top()) != closing.find(formula[i]))
				return false;
			openStack.pop();
		}
	}
	return openStack.empty();
}

 

19.6 문제:외계 신호 분석

부분 수열이란 연속된 수열의 일부를 말함. 이 부분 수열들은 서로 겹쳐도 된다는데 유의함. 

 

19.7 풀이:외계 신호 분석

입력의 크기부터 문제임. 따라서 우리는 모든 키를 메모리에 생성해 올려놓지 않고 이 중 일부만을 사용하는 온라인 알고리즘을 작성해야 함. 오프라인 알고리즘이란 입력 전체를 이미 가지고 있다고 가정하고 동작하는 알고리즘을 말함. 

 

오프라인 알고리즘 만들기

모든 부분 구간을 검사하면서 합이 K인 것을 찾는 것임. 제약 조건을 무시하고 알고리즘을 설계한 뒤 이것을 점진적으로 최적화. tail에 대한 for문은 최대 min(N,K)번 수행될 수 있음. 대부분의 경우 K<=N 이라고 가정하면 전체 시간 복잡도는 O(NK)가 됨. 알고리즘이 하는 일을 정확히 이해하고 최적화하면 이것을 선형 시간 알고리즘으로 바꿀 수 있음. 이 구간들만이 답이 될 가능성이 있다는 의미에서, 이 구간들을 후보 구간들이라고 부름. 

 

최적화를 하면 O(N)임

int optimized(const vector<int>& signals, int k) {
	int ret = 0, tail = 0, rangeSum = signals[0];
	for (int head = 0; head < signals.size(); ++head) {
		while (rangeSum < k && tail + 1 < signals.size())
			rangeSum += signals[++tail];
		if (rangeSum == k) ret++;
		rangeSum -= signals[head];
	}
	return ret;
}

 

온라인 알고리즘 만들기

구간에 새 숫자를 포함시켜야 할 때마다 해당 숫자를 하나씩 생성함. 필요 없게 된 숫자는 메모리에 저장해 둘 필요 없이 지워버리면 됨. head가 증가하고 나면 우리가 지나쳐온 숫자들은 더 이상 고려할 필요가 없으므로, 저장할 필요가 없음. 결과적으로 우리는 각 tail에 대해 합이 K이하가 되는 가장 긴 구간을 찾는 셈임. 이 문제에서 모든 신호는 양수이므로 큐의 크기는 항상 K 이하이고, 결과적으로 적은 양의 메모리만을 쓰고 이 문제를 해결할 수 있음.

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;
}

 

신호의 생성

난수 생성기. 이런 코드를 작성할 때 유의할 점은 계산 과정에서 오버플로우가 발생하는 경우를 잘 처리하는 것임.