[Do it! 알고리즘 코딩테스트: Chapter 3] 스택과 큐(Stack and Queue)

 

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

1. 스택(Stack)

 스택(stack)은 삽입과 삭제 연산이 후입선출(LIFO: Last-in First-out)로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.

 

스택의 동작

• push : top 위치에 새로운 데이터를 삽입
• pop : 스택에서 가장 위에 있는 데이터를 삭제(확인도 동시에 하는 경우가 있음)
• peek(top) : 스택의 가장 위에 있는 데이터를 확인
• isEmpty : 스택이 비어있는지 검사

 

 스택은 깊이 우선 탐색(DFS: Depth First Search), BackTracking 종류의 코딩 테스트에 효과적인 자료구조이다. 

 

2. 큐(Queue)

 큐는 선입선출(FIFO: First In First Out) 구조를 가지는 자료구조이다. 즉, 먼저 들어간 데이터가 먼저 나온다는 특징이 있다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.

 

큐의 동작

• back : 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• push : 데이터를 큐의 뒤쪽(Rear)에 추가한다.
• pop : 큐의 앞쪽(Front)에 있는 데이터를 제거한다.
• peek : 큐의 가장 앞에 있는 데이터를 확인한다.
• isEmpty : 큐가 비어있는지 검사한다.

 

 큐는 너비 우선 탐색(BFS: Breadth Fisrt Search)에서 자주 사용하는 자료구조이다.

 

// Baekjoon Online Judge Problem. 1874

#include <iostream>
#include <vector>
using namespace std;

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

	vector<int> v(n, 0);
	vector<int> stack;
	vector<char> answer;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	int i = 0, j = 1;
	
	while (i < n) {
		int target = v[i];

		if (stack.empty()) {
			stack.push_back(j);
			answer.push_back('+');
			j++;
		}
		else {
			if (stack.back() < target) {
				stack.push_back(j);
				answer.push_back('+');
				j++;
			}
			else if (stack.back() > target) {
				cout << "NO";
				return 0;
			}
			else {
				stack.pop_back();
				answer.push_back('-');
				i++;
			}
		}
	}

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

	return 0;
}

 

 

 

// Baekjoon Online Judge Problem. 17298

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int> A(N, 0);
	vector<int> ans(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	stack<int> myStack;
	myStack.push(0);

	for (int i = 1; i < N; i++) {
		
		while (!myStack.empty() && A[myStack.top()] < A[i]) {
			ans[myStack.top()] = A[i];
			myStack.pop();
		}
		myStack.push(i);
	}
	while (!myStack.empty()) {
		ans[myStack.top()] = -1;
		myStack.pop();
	}

	for (int i = 0; i < N; i++) {
		cout << ans[i] << ' ';
	}

	return 0;
}

 

 스택의 후입선출이라는 독특한 성질이 종종 시간 복잡도를 줄이거나 특정한 문제의 조건을 손쉽게 해결하는 경우가 있다. 이번 문제에서는 스택에 값을 넣는 것이 아니라 index를 넣는것이 핵심이었다. 스택에 새로 들어오는 수와 top에 존재하는 수를 서로 비교하고, 마지막에 stack에 남아있는 index들을 한꺼번에 정리하였다. 

 while문을 이용해 top이 새로 들어오는 수보다 작다면 반복해서 비교하도록 구현하였다. 

 

// Baekjoon Online Judge Problem. 2164
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	queue<int> myQueue;

	for (int i = 1; i <= N; i++) {
		myQueue.push(i);
	}

	while (myQueue.size() != 1) {
		myQueue.pop();
		myQueue.push(myQueue.front());
		myQueue.pop();
	}

	cout << myQueue.front();

	return 0;

}

 

 

// Baekjoon Online Judge Problem. 2164
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

struct compare {
	bool operator()(int a, int b) {
		
		if (abs(a) == abs(b)) {
			return a > b;
		}
		else {
			return abs(a) > abs(b);
		}
	}
};
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, x;
	cin >> N;
	priority_queue<int, vector<int>, compare> myQueue;

	for (int i = 0; i < N; i++) {
		cin >> x;

		if (x == 0) {
			if (myQueue.empty()) {
				cout << '0' << '\n';
			}
			else {
				cout << myQueue.top() << '\n';
				myQueue.pop();
			}
		}
		else {
			myQueue.push(x);
		}
	}
	return 0;
}

 

 우선순위 큐(priority_queue)는 우선순위(priority)에 따라 요소가 정렬되는 특수한 형태의 큐이다. 일반적인 큐(queue)는 FIFO(First-In-First-Out, 먼저 들어온 요소가 먼저 나감) 방식으로 동작하지만, 우선순위 큐(priority queue)는 요소가 들어오면 우선순위를 기준으로 자동 정렬되며, 가장 높은(혹은 낮은) 우선순위를 가진 요소가 먼저 나간다.

 

우선순위 큐(priority_queue)는 기본적으로 최댓값이 먼저 나오는 최대 힙(Max Heap)으로 동작하지만, 사용자가 직접 우선순위를 원하는 기준으로 정할 수 있다. 우선순위를 정하는 대표적인 방법은 구조체(struct), 람다(lambda)가 있다. 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main() { // 우선순위 큐 선언 방법

	priority_queue<int> myQueue; // 기본 우선순위 큐(내림차순 정렬)
    priority_queue<int, vector<int>, greater<int>> myQueue; // 변형 우선순위 큐(오름차순 정렬)
    priority_queue<int, vector<int>, struct_name> myQueue;  // Struct로 우선순위를 설정한 경우
    return 0;
}