🤗 [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]에서 큐와 스택, 데크 내용을 요약, 정리한 게시글입니다.

일렬로 늘어선 자료구조를 표현한 자료 구조.
자료를 넣고 꺼내는 연산을 지원, 특정한 순서로 넣고 특정한 순서로 꺼낼 수 있다는 특징을 가짐.

도입

• 큐: 선입선출
• 스택: 선입후출
• 데크: 스택, 큐 모두 구현 가능

큐와 스택은 각각 넣고 빼는 방향에 따라 푸시와 팝 연산을, 그리고 데크는 앞뒤에서 모두 푸시와 팝 연산을 지원 가능.

구현

연결 리스트를 통한 구현

가장 간단한 방법: 연결 리스트를 사용하는 것
연결 리스트를 이용 → 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 할 수 있기 때문

동적 배열을 이용한 구현

스택의 경우: 한쪽 끝에서만 자료의 추가와 삭제가 일어나므로 동적 배열 가능

큐나 데크: 맨 앞에서 원소 삭제하면 O(n)의 수행 시간. 간단X
→ 동적 배열에서 head와 tail에 유지하면서 맨 앞에서 원소를 pop하면 head를 그 다음 원소를 옮김.

공간 비효율: tail이 배열 마지막 원소까지 도달하면 0번째 공간으로 돌아와서 원소를 저장해 줌(circular buffer)

스택과 큐의 활용

예제: 큐를 이용한 조세푸스 문제의 해법

• 큐의 첫 번째 사람이 나와서 죽고
• 큐의 맨 앞에 있는 사람을 맨 뒤로 보내는 작업을 k-1번 반복

짝이 맞지 않는 괄호(BRACKETS2)

• 모든 괄호는 해당하는 짝이 있어야 합니다. 이때 (는 )와, {는 }와, [는 ]와 짝
  을 이뤄야만 합니다.
• 모든 괄호쌍은 먼저 열린 뒤 닫힙니다.
• 한 괄호 쌍이 다른 괄호쌍과 서로 ‘교차해’ 있으면 안 됩니다. 이 정의에 의하면 [(])는 짝이 맞지 않는 경우입니다.

<<풀이>>

• 닫는 괄호 문자가 들어오면 스택에서 pop해서 직전 여는 괄호 문자와 맞는 짝인 지 검토 후 안 맞으면 no 출력

외계 신호 분석(ITES)

수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@ home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처 리를 거쳐 각 숫자 가 [1，10000] 범위 안에 들어가는 자연수 수열로 주어지는데, 이 전파가 과연 단순한 노이즈인지 아니면 의미 있는 패턴을 가지고 있는지를 파악하고 싶습 니다. 수환이는 전파의 부분 수열 중에 합 이 《인 것이 유독 많다는 사실을 눈치 챘습니다. 부분 수열이란 연속된 수열의 일부를 말합니다. 예를 들어 수열 {1, 4, 2, 1, 4, 3, 1, 6}에서 합이 7인 부분 수열은 다음과 같이 다섯 개입니다. {1, 4, 2}, {4, 2, 1}, {2, 1, 4}, {4, 3} ,{1, 6} 이 부분 수열들은 서로 겹쳐도 된다는 데에 유의합시다.

포가 외계인에게 의미 있는 숫자일까요? 수환이의 가설을 확인하기 위해, 길이 N인 신호 기록이 주어질 때 합 이 《인 부분 수열이 몇 개나 있는지 계산하는 프로그램을 작성하세요.

[입력 생성]

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

• A[0] =1983
• A[i]=(A[i-l]x 214013+2531011)mod2^12

<<풀이>>

온라인 알고리즘: 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아도 계산을 시작할 수 있음.
(예: 삽입 정렬)

head와 tail로 2중 for문 구성.

이때 head-tail 구간의 합이 K를 넘어서는 순간, tail for문에서 break하고 다음 head로 넘어감.

즉, 후보 구간 = 합이 K이상인 가장 짧은 구간(head는 고정), 그리고 아래와 같은 원리로 tail을 직전 후보구간의 tail부터 찾으면 됨.

// 개선된 오프라인 알고리즘
int optimized(const vector<int>& signals, int k) {
	int ret = 0, tail = 0, rangeSum = signals[0];
	for(int head = 0; head < signals.sizeO; ++head) {
	// rangeSum이 k 이상인 최초의 구간을 만날 때까지 tail을 옮긴다. 
		while(rangeSum < k && tail + 1 < signals.size())
			rangeSum += signals[++tail];  
		if(rangeSum = k) ret++;
	// signals[head]는이제 구간에서 빠진다.
		rangeSum -= signals[head]; 
}
return ret;

분할 상환 분석을 이용하면 코드의 Time Complexity는 O(N)이라는 것을 쉽게 알 수 있음.

이제 메모리를 고려해서 온라인 알고리즘을 만들어 보자.

// 온라인 알고리즘 만들기
// 모든 데이터를 미리 생성하지 않고 구간에 새 숫자를 포함시켜야 할 때마다 해당 숫자를 하나씩 생성.
// 필요 없게 된 숫자는 메모리에 저장해 둘 필요 없이 지원버리면 됨.
int countRanges(int k, int n) {
	RNG rng; 
	//신호값을 생성하는 난수 생성기 
	queuec<int> range; //현재 구간에 들어있는 숫자들을 저장하는 큐
	int ret = 0, rangeSum = 0;
	for(int i = 0; i < n; i++) {
		// 구간에 숫자를 추가한다.
		int newSignal = rng.next();
		rangeSum += newSignal;
		range.push(newSignal);
		// 구간의 합이 k를 초과하는 동안 구간에서 숫자를 뺀다
		while(rangeSum > k) {
			rangeSum -= range.front();
			range.pop();
		}
		if(rangeSum — k) ret++;
	}
	return ret;
}

동일한 원리지만, tail을 고정으로 하고 head에서부터 가지고 있던 구간에서 head부터 쳐내면서

K이하의 최대 길이 구간을 구한다.