Computer Science (14) 썸네일형 리스트형 linear time 2+E approximation algorithm for min cut David W. Matula의 1993년 논문 을 다룬다. 이 논문에서 다루는 그래프는 가중치가 없는 그래프이다.(multi-edge는 허용한다.) 이 알고리즘의 주목할 만한 점은 선형이면서도 min cut에 대한 강력한 approximation을 제공한다는 점이다. 이 알고리즘은 보통 min cut의 크기를 대략적으로 알아야 할 때(대표적인 예시로 Nagamochi-Ibaraki 1992에서 sparse k-connectivity certificate를 만들기 위해 대략적인 min cut 값을 필요로 함)에 사용된다. 이 논문에선 Maximum Adjacency Search라는 것을 도입한다. 시작 정점 $v$에서 시작하여, 현재까지 탐색한 정점을 $v_1, v_2, ..., v_k$이라 할 때 남은 .. 2-Respecting Cut in O(MlogN) Times 그래프의 최소 절단(Minimum Cut)은 그래프를 연결되지 않은 상태로 만들기 위해 삭제해야 하는 간선의 가중치의 최소 합을 의미한다. Minimum Cut을 찾기 위한 방법들이 제시되어 왔었다. Min cut Max flow 정리를 이용하여, Gomory-Hu Tree를 구성한 후 이 중 최소 절단 구하기. 이 방법은 가장 처음 제시된 방법으로, Gomory와 Hu가 O(n)의 flow 연산으로 이를 구하는 방법을 제시하여 다항시간 해법이 제시되었다. 이후 오랜 기간동안 발전이 없었지만, 2020년대에 들어서자 Jason Li et al.에 의해 가중치가 없는 그래프에서 poly-log(n)의 flow 연산으로 gomory-hu tree를 구할 수 있게 되었다. 이후 flow가 near-linear.. JOISC 2021/2022 Day 1. Jail 트리 형태의 감옥이 주어진다. 이후 M개의 죄수의 초기 위치인 a_i와, 목표 위치인 b_i가 주어진다. 죄수를 인접한 위치로 옮길 수 있다. 다음 두 조건을 만족하면서 M개의 죄수를 목표 위치로 옮길 수 있는지 판별하면 된다. 1. 도중에 한 방에 여러 명의 죄수가 존재해선 안 된다. 2. 한 죄수는 무조건 최단경로로만 이동해야 한다. (트리이므로 최단경로가 유일하다.) 다음과 같은 관찰이 가능하다. Claim) 만약 가능하다면, Exist i, a_i -> b_i 사이 아무것도 없고, b_i는 어떠한 a_j -> b_j 사이에도 존재하지 않음(즉 그냥 i를 먼저 밀어버리고 생각 가능) 이 강력한 Claim을 바탕으로 문제를 그냥 풀어버릴 수 있다. 죄수들을 정점으로 하는 그래프를.. 1221 Problem Solving CERC 2021 F Letters : 그냥 구현하면 된다. Petro Camp Summer 2016 Day 6 D Championships : 먼저 차수가 d 미만인 점을 제외하고, 이를 바탕으로 위상정렬하듯이 큐로 불가능한 후보들을 제거해준 후 가장 큰 연결성분을 찾으면 된다. Petro Camp Summer 2016 Day 5 I Vier : a+b = c+d = K일 때 K를 고정시키면 N개 후보군에 대해 성립하는지 판별은 O(N)에 가능. 임의의 순열은 모든 K에 대해 성립하거나, 아주 적은 개수의 K개에 대해서 성립하지 않을 것으로 추측 가능하다. 이를 바탕으로 K를 무작위로 1000번정도 정해주면 된다. CERC 2021 K Single-track railway : 세그먼트 트리에서 이분탐색.. 1114 Problem Solving IOI 2005 Practice 1 : Divisor game p가 소수라고 생각해보면, n = p인지 확인하기 위해선 p 이하의 모든 소수들에 대해 질문을 해 보아야 한다. 이러한 결과를 바탕으로 생각해보면, 그냥 체를 이용해 n 이하의 모든 소수를 구하고 그 소수들에 대해 지수를 구한다고 생각하면 풀 수 있다. (최소 증명은 자명하므로 생략함) 시간복잡도는 O(NlogN)이다. Google Code Jam 2014 Round 2 C : Don't Break The Nile Small : 그래프를 탐색한다고 생각하자. 단순 플로우 알고리즘을 돌릴 경우 TLE가 날 것이다. 다음과 같은 그리디한 전략으로 격자 그래프에서 dfs를 하자 : 왼손 법칙을 하면서 미로를 건너듯이, 왼손이 벽에 붙어있도록 방향을.. 0916 Problem Solving urd05의 추천으로 4문제 셋을 돌았습니다. 점수는 50/100/85/0입니다. JOISC 2016/2017 Day 1 : Sparklers 50점 (서브테스크 1, 2) : 기본적으로 파라메트릭 서치를 박고 시작하는건 굉장히 자명해 보인다. 자명한 관찰을 하나 할 수 있다. 현재 l~r까지를 소비했을 때, 다음 소비하는 것은 l-1 혹은 r+1이 될 것이다. 이를 바탕으로 DP를 정의하자. L[s][e], R[s][e]를 정의하자. 이는 s~e 구간의 모든 것을 소비했을 때 가능한 최소 위치, 최대 위치이다. DP 전이는 굉장히 간단하다. L[0][N-1], R[0][N-1]이 존재한다면 가능, 아니면 불가능이다. 시간복잡도는 O(N^2log(1e9/T))이다. 100점 : L번째 사람부터 R번째 사.. 0911 Problem Solving 보호되어 있는 글입니다. 0909 Problem Solving 보호되어 있는 글입니다. 이전 1 2 다음
