-
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$번째 수 중에서 서로 다른 수의 개수를 세고 출력한다....
-
Convex hull trick의 시간에 따른 관리
Convex Hull Trick의 시간에 따른 관리 Introduction Dynamic 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$에 대해서...
-
Barrett, Montgomery Reduction을 이용한 모듈러 연산의 고속화
1. Introduction 현대 CPU에서 나눗셈과 모듈러 연산은 연산 비용이 상당히 큰 편입니다. Agner Fog의 instruction tables에 따르면, Intel Skylake 아키텍처 기준으로 ADD, SUB의 latency는 1 cycle, MUL은 3~4 cycle인데 반해, DIV는 32비트는 26 cycle, 64비트는 최소 35 cycle, 최대 88 cycle까지 소요됩니다. 그런데 실제로 코드를 작성해보면 나눗셈 연산은 생각보다 빠르게 동작하는 경우가 많습니다. 이는 현대 컴파일러가 x / c, x % c에서 나누는 수 c가 compile-time const일 때 해당 연산을 곱셈(*)과 시프트(>>)로 변환해 최적화해주기 때문입니다....
-
CUDA를 이용한 행렬 곱셈
Introduction 행렬 곱셈은 병렬 프로그래밍에서 가장 중요한 연산 중 하나입니다. 행렬 곱셈은 컴퓨터 그래픽스, 인공 신경망 등 다양한 분야에서 기본적인 연산으로 사용되며, 사용하는 메모리에 비해 연산의 수가 많아 병렬화하기에 적합하기 때문입니다. GPU는 이러한 병렬 연산에 특화된 하드웨어입니다. GPU에는 단순한 연산 수천 개를 동시에 수행하도록 많은 연산 장치가 있으며 CPU의 cache 구조와 비슷하게 각 계층에서 공유되는 메모리가 있습니다. 행렬 곱셈을 위한 cuBLAS와 같은 라이브러리가 있으며, 이 글에서 소개할 내용은 해당 라이브러리를 구현하는 데 사용된 테크닉의 일부입니다....