스택
- 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조
- 위치
- 연산
- push: top 위치에 새 데이터 삽입
- pop: top 위치에 현재 있는 데이터 삭제
- top: top 위치에 현재 있는 데이터 확인
- 관련 알고리즘: DFS, 백트래킹 종류 (후입선출 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통함.)
스택 관련 문제들
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
stack<int> num_sequence;
vector<char> answer;
int num = 1;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
while (num <= a)
{
num_sequence.push(num);
answer.push_back('+');
num++;
}
if (num_sequence.top() == a)
{
num_sequence.pop();
answer.push_back('-');
}
else
{
cout << "NO";
return 0;
}
}
for (int i = 0; i < answer.size(); i++)
cout << answer[i] << '\n';
return 0;
}
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
stack<int> index;
vector<int>A(N, 0);
vector<int>answer(N, 0);
for (int i = 0; i < N; i++)
cin >> A[i];
index.push(0);
for (int i = 1; i < N; i++)
{
while (!index.empty() && A[index.top()] < A[i])
{
answer[index.top()] = A[i];
index.pop();
}
index.push(i);
}
while (!index.empty())
{
answer[index.top()] = -1;
index.pop();
}
for (int i = 0; i < N; i++)
{
cout << answer[i] << ' ';
}
return 0;
}
큐
- 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조
- 위치
- back: 큐에서 가장 끝(뒤)의 데이터를 가리킴
- front: 큐에서 가장 앞의 데이터를 가리킴
- 연산
- push: back 위치에 새 데이터를 삽입
- pop: front 위치에 현재 있는 데이터 삭제
- 관련 알고리즘: BFS
큐 관련 문제들
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
queue<int> card;
for (int i = 1; i <= N; i++)
card.push(i);
while (true)
{
if (card.size() == 1)
break;
card.pop();
if (card.size() == 1)
break;
int k;
k = card.front();
card.pop();
card.push(k);
}
cout << card.front();
return 0;
}
우선순위 큐
우선순위 큐 관련 문제들
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++) //테스트케이스
{
int count = 0;
int n, m, ipt; //문서의 개수, 궁금한 문서의 위치, 중요도
cin >> n >> m;
queue<pair<int, int>> q;
priority_queue<int> pq;
for (int j = 0; j < n; j++)
{
cin >> ipt;
q.push(make_pair(j, ipt)); //q.push({ j, ipt });
pq.push(ipt);
}
while (!q.empty())
{
int index = q.front().first; //q 첫번째의 pair 첫번째 값
int value = q.front().second; //q 두번째의 pair 두번째 값
q.pop(); //첫번째 q 요소 삭제
if (pq.top() == value)
{
pq.pop();
count++;
if (m == index)
{
cout << count << "\n";
break;
}
}
q.push({ index, value });
}
}
}
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct comp
{
bool operator()(int a, int b)
{
if (abs(a) == abs(b))
{
return a > b;
// 더 작은 값에 우선순위를 높게 주겠다는 뜻
}
else
{
return abs(a) > abs(b);
}
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
priority_queue<int, vector<int>, comp> pq;
for (int i = 0; i < N; i++)
{
int a;
cin >> a;
if (a != 0)
{
pq.push(a);
}
else
{
if (pq.empty())
{
cout << 0 << '\n';
}
else
{
cout << pq.top() << '\n';
pq.pop();
}
}
}
return 0;
}
//사용할 구조체
struct s
{
int i;
char c;
//생성자
s(int num, char alpha) : i(num), c(alpha) {}
};
// 비교를 위한 기준
struct cmp
{
bool operator()(s a, s b)
{
// int형의 값이 같을 경우
if (a.i == b.i)
{
// char형의 값이 큰 것이 우선하도록한다.
return a.c < b.c;
}
// int형의 값이 작은 것이 우선하도록한다.
return a.i > b.i;
}
};
int main()
{
//우선순위큐를 선언할때 <자료형, 구현체, 비교연산자> 로 선언한다.
priority_queue <s, vector<s>, cmp> pq;
//생성자를 이용한 구조체 입력
pq.push(s(3, 'a'));
pq.push(s(4, 'b'));
pq.push(s(5, 'y'));
pq.push(s(3, 'z'));
pq.push(s(100, 'z'));
while (!pq.empty())
{
s temp = pq.top();
cout << temp.i << " " << temp.c << endl;
pq.pop();
}
// 출력결과
// 3 z
// 3 a
// 4 b
// 5 y
// 100 z
return 0;
}
