본문 바로가기

분류 전체보기

 (89)
백준 11003번 최솟값 찾기 - 덱 정렬 https://www.acmicpc.net/problem/11003 아이디어:1. 슬라이딩 윈도우라고 생각했을 때, 범위가 i - L + 1 부터 1까지 => 슬라이딩 윈도우의 사이즈가 L2. 덱을 사용해서 덱 내부 정렬하듯이 구현3. (값, 인덱스)로 구성된 Node 사용4. 새 노드가 추가될 때, 덱에서 새 노드의 숫자보다 큰 숫자의 노드는 전부 삭제 (= 모노톤 스택)5. 새 값 추가. 새 값은 무조건 추가된다.6. 덱 안에 있는 노드의 인덱스 범위가 슬라이딩 윈도우의 크기를 벗어나면 (ex. L = 4인데, 덱에 있는 인덱스는 2~6인 경우) 덱의 앞에서부터 노드 제거 덱의 정렬은 모노톤 스택과 동일한 방식이다. pair 사용하는 정갈한 풀이#include #include using namespa..
백준 5430번 AC https://www.acmicpc.net/problem/5430 아이디어:1. [1,2,3,4]의 형태로 입력됐을 때, 덱 안에 1 2 3 4를 순서대로 push_back() 해주는 parse() 함수를 따로 작성int dat라는 임시 값에 char형 숫자가 들어올 때 이전값 * 10을 하고 들어온 숫자에서 48 ('0'에 해당)을 뺀 수를 더한다.2. 덱 안의 값을 [1, 2, 3, 4]의 형태로 출력하는 print() 함수를 따로 작성3. 'R'이 나올 때마다 reverse()를 하면 시간초과에 걸린다. 'R'은 토글 스위치처럼 0 과 1로 처리한다.4. 'R'이 1이면 reverse()된 상태이므로 pop_front()가 아닌 pop_back() 한다.'R'이 0이면 원래대로 pop_front()..
백준 1021번 회전하는 큐 https://www.acmicpc.net/problem/1021 아이디어:1. 덱에 1~n까지 push_back2. 덱에서 tmp의 위치를 찾는게 중요int idx = find(DQ.begin(), DQ.end(), tmp) - DQ.begin()으로 위치를 찾는다.tmp를 가리키는 반복자에서 시작을 가리키는 반복자인 DQ.begin()을 빼서 구한다.3. idx가 DQ의 가운데(DQ.size() / 2)보다 작거나 같다면 앞쪽에 위치하니까 front()를 뒤로 보내준다.4. 아니라면 뒤쪽에 위치하니까 back()을 앞으로 보내준다.5. 이동 할 때마다 ans++ 해서 마지막에 출력 주의사항:이 문제에는 해당하지 않지만1. tmp가 DQ에 없으면 find()는 DQ.end()를 가리키므로 idx가 DQ..
백준 10866번 덱 https://www.acmicpc.net/problem/10866 아이디어:1. STL deque의 사용법을 묻는 기본 문제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, tmp; deque DQ; string str; cin >> n; while (n--) { cin >> str; if (str == "push_front") { cin >> tmp; DQ.push_front(tmp); } else if (str == "push_back") { ..
덱 덱, DequeDouble Ended Queue양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 덱의 성질원소의 추가, 제거, 확인이 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가단, STL deque에서는 인덱스로 원소에 접근 가능 구현head는 앞쪽 포인터, tail은 뒤쪽 + 1 빈공간 포인터덱은 가운데에서 앞/뒤로 모두 늘어나므로 크기를 2 * MX + 1로 지정하고 head와 tail의 초기값으로 MX를 넣어줘야 한다.#include using namespace std;const int MX = 1000005;int dat[2 * MX + 1];int head = MX, tail = MX;void push_front(int x) { dat[--head] = x;}void..

티스토리툴바