유량 알고리즘과 테크닉들은 다른 분야에 비해서 자명하지 않고 어려운 증명들을 상당히 많이 사용한다고 느꼈다. 이러한 증명들을 알아둬야지만 상급 문제들을 풀 수 있다고 생각해서, 여러 중요한 정리들을 증명해 놓으려고 한다. 엄밀하게 잘 증명하려고 노력은 하고 있지만 잘 될지는 모르겠다. (지적 환영합니다) 정리 글하고 같이 보자. (정리에 없는 내용들도 있다.) 1) Edmonds-Karp Algorithm이 VE^2인 이유 Edmonds-Karp Algorithm이 VE^2인 이유를 증명하기 위해서는, 증가 경로를 많아야 VE번 찾는다는 것을 보이면 된다. BFS 한번이 O(E)이기 때문이다. 이 사실을 보이겠다. 정의 1. 간선의 capacity == 간선에 흐른 flow 인 간선을 포화 간선이라 정의..
BOJ SPOJ얼마 전 코포에 비슷한게 나와서 풀어본 문제. 집합 S가 주어졌을 때 XOR 값을 최대로 하는 부분집합의 XOR 값을 구하는 문제이다. 대부분의 경우에 2^maxbit - 1이 나올 거 같이 생겼지만, 어떠한 비트들이 다른 비트의 값에 종속적이기 때문에 실제로는 그렇지 않다는 것을 알 수 있다. 여기서 약간의 선형대수학 지식을 활용하자. 일단 주어진 수들을 modulo 2에서의 벡터로 생각할 수 있다. 선대에서 보통 이러한 경우가 나오면 row echelon form을 구해서 종속 관계를 추려내는데, 이것도 똑같이 하면 된다. 주어진 수로 이루어진 row echelon form을 구하는 방법은 다음과 같다. 숫자를 하나씩 하나씩 넣어가는데, 각 숫자에 대해서 가장 큰 비트부터 본다. 현재 ..
http://codeforces.com/contest/724 B (14분) N^6 짬. 이거 별로 안쉬웠다... 그냥 글러먹은듯 ㅠ D B를 풀고 친구 스탠딩을 봤을 때(=14분) 정우형이 AC를 받은 걸 확인했다. 그래서 잡았다. 그 때까지만 해도 내가 이걸 한시간 이상 잡을 줄은 몰랐다.. 문제를 처음에 보고 lexicographically라는 조건을 보고 내가 처음 한 생각은 "길이를 최소화해보는게 좋겠군!" 이었다. 대충 이 때부터 망한 듯 하다. 길이를 최소화한 상태에서 lexicographically smallest를 구했더니 예제가 안 나왔다. 앞에서부터 안 뽑힌 것중 가장 character가 작은 걸 뽑아가는 그리디를 생각했다. 세그먼트 트리를 하나 짰다. 예제 안나왔다. 또 하나 이상한 ..
일전에 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의 증가경로를 찾으면 안된다는 얘기를 듣고 멘붕함. 이 기회를 통해서 정리하려 한다. 여담으로, 프로그래밍 콘테스트 챌린징의 네트워크 유량 부분에 굉장히 중요하고 쉽게 배우..
(Autoamerican, 1980)
푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. 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의 ..
- Total
- Today
- Yesterday