-
Link Cut Tree Subtree Query
안녕하세요, jthis입니다. 이 글에서는 Link-Cut Tree에서 Subtree Query를 효율적으로 수행하는 방법에 대해 소개하겠습니다. 편의상 코드는 Splay Tree를 기준으로 설명하겠습니다. Link Cut Tree Link-Cut Tree는 간선 추가 삭제와 경로 쿼리(Path Query) 를 지원하는 자료구조입니다. 시간복잡도는 amortized $O(\log N)$이며, amortized를 제거하여 $O(\log N)$으로도 가능합니다. 또한, 이 자료구조는 Subtree 연산도 지원할 수 있습니다. 따라서 Top Tree로 해결할 수 있는 대부분의 쿼리 문제를 거의 모두 Link-Cut Tree로 대체할 수 있습니다. Link-Cut Tree는 Splay Tree로만 구현할 수 있다고 생각할 수도...
-
Moving Least Squares Projection 2 - Optimization
지난 글 Moving-Least-Squares-Projection 기존 MLS Projection의 한계 지난 글의 결론 부분에서 간략하게 짚어보았지만, 전에 설명한 방법은 성능적으로도, 그리고 컴퓨팅적으로도 한계가 명확했습니다. 첫째, 측정하고자 하는 물체의 뾰족한 부분이 제대로 표현되지 않고 뭉툭한 형태로 구해집니다. 이는 근본적으로 기존 MLS Projection은 smoothing 기반 기법이기 때문입니다. 아래 정리해본 기존 MLS Projection의 로직을 생각해보면 당연한 결과입니다. 뾰족한 부분에서는 하나의 뚜렷한 Local Approximating Hyperplane이 존재하지 않고, 여러 개의 근사 평면이 서로 교차하게 됩니다. 따라서 알고리즘이 도출하는 결과는 이들 사이의 ‘평균’ 평면이...
-
웹 개발의 3요소: HTML, CSS, JavaScript
서론 웹 페이지를 만들 때 가장 기본이 되는 세 가지 언어는 HTML, CSS, JavaScript 입니다. 프로그래밍에 관심이 있다면 누구나 들어봤을 용어지만, 웹 개발을 처음 접하는 입장에서는 이들 기술의 동작과 상호작용을 먼저 이해하는 것이 중요하다고 생각합니다. 단순한 사용법이 아니라, 브라우저 내부에서 HTML/CSS/JS(JavaScript)가 처리되는 흐름, DOM(Document Object Model)과 렌더링 엔진의 역할, JavaScript의 이벤트 루프와 비동기 처리 방식 등 기본 원리를 빠르게 알아보겠습니다. 본 글에서는 다음과 같은 내용을 다룹니다. HTML: 구조를 정의하는 마크업 언어의 역할, 태그와 DOM의 관계,...
-
Graph Degeneracy와 Subgraph Counting
1. Introduction 그래프 $G$에서 특정 패턴 그래프 $H$와 동형인 subgraph를 찾거나 그 개수를 계산하는 문제는 알고리즘 대회 뿐만 아니라 여러 분야에서 중요한 주제입니다. 특히 삼각형($C_3$)이나 $4$-사이클($C_4$), 경로($P_k$), 클리크($K_k$) 등 잘 알려진 그래프를 대상으로 한 문제는 이미 많은 문제로 출제된 바가 있습니다. 이번 글에서는 graph degeneracy 개념을 이용해 subgraph counting 문제를 해결하는 일반적인 방법을 소개합니다. 그래프는 무방향 단순 연결 그래프를 대상으로 하며, 이분 그래프(bipartite graph), 평면 그래프(planar graph), 트리(tree) 등 특수한 경우에만 적용 가능한 기법은 제외하였습니다....
-
Variation of Mo's Algorithm 3
안녕하세요 jthis 입니다. 이 글에서는 Variation of Mo’s Algorithm 1과 Variation of Mo’s Algorithm 2에 이어, 또 하나의 Mo’s Algorithm의 변형에 대해 소개하겠습니다. Online Mo’s Algorithm Mo’s Algorithm은 오프라인 쿼리에서 $(L, R)$ 포인터만 최소한으로 이동시켜 구간 쿼리를 빠르게 처리하는 기법이지만, 쿼리 순서를 바꿀 수 없는 온라인 문제에 그대로 적용하기 어렵습니다. 예를 들어, BOJ 14897를 생각해 봅시다. 이 문제에서는 다음 연산을 처리해야 합니다. $l$ $r$: $l$번째 수부터 $r$번째 수 중에서 서로 다른 수의 개수를 세고 출력한다....