티스토리

Blog

검색하기

블로그 홈

Blog

cross-ratio.tistory.com/m

Jihoo Lee 님의 블로그입니다.

구독자: 5

방명록 방문하기

주요 글 목록

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$이라 할 때 남은 .. 공감수 1 댓글수 0 2024. 1. 6.
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.. 공감수 1 댓글수 0 2024. 1. 5.
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을 바탕으로 문제를 그냥 풀어버릴 수 있다. 죄수들을 정점으로 하는 그래프를.. 공감수 0 댓글수 0 2023. 1. 19.
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 : 세그먼트 트리에서 이분탐색.. 공감수 0 댓글수 0 2022. 12. 22.
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를 하자 : 왼손 법칙을 하면서 미로를 건너듯이, 왼손이 벽에 붙어있도록 방향을.. 공감수 0 댓글수 1 2022. 11. 19.
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번째 사.. 공감수 0 댓글수 0 2022. 9. 17.
0911 Problem Solving 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 9. 12.
0909 Problem Solving 보호되어 있는 글입니다. 공감수 0 댓글수 2 2022. 9. 10.
0903 Problem Solving 4문제로 이루어진 셋을 돌았습니다. 결과는 100 / 42 / 0 / 100입니다. 1. JOI2020 Capital City(수도) 30점 (서브테스크 3) : 직관적인 DnC가 보인다. 현재 구간을 [s, e)라고 할 때, mid를 포함하는 답을 생각해보면 순회를 통해 O(N) 혹은 O(NlogN)에 mid를 포함하는 모든 답을 구할 수 있음을 알 수 있다. 또한 어떤 도시가 mid를 사이에 둔다면, 이 도시가 수도로써 동작하기 위해선 mid를 반드시 거쳐야 하므로 mid를 포함하는 답에 포함되게 된다. 따라서 mid가 사이에 없는 도시들로 분리할 수 있고, 이를 통해 DnC가 가능하다. 100점 : 위 방법을 트리에서 정확히 똑같이 하면 된다. 센트로이드 분할을 이용하자. (이 경우엔 한번에 여러 .. 공감수 0 댓글수 0 2022. 9. 4.
0827 Problem Solving 4문제로 구성된 셋을 돌았습니다. JOI 17 : Long Mansion 먼저, 각 i에 대해 최종 도달 가능 범위를 L[i] ~ R[i]라 하자. 이러한 L[i], R[i]를 모두 구할 수 있다면, 쿼리를 O(1)에 처리 가능하다. 이제 이러한 L[i], R[i]를 구해보자. 10점 (서브테스크 1) : 최대한 왼쪽으로 갔다가 최대한 오른쪽으로 갔다가 ... 구간이 일정해질 때까지(더 이동이 불가능해질 때까지) 반복한다. 가지고 있는 Key의 정보는 std::set으로 관리한다. 시간복잡도는 O(N^2logN + Q)이다. 25점 (서브테스크 2) : Key의 종류가 최대 20개이다. 따라서 이를 비트마스킹하고 bitwise or SegTree를 짜고, 최대한 왼쪽으로 가는 것과 최대한 오른쪽으로 가는.. 공감수 0 댓글수 0 2022. 8. 30.
0826 Problem Solving 푼 시간 순서입니다. BOJ 19265 Is It a p-drome? 간단한 FFT, 해싱 문제이다. 일단 무지성으로 각 부분열에 대해 Rabin Fingerprint를 찍고 생각하자. 순열 p를 순열 사이클 분할을 해 '같아야만 하는 index들'의 집합을 적절히 구한다. 이러한 집합을 적절히 구하고 나면, 만약 부분열이 p-drome일 경우 Rabin FingerPrint를 C라 하면 C = sigma i = 0 ~ M-1 A[i] * B[i] (B[i] = sigma j = 0 ~ M-1, i and j is in same cycle, i is smallest on that cycle : h^j mod p) 와 같은 식이 도출된다. 이는 FFT로 쉽게 구할 수 있고, 이 값이 Rabin Finger.. 공감수 1 댓글수 0 2022. 8. 30.
0825 Problem Solving 2020년 2차 선발고사를 쳐봤습니다. 아이싱 문제는 풀이를 이전에 접한 적이 있어서, 첫 3문제만을 풀었습니다. 결과 : 150 / 43 / 18 1. 마법의 다이얼 먼저 좌표 압축을 한 뒤, 각 다이얼 기준으로 i번째 칸에 다이얼을 모으게 될 때 얼마나 돌려야 할지를 생각해보자. 이는 함수 y = ax + b 꼴들로 나타내어지며, 따라서 각 칸 별로 x의 계수, 상수항을 저장해둔 뒤 prefix sum을 잘 관리해주면 풀 수 있다. 2. 하나 둘 셋 43점 (서브테스크 1, 2) : 먼저 다항식 시간복잡도의 풀이를 위해선 다음과 같은 아이디어를 얻어야 한다. (1, 2, 3) 쌍의 개수와 (3, 2, 1) 쌍의 개수를 정하고 생각해보면, 1과 3의 위치를 그리디하게 선택 가능하고, 무슨 1을 무슨 3.. 공감수 1 댓글수 0 2022. 8. 30.
0823 Problem Solving 2020년도 1차 국가대표 선발고사 시험을 쳐봤습니다. 결과 : 100 / 48 / 47 / 100 1. 문자열 찾기 100점 : S1의 연속된 부분문자열 중 S2와 '사실상 같은' 것의 개수를 구하면 된다. '사실상 같다' 라는 것은 먼저 두 문자열의 길이가 같고, 쌍 (i, j)에 대해 S1[i] == S1[j] S2[i]==S2[j]임을 의미한다. 이는 간단한 해싱으로 가능하다. 알파벳의 개수는 총 26개이므로, 각 26개의 알파벳에 대해 Rabin - Fingerprint를 찍는다. 두 문자열이 '사실상 같다' 이러면 S1, S2에 대해 이 Rabin-Fingerprint의 집합들이 같아야 한다. set으로 비교하거나, 혹은 전체를 xor해서 같으면 같다고 해싱하는 것도 좋은 것 같다. 난 후자로.. 공감수 1 댓글수 0 2022. 8. 29.
0822 Problem Solving 푼 문제들을 정리해 보자. 푼 문제들은 난이도순이 아닌 시간순이다. 08/16 Codeforces Round #814 (Div. 1) 29등을 해 오랜만에 LGM 퍼포를 받았다. A1, A2 : Burenka and Traditions 문제를 잘 분석하면 range가 1인 시행, range가 2인 시행으로 분할할 수 있고 2인 시행을 많이 할 수록 유리하다는 것을 깨달을 수 있다. range 2인 시행을 함으로써 이익이 되기 위하려면 구간 l~r 에 대해 A[l] ^ A[l+1] ^ .. ^ A[r] = 0이어야 하고, 이 구간에서 1만큼의 이득을 얻을 수 있다. 이는 map을 통해 prefix xor값을 C[i]라 하면 prefix xor이 c가 되는 최소의 i를 M[c] = i라고 정의한 다음, 이를.. 공감수 1 댓글수 0 2022. 8. 29.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.