-
jinhan814's profile image
jinhan814
July 28, 2025
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) 등 특수한 경우에만 적용 가능한 기법은 제외하였습니다....
-
jinhan814's profile image
jinhan814
June 3, 2025
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일 때 해당 연산을 곱셈(*)과 시프트(>>)로 변환해 최적화해주기 때문입니다....
-
jinhan814's profile image
jinhan814
May 11, 2025
read, write, mmap을 이용한 Fast I/O 구현 (2)
이번 글에서는 이전 글인 read, write, mmap을 이용한 Fast I/O 구현 (1)에 이어 Bit-Twiddling Hack을 적용한 더 빠른 입력 기법과 Lookup Table 및 SIMD를 활용한 출력 기법을 살펴보겠습니다. 1. Faster Input Implementation read 또는 mmap을 이용한 빠른 입력 방식은 입력 버퍼를 두고 버퍼 단위로 한 번에 입력을 읽어오며 입력 속도를 향상시킵니다. 대부분의 문제에서는 이 정도 최적화만으로 충분하지만, 한 번에 여러 문자를 처리할 수 있다면 입력 속도를 더욱 높일 수 있습니다. 1.1 8-Byte Parsing 앞서 소개한...
-
jinhan814's profile image
jinhan814
April 25, 2025
read, write, mmap을 이용한 Fast I/O 구현 (1)
1. Introduction 입출력 연산은 C++에서 가장 무거운 연산 중 하나입니다. 일반적인 산술 및 논리 연산은 대략 $1$초에 $1$억 번 정도 수행할 수 있는 것으로 알려져 있지만, 입출력 연산은 입력 또는 출력 값의 개수가 $10^5$ 이상만 되어도 입출력 속도가 전체 실행 시간에 상당한 영향을 줄 수 있습니다. (참고) 이럴 때 표준 스트림 함수인 cin, cout 대신 read, write와 같은 저수준 입출력 함수를 사용하면 입출력 시간을 유의미하게 줄일 수 있습니다. 다만 이 함수들은 문자열 이외의 자료형을 자동으로...
-
jinhan814's profile image
jinhan814
March 23, 2025
Block Decomposition을 이용한 Online FFT 구현
Introduction 이 글에서는 Block Decomposition을 이용한 Online FFT(Fast Fourier Transform) 구현 방법을 소개합니다. 두 수열 $A$, $B$의 convolution $C$를 $\mathcal{O}(n\log n)$에 구하는 FFT 알고리즘은 두 수열 $A$, $B$가 모두 주어져야만 사용할 수 있습니다. Online FFT는 $A$, $B$의 원소 $a_i$, $b_i$가 하나씩 주어질 때 $c_i$를 온라인으로 구하는 알고리즘입니다. 이는 점화식이 convolution 형태이면서 $c_0, \cdots, c_{i-1}$을 알아야 $a_i$, $b_i$를 구할 수 있는 경우(예를 들면 카탈란 수 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$)에 사용할 수 있습니다. Online FFT는 여러...
-
jinhan814's profile image
jinhan814
January 31, 2025
다양한 그래프 표현 방법
개요 그래프는 다양한 방법으로 표현될 수 있습니다. 각 방법은 특정 상황에서 장단점을 가지며, 문제의 요구 사항에 따라 적절한 표현 방법을 선택하는 것이 중요합니다. 이 글에서는 그래프를 표현하는 4가지 방법인 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), CSR(Compressed Sparse Row), 그리고 XOR Linked Tree에 대해 설명합니다. (XOR Linked Tree 개념은 코드포스 글 https://codeforces.com/blog/entry/135239을 참고해 작성했습니다) 1. 인접 행렬 (Adjacency Matrix) 개념 인접 행렬은 그래프를 2차원 배열로 표현하는 방법입니다. 그래프에 i번 정점에서 j번 정점으로 가는 간선이 있다면 i행...