돌이 코딩하는 방

오프라인 다이나믹 커넥티비티 (offline dynamic connectivity) 1년전에 배우고 최근에 복습한 알고리즘. 이번 글에서는 오프라인 다이나믹 커넥티비티라는 알고리즘에 대해서 다뤄보려고 한다. 이 글에서 앞으로 odc 라고 줄여쓰기도 할 것 같다. When? 어떤 문제를 풀기 위해 쓰느냐. life가 있는 변화들과 질문들이 쿼리로 들어왔을 때 사용한다. 문제 www.acmicpc.net/problem/16911를 보자. 각 간선들은 연결을 했다가 일정 시점 이후 사라진다. 또한, 중간에 어떤 두 점의 연결성을 물어보는 쿼리들이 주어진다. 이런 형태의 변화되는 선분과 두 점간의 연결성을 물어보는 문제가 대표적인 odc를 쓰는 문제이다. 위에서 소개한 문제를 odc로 푸는 과정을 소개할 예정이..

이번에 소개할 내용은 Persistent Segment Tree이다. Segment Tree 의 한 종류로 굉장히 특별한 부분을 맡고 있다. Persistent Segment Tree의 사용 이 문제를 보자. www.acmicpc.net/problem/16978 물론 오프라인이기 때문에 쓸 수 있는 테크닉으로 풀 수도 있지만, 이 문제가 주어진 쿼리를 순서대로 대답해야하는 온라인 문제라고 생각을 해보자. 일단은 세그먼트 트리를 사용할 것이다. 그런데 우리는 임의의 k에 대해서 k번째 쿼리까지만 의해서만 바뀐 그 시점의 세그먼트 트리를 알고 싶다. 가장 직관적인 방법은 모든 k에 대한 세그트리의 상황을 저장해 놓는 것이다. 하지만 O(QN)의 시간과 공간 복잡도가 필요할 것이고, 당연히 Q와 N은 1000..

이번에 소개할 Segment Tree 심화는 HLD이다. 원래는 Euler Tour 이후에 바로 글을 작성했어야 하는데, 대회 준비등의 이유로 다른 내용 관련 글을 계속 쓰다 보니까 계속 미뤄져서 이제서야 글을 쓰게 되었다. 사전 지식 (먼저 읽고 와야하는 글) stonejjun.tistory.com/103 세그 먼트 트리 - euler tour tree 설명글 What is HLD? 그러면 본격적으로 HLD는 무엇일까? HLD는 일단 Heavy - Light Decomposition의 약자이다. 무거운거 - 가벼운거 분해. 즉 Decomposition인데 Heavy Groupr과 Light Group으로 분리한다는 것이다. 그러면 여기서 좀 세부적으로 알아야 할 사항이 생긴다. 1. 뭐를 분리하는 것인..

이 글을 쓰게 된 동기는 굉장히 재미있다. 증명을 원하시는 분이 있었고 누군가가 내 글을 링크해주신 것을 알게 되었지만 그 글에서는 증명이 없었고, 그래서 관심을 가지게 되었다. 어느 정도 생각해본 결과 대충 증명이 된 것 같아서 일단은 빠르게 글을 써보려고 한다. 따라서 증명이 완벽하지 않을 수도 있으며 뇌피셜일 수도, 많이 생략했을 수도 있다. 하지만 오히려 직관적으로 받아들여질 수도 있다. 댓글로 비판과 지적은 언제나 환영한다.이 글을 읽기 전에...로테이팅 캘리퍼스 설명글 stonejjun.tistory.com/42본인은 설명을 굉장히 못하기 때문에 어쩔 수 없이 설명하려면 코드와 함께 설명하는 수밖에 없을 것 같다. 위 글의 맨 마지막에 코드가 있고, 증명과정에서 그 코드를 언급을 하게 될 것 ..

이번에는 자료구조의 성격을 띄고 있는 STL이 아닌 함수의 성질(?)을 띄고 있는 STL에 대해서 말하려고 한다. 바로 lower_bound와 upper_bound이다. lower_bound를 확실히 정리하려는 이유는 이상, 이하, 초과, 다음이 맨날 햇갈려서 항상 한번 긴가민가 하면서 코딩해보고 수정을 하기 때문이다. 엄청나게 시간소모를 하는것은 아니지만, 답이 틀릴때 마다 lower_bound에 확신이 없어 한 번 검토해야하는 것은 확실히 스트레스이다. ※ 배열은 1-base 기준입니다. lower_bound lower_bound는 범위내의 정렬된 자료들 내에서 원하는 원소보다 같거나 큰 첫 번째 위치를 찾아준다. 예를 들어서 벡터에 2 2 4 5 7 9가 있고, 이 벡터 전체에 대해서 7을 기준으로..

이번에 소개할 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 활용을 잘 하지 못한다. 일단 제대로 많이 알고 있는 것도 아니고, 별로 익숙하지도 않아서, 사용할 수 있는 각을 잘 보지 못하고, 막상 사용을 한다고 하더라도 기억을 제대로 못해서 꼭 디버깅을 몇 번 해보거나 코딩에 머뭇거림이 굉장히 심해진다. 이는 빠른 속도의 코딩을 요구하는 몇 개의 대회에서의 성적 하락으로 이어졌다. 마침, 조만간 빠른 속도의 코딩을 요구하는 대회가 좀 있고, 한 번쯤은 정리했어야 할 내용이기 ..