전체 글 (48) 썸네일형 리스트형 Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다.먼저 보로노이 다이어그램과의 관계 및 '빈 외접원 속성'을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson's algorithm을 분석한다.마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다.1. Delaunay triangulation의 정의와 최적성평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은 계산기하학의 근본적인 문제 중 하나로, 유한요소해석, 컴퓨터 그래픽스, 지형 모델링 등 다.. SCPC 2025 후기 SCPC에서 상을 이미 2번 받은 나는 더 이상 상을 받을 수가 없다. 그래서 이번 scpc는 오프라인 대회장에 가는 것을 위해서 치기로 했다. 예선 1차이때는 몰입캠프 중에 있었다. 1차는 조금만 풀면 통과해서 밤에 대충 쳤다. 만점을 받았다.예선 2차꽤나 어려웠다... 1번 2번은 쉽게 풀었는데 3번에서 막혔다. 스위핑을 하는 복잡한 풀이가 나와서 오랜 시간 구체화만 하다가, 이 문제를 이렇게 풀게 되었다가는 디버깅만 하다가 끝날 것 같다는 생각이 들었다. 그래서 4번에서 서브태스크 2를 긁기로 했다.설상가상 4번 서브태스크도 왜인지 모르게 틀렸다. 중간에 멘탈이 나가서 잠깐 샤워를 하고 왔다. 차분하기 읽어보니까 내가 점수 조건을 잘못 읽었다는 것을 깨달았다. 지문에 있는 기준은 d_G(x, y) .. 250821 연습 요즘 팀연습을 안 하고 랜덤디펜스를 하는 중이다. 다사다난한 랜덤디펜스였다. 랜덤디펜스 하면서 문제풀이와 관련해서 몇 가지 생각을 하게 되었다. 시간이 상대적으로 느껴진다대략적인 문제 풀이를 떠올릴 때는 시간이 굉장히 느리게 간다. 문제 풀이 생각하다가 아 진짜 큰일났다 싶어서 시계 보면 10분만 흘려가있다.문제 풀이의 구체화를 할 때는 시간이 정말 빠르게 흘러간다. 복잡한 풀이의 구체화를 할 때는 20분이 호다닥 간다.문제 풀이의 구체화를 잘 했으면 구현을 하는데는 시간이 오래 걸리지 않는다. 코딩이 오래 걸리는 이유는 중간에 계획이 틀어져서 그렇다디버깅하는 시간, 풀이가 틀려서 갈아엎는 시간은 정말정말 빨리간다. 0분이면 해결되었을 것이 20~30분 가니까 시간이 아깝다. Costly Binary S.. Convex Hull Trick의 시간에 따른 관리 IntroductionDynamic programming은 많은 문제에서 등장하는 풀이 방법이다. Convex hull trick은 $O(n^2)$ 시간복잡도를 $O(n log n)$으로 줄여주는 등 획기적인 시간 단축을 이루어내는 dynamic programming에 대한 최적화 방법이다.이번 글에서는 시간에 따른 convex hull의 관리에 대해 알아본다. Persistent convex hull과 convex hull rollback에 대해서 알아보자.1. Persistent Convex Hull문제 상황$n$개의 직선 $f_i(x) = a_ix + b_i$가 주어진다. 직선들의 기울기 $a_i$는 증가하는 순서로 주어진다. 쿼리로 주어진 $t$, $k$에 대해서 $max_{i=1}^t f_i(k.. UCPC 2025 회고 + 250809 연습 대략적인 ucpc 타임라인을 말하면 다음과 같다. (나의 기준)E: 대충 빠르게 풂C: 송씨가 랜덤 이야기했는데 내가 p=2를 언급하고 빠르게 풂H: 풀이 냈는데, 풀이짜기 / 디버깅하기 를 3시간 동안 하다가 옆에 있는 songC가 풀이를 많이 냄. 180줄 코딩하는 것보다 남을 돕는 것이 팀에 더 이롭다는 것을 깨닫고 팀원 풀이 들어주기 / 예제 짜기 등을 하러 감 H번이 P3이라는 사실을 통해서 보면, 상당히 박았다는 것을 알 수 있다.이런 적이 한두번이 아니다.icpc 2023 때는 J번(P2) 예외처리 잘못 했다가 대회 직전까지 디버깅했다.icpc 2023 예선 때는 F번 자구비빔밥(D5)을 잡고 1xx줄 짜고 사망했다. 그래서 풀이를 내는 능력보다는 구현하는 능력이 딸린다고 생각했고, 백준랜덤.. 250717 연습 카이스트에서 여는 몰입캠프에서 오전부터 저녁까지 개발하느라 ps를 조금 놓았다...하지만 ucpc 예선도 치고, 2023 icpc yokohama regional도 푸는 등 심심할 때마다 문제를 풀었다. 1.1. Burnside lemmagroup $G$의 $X$에 대한 group action의 orbit을 개수를 구하는 공식이다.$$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$여기에서 $|X/G|$는 orbit 개수, $X^g$는 $g = g \cdot x$인 $x$의 집합이다. $g \cdot x = x$를 만족하는 $(g, x)$의 개수에 대한 double counting$g$를 기준으로 하면 $\sum_{g \in G} |X^g|$이다.$x$를 기준으로 하면 $\.. ucpc 2025 예선 후기 개요이번 ucpc는 serin, songc와 함께 Fox is cute 팀으로 참가했다. 다들 잘한다! 기본적으로 3 마스터 팀이다.예선은 각자 자기 방에서 치기로 했다.진행songc가 늦잠을 쿨쿨 자서 serin이랑 같이 돌았다. 2인팀이면 속도가 느릴 것이니까 스코어보드를 따라가야겠다고 생각했다. 나는 앞에서부터, serin은 뒤에서부터 봤다. A(00:01) azberjibiou: 제일 쉬운 문제가 A번이라고 해서 즉시 풀었다.B(00:04) azberjibiou: 그 다음 문제를 봤다. 애드혹 세팅에 이것저것 있어서 유심히 살펴봤지만, 결과적으로 매우 간단한 풀이가 도출되었다. 빠르게 풀고 넘어갔다.E(00:15) azberjibiou: C D E를 순서대로 봤는데, 쿼리 쿼리 쿼리여서 걸렀다. .. 연습 250626 1. https://www.acmicpc.net/problem/32512구사과님의 잘 비벼진 문자열 비빔밥이다. failure function으로 만든 트리에 대한 고찰이 잘 녹아있다. 문제는 그냥 잘 풀어서 풀이 생략. 중간에 모든 i에 대해 B[i..m]과 C의 longest common prefix를 구할 일이 있었다.나는 해싱이분탐색을 썼다. 해싱 소수에 const를 안 붙였더니 시간이 많이 걸렸다. 선형로그 시간복잡도이다. C[i..len(C)]와 C의 longest common prefix를 Zc, B[i..m]과 C의 longest common prefix를 Zb라고 하자.Zc는 Z 알고리즘으로 구할 수 있다.i=1부터 m까지 스위핑을 해서 Zb를 구하자. i+Zb[i]가 최대인 경우의 i와.. 이전 1 2 3 4 ··· 6 다음
