일전에 Coder's High 2016에 전갈 그래프에 대한 문제를 출제한 적이 있었다. 문제 전갈 그래프에 대한 이론적 뒷배경에 대해서는 위키백과 참고. 개인적으로 꽤 애착이 가는 문제인데, 사실 저 문제를 general case에서 해결하는 방법은 오랫동안 모르고 있었다. 고민을 했는데 못 풀고 결국은 관련 자료를 봤다. 재미있는 알고리즘이여서 공유하려고 한다. 그래프의 모든 정점의 degree에 대해서 생각을 해보자. 가시의 degree는 1이고, 꼬리의 degree는 2이고, 몸통의 degree는 n-2이고, 나머지 정점의 degree는 1 ~ n-3이다. 이제 아무 정점이나 잡은 후, degree에 따라서 케이스를 나누자. d = 1, d = 2, d = n-2일 경우에는 몇가지 케이스를 해결하..
[2015/07/24 MCMF 보강] [2016/10/03. 옛날에 썼던 글이라 내용을 대폭 보강해서 다시 올린다. 이 글은 "정리하는" 개념의 글이니, 문제나 알고리즘에 대한 구체적인 설명은 따로 찾길 바란다.] [2016/10/14 잡설을 추리고 증명 관련 부분을 개별 글로 뺐다. 증명 뿐만 아니라 "답을 출력하는" 일이 필요하다면 해당 글 참고] 유량(flow) 관련 문제는 대부분 유량을 흘릴 수 있는 경로를 찾고 그 경로에 유량을 보내줌으로써 해결한다. 비슷비슷해서 난 별로 차이가 없는 줄 알았는데 얼마전 DFS로 maxflow의 증가경로를 찾으면 안된다는 얘기를 듣고 멘붕함. 이 기회를 통해서 정리하려 한다. 여담으로, 프로그래밍 콘테스트 챌린징의 네트워크 유량 부분에 굉장히 중요하고 쉽게 배우..
푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. ONTAK2010. Garden https://www.acmicpc.net/problem/8468 쉽게 생각할 수 있는 아이디어는 N^2개의 행을 잡고, 행 각각에서 교집합을 잡아서 O(N) 루프를 돌리는 것이다. N^3의 끔찍한 시간 복잡도를 가지기에 여기서 포기하기 쉽지만, 놀랍게도 sqrt decomposition을 통해서 큰 차이 없이 N^1.5 정도에 풀 수 있다. 행 R에 대해서, Xi == R을 만족하는 i의 개수가 N^0.5 이상일 경우 heavy row라 하고, 아닐 경우 light row라고 하자. 두가지 방법으로 문제를 해결한다. * 두 행 쌍 중 하나라도 light row일 때를 세주자. light row를 하나 잡고, 고를 수 있는..
다음과 같은 참고 자료들이 있으니 같이 보자. http://web.stanford.edu/class/cs97si/suffix-array.pdf http://web.stanford.edu/class/cs97si/10-string-algorithms.pdf http://blog.myungwoo.kr/57 http://m.blog.naver.com/dark\_\_nebula/220419358547 Suffix Array는 문자열과 부분문자열을 가지고 놀 수 있는 자료구조이다. 이름만 보면 도대체 어디에 쓰는 것인지 잘 이해도 안 가고 왜 배우는 지도 알 수 없을 것이다. 일단, Suffix Array를 통해서 쉽게 풀 수 있는 문제 몇가지를 나열하자면 : * 길이 |S|의 스트링 하나와, Q개의 길이 Ti의 ..
옛날부터 모아오던 문제집인데 이제서야 정리... 대부분 IOI 합숙교육때 봤던 문제들이다. koistudy 1534. 369 마스터http://koistudy.net/?mid=prob_page&NO=1534 수의 개수가 10^8개이다. 단순한 알고리즘으로는 10^8 * lg(10^8) / lg(10) 정도라 아마 TLE가 날 것이다. 하지만 루프가 단순하면 10^8 정도는 무난하게 돌릴 수 있을 테니, 각각의 숫자를 아주 빠르게 판별할 수 있으면 괜찮다.여기서 약간의 전처리를 통해서 판별을 아주 빠르게 할 수 있는데, 100000 미만의 i에 대해서, 해당 수가 369 수인지를 전처리 해두면, 10^10 크기의 수 X는, X / 10^5가 369 수거나 X % 10^5가 369 수이면 369 수이다. 이..
http://acm.hdu.edu.cn/showproblem.php?pid=5306 세 종류의 쿼리를 지원하는 자료구조를 설계하는 문제이다. O((N + Q)lgN)에 해야 한다. * 1. 구간 [L, R]에 a[i] = min(a[i], V) 대입 * 2. 구간 최댓값 * 3. 구간 합 보통 이러한 문제들은 세그먼트 트리에 익숙하면 쉽게 풀 수 있고, 실제로 2번 쿼리까지는 쉬운 문제지만, 이 문제는 3번 쿼리 때문에 굉장히 어려운 문제가 되었다.해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다. 먼저 이 값들을 제대로 관리했다면,..
그래프 이론에서 Dynamic Connectivity Problem은, * 1. 정점 u, v를 잇는 간선 추가 * 2. 정점 u, v를 잇는 간선 제거 (이미 있다고 치자.) * 3. 그래프 상에서 두 정점이 연결되어 있는지 체크와 같은 질의가 주어졌을 때, 이러한 질의를 빠르게 응답하는 방법을 찾는 문제이다. O(Q|V|) 나 O(Q|E|) 정도에는, 기본적인 그래프 탐색 알고리즘으로도 아주 쉽게 풀수 있지만, 더 나은 복잡도를 내기는 쉽지 않은 문제이다. 2번 쿼리가 없다면 union-find data structure (링크) 를 사용해서 쉽게 풀 수 있지만, 더 복잡한 질의가 들어왔을 때는 쉬운 풀이가 존재치 않는다. 일반적인 경우 이 문제의 해법은 매우 어려워 보인다 (링크). 하지만, 오프라..
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=639&page=show_problem&problem=4917 설명이 개판인 점은 양해 부탁한다 (풀이 쓸 시간이 없음.. ㅠㅠ) 어떠한 시간에 대해서 겹치는 구간이 100개인데, 이는 임의의 interval i 에 대해서, sj < si이며 자신과 교차하는 interval이 100개 이하라는 것으로 해석할 수 있고, 고로 모든 교차 쌍의 개수가 100N개 이하라는 결론으로 귀결된다. 요트를 모두 시작점 순으로 정렬하자. 만약에 요트가 단 하나라면, 간단한 dynamic programming을 통해서 O(N)에 해결할 수 있다. 문제는 요트가 두개라는 ..
- Total
- Today
- Yesterday