Optional

[문제] https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net [풀이] 기본 큐 문제 [코드] #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); queue q; int n; cin >> n; while(n--){ string s; cin >> s; if(s == "push") { int n; cin >> n; q.push(n); } ..

[문제] https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net [풀이] 1. 스택을 이용한 방법 최대 넓이를 구하기 위해서 스택의 top에 존재하는 높이 값이 현재 높이값보다 크거나 같을때까지 스택을 탐색하여 최대 넓이를 구한다. 스택에는 (삭제할때의 idx, 높이)를 저장하고, 스택에 저장하면 된다. 주의할 점은 0~n 까지 탐색할 경우 마지막에 넣은 높이의 넓이를 구할수 없으므로, S.em..

[문제] https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net [풀이] 스택에 넣을때 순감소 수열(Ex 10 9 8 ..)이 되도록 넣어야 한다. 중복 되는 경우(Ex 2 2 2)를 고려해야 한다. 1. 스택의 top()보다 지금 값이 큰 경우 순감소 수열이 되어야 하므로, 스택의 second 값인 중복 누적 값을 더하고, top()을 pop 한다. 2. 스택의 top()보다 지금 값이 같은 경우 순감소 수열이 되어야 하므로,..

[문제] https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net [풀이] STL 스택을 이용하는 문제이다. 입력된 정수가 0일 경우에는 가장 최근에 쓴 수를 지우므로, 스택의 empty()를 이용하여, 값이 들어있는 지 확인후, pop() 함수로 삭제하면 된다. 입력된 정수가 0이 아닌 경우에는 원소를 스택에 집어넣기 위해서 push() 함수를 이용하면 된다. 합계 결산은 empty()를 이용하여 값이 있는지 확인하고..

[문제] https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net [풀이] 기본적인 스택 풀이 문제이다. C++ STL 중 하나인 스택의 개념과 사용법을 알아보자. 1. 스택 스택(Stack)은 대표적인 LIFO(Last In First Out) 구조이다. 즉, 제일 마지막에 넣은 데이터가 처음으로 빠져나오는 구조를 말한다. C++ STL 사용법 > 스택 선언 stack 이름으로 스택 선언하기 stack stack; > 스택에 데이터 ..

[문제] https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [유형] 스택 [코드] #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; stack S; vector v; int index = 1; while(n--) { int t; cin >> t; if(index == 1) { S.push({t, index}); v.push..