-
jinhan814's profile image
jinhan814
April 25, 2025
read, write, mmap을 이용한 Fast I/O 구현 (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행...