돌이 코딩하는 방

이번에 소개할 STL은 Deque이다. Deque 덱 Deque. 간단히 줄여서 dq라고도 한다. 덱은 queue와 stack을 합쳐놓았다고 생각하면 된다. 정확히는 가능한 부분을 더했다고 생각해야 한다. 덱에서는 앞 또는 뒤로 넣고, 앞 또는 뒤로 뺄 수 있다. 즉, 출입의 경우의 수가 4가지가 된다는 것이다. 이는 아래의 그림과 같이 행동한다. 이와 같이 4가지 행동을 모두 할 수 있는 자료구조이다. 그러면 stack이나 queue를 쓸 바에 무조건 deque을 쓰면 되지 않냐고 생각할 수 있다. 사실 맞는 말이다. 하지만 stack이나 queue가 더 익숙하고, 코드가 더 짧기 때문에 (이 이유가 크다) stack이나 queue를 많이 사용을 한다. 위와 같이 생각을 했었으나 조사를 해보니 dequ..

정말 유용한 줄 모르고 정말 늦게까지 쓰고 있지 않았던 자료구조다. priority queue에는 정말 얽힌 사연도 많다. 이 때문에 내가 얼마나 고생을 했는지도 모르겠다. 정말 애증의 관계이다. Prioirty Queue 한국어로는 우선순위 큐라고 불리는 priority queue이다.(줄여서 pq라고도 쓴다) 큐는 큐인데 우선순위가 있는 큐이다. 스택은 마지막에 넣은 것이 가장 먼저 나오고 큐는 가장 먼저 넣은 것이 가장 먼저 나오지만, 우선순위 큐는 기존에 설정이 되어있는 우선순위에 따라서 가장 먼저 나오는 원소가 결정된다. 어떤 상황에서는 집합에서 가장 조건에 부합하는 원소를 찾을 수 있고, 내부는 일종의 항시 정렬된 상태라고 생각하면 편하다. 따라서 삽입 삭제에 시간복잡도가 $O(lgN)$이 걸..

Vector C++을 사용하게 되면 정말 많이 사용하게 되는 자료구조(?)인 벡터이다. 배열을 사용하는 만큼 정말 많이 사용한다. 배열에서 가능한 모든 연산을 할 수 있으며 추가로 몇 가지 연산들을 더 할 수 있다. 하지만 1-based index를 사용하는 입장으로써는 몇 가지 상황이 아니면 그냥 배열을 사용한다. 문법 많이 사용하는 문법 vector v ll 형식의 vector v 생성. (아무것도 안 들어있는 상태) vector v[303030] ll 형식의 vector 로 이루어진 배열 v 생성. v[i] v의 i번째 원소 참조. 이때 v의 크기는 i+1이상이어야 한다. v.push_back(x) v의 마지막에 원소 x 삽입 v.emplace_back(a,b,c) 원래는 구조체등의 다 원소 개체를..

Queue FIFO. First In First Out의 자료구조이다. 즉, 큐에 먼저 들어간 원소가 먼저 빠져 나오게 된다. 즉 아래와 같은 형식으로 자료구조가 원소들을 관리한다는 것이다. 문법 queue q ll 형식의 자료를 담는 큐 q 생성 q.push(x) q의 가장 뒤쪽에 원소 x삽입 q.front() q의 가장 앞에 있는 원소 참조 q.back() q의 가장 뒤에 있는 원소 참조 q.pop() q의 가장 앞에 있는 원소 삭제 q.size() q에 들어있는 원소의 수 반환 q.empty() q에 원소가 없는지(비었는지) 판별 while(!q.empty()) or while(q.size()) q가 빌 때까지. 보통 q의 원소를 하나씩 모두 뺄 때 사용 q1=q2 q1에 그대로 q2를 대입 swa..

서론 STL. Standard Template Library. C++을 위한 라이브러리로 사용자의 편의를 위해서 기본적으로 제공되는 라이브러리이다. 코딩을 함에 있어 STL과는 떼려야 뗄 수 없는 관계이고, STL 사용능력은 곧 코딩 능력과 코딩 속도로 직결되게 된다. 하지만, 나는 STL 활용을 잘 하지 못한다. 일단 제대로 많이 알고 있는 것도 아니고, 별로 익숙하지도 않아서, 사용할 수 있는 각을 잘 보지 못하고, 막상 사용을 한다고 하더라도 기억을 제대로 못해서 꼭 디버깅을 몇 번 해보거나 코딩에 머뭇거림이 굉장히 심해진다. 이는 빠른 속도의 코딩을 요구하는 몇 개의 대회에서의 성적 하락으로 이어졌다. 마침, 조만간 빠른 속도의 코딩을 요구하는 대회가 좀 있고, 한 번쯤은 정리했어야 할 내용이기 ..