본문 바로가기

분류 전체보기

 (89)
백준 2164번 카드2 https://www.acmicpc.net/problem/2164 아이디어:1. 큐에 1부터 n까지 push()2. 큐 크기가 1이 될 때까지 pop(), push(), pop() #include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; queue Q; for (int i = 1; i 1) { Q.pop(); Q.push(Q.front()); Q.pop(); } cout
백준 10845번 큐 https://www.acmicpc.net/problem/10845 아이디어:1. STL queue의 사용법을 묻는 기본 문제2. 큐가 비어있을 때의 예외처리3. push 입력받고 int tmp; cin >> tmp; 처리하기#include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; string str; queue Q; cin >> n; while (n--) { cin >> str; if (str == "push") { int tmp; cin >> tmp; Q.push(tmp); } else if (str == "pop") { if (!Q.empty..
큐 큐, Queue한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 빼는 자료구조FIFO: First Input First Output 큐의 성질원소의 추가, 제거, 확인이 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가추가는 뒤쪽(rear, tail), 제거는 앞쪽(front, head)에서 이루어짐 원형 큐 Circular Queue선형 큐를 배열로 만들었을 때, pop으로 앞쪽에 빈 공간이 생겨도 원소를 더 채울 수 없다.큐를 원형으로 만들면 앞쪽 빈 공간을 활용할 수 있다. 구현head는 제거하는 앞쪽, tail는 추가하는 뒤쪽#include using namespace std;const int MX = 1000005;int dat[MX];int head = 0, tail = 0..
백준 6549번 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549 아이디어:1. 오름차순을 유지하는 모노톤 스택2. 스택에는 pair 저장3. 결과는 long long형으로 저장 (중간에 int에서 long long으로 변환하거나 stack에 pair 저장)4. 스택에서 pop()할 때마다 top()으로 만들 수 있는 직사각형의 넓이 계산(i - S.top().second) * S.top().first(현재 사각형 위치) - (S.top() 사각형의 최초 등장 위치)5. 마지막에 스택을 비우면서 남은 스택 요소들로 만들 수 있는 직사각형의 넓이 계산(n - S.top().second) * S.top().first(마지막 위치) - (S.top() 사각형의 최초 등장 위치) S.top()은 항상 스택 내 ..
백준 3015번 오아시스 재결합 https://www.acmicpc.net/problem/3015 아이디어:1. 스택의 내림차순 유지2. 같은 키에 대한 처리가 핵심3. 스택에 들어가는 값은 { tmp, cnt } 로 cnt는 "스택 내에서 같은 키를 가진 사람 수"4. 같은 키 n명에 대해 등차수열의 합 n*(n+1)/2 생각해보면 정답 변수 ans는 int형이 아닌 long long형으로 정의해야한다. 추가 예제:7 2 4 1 2 2 5 1 (정답: 10)5 5 5 2 2 5 (정답: 8) 스택에 내림차순 적용하는 방식은 똑같다.cnt는 기본 1이다.내림차순 유지를 위해 pop()을 할 때, (tmp 정답 ans에 top()의 cnt (키 같은 사람 수)를 더해준다.만약 새로 들어온 수와 top()의 키가 같다면 cnt는 그만큼 더..

티스토리툴바