애니메이션

데이터를 메모리에 들어가는 청크 단위로 정렬해 디스크에 Run 으로 저장하고, K-way merge 로 한 번에 합쳐 출력한다.

cin/cout sync 해제, getchar_unlocked, mmap 으로 입출력 속도 30배 향상.

p=7, a=3 예제. {1,2,3,4,5,6} × 3 (mod 7) = {3,6,2,5,1,4}. 일대일 대응으로 3^6 ≡ 1 (mod 7) 증명.

두 다항식 A=[1,2,3], B=[4,5,6] 의 곱셈을 FFT/NTT 로. 계수→값(DFT)→점별 곱→계수(IDFT) 의 butterfly 단계 시각화. O(n log n) 컨볼루션.

격자에서 BFS로 연결된 같은 색 영역을 새 색으로 칠하는 알고리즘

Σ ⌊(ai+b)/m⌋ 의 기하적 해석과 O(log m) 계산

A=[1,2,3,4], B=[5,6,7,8]의 XOR 컨볼루션. XOR butterfly로 변환, 점별 곱셈, 역변환으로 O(N log N)에 c[k] = Σ_{i⊕j=k} a[i]·b[j] 계산.

N=4 stable matching with Gale-Shapley. Men propose to women by preference until all matched.

일반 그래프에서 최대 매칭을 찾는 Edmond's Blossom 알고리즘: odd cycle 을 축약해 augmenting path 를 발견.

두 테이블을 같은 해시 함수로 N 개 파티션에 분할한 뒤, 같은 번호의 파티션 쌍끼리 메모리에서 조인한다. 빌드가 메모리에 안 들어가도 작은 조각으로 나눠 처리할 수 있다.

f(x,y)=x^2+2y^2 위 (3,2) 에서 시작, lr=0.1, 10 step trajectory.

6개 구간을 종료 시각 순 정렬 후 greedy 선택. 충돌 없는 최대 개수 선택.

Green 정리: 폐곡선 C 의 선적분이 내부 영역 D 의 이중 적분과 같음. 다각형 면적을 O(N) 에 계산하는 shoelace 공식의 기반.

Chain B-B-R (Blue, Blue, Red) rising from ground. Each blue = +1, red = -1. Total = +1, Left wins.

반평면 4개 (y>=0, x>=0, x+y<=6, y<=x+2) 의 교집합을 각도 정렬 + deque 로 O(N log N) 에 구한다.

왼쪽 집합 S의 모든 부분집합에 대해 |N(S)| ≥ |S|면 완전 매칭 존재

HashMap 이 해시 충돌 시 linked list 로 체이닝하고, 한 버킷이 8개 이상이 되면 red-black tree 로 변환하는 과정.

배열을 max-heap 으로 만든 뒤, 루트(최댓값)를 끝으로 보내며 heap 크기를 줄여간다. In-place + O(n log n) 보장.

Heavy 간선으로 트리를 O(log N) 체인으로 분할

Greedy (당장 최선), Local Search (이웃 개선), Approximation (OPT 대비 alpha 보장).

ABCBDAB 와 BDCAB 의 LCS 를 Hirschberg 로. fwd/rev DP 행만 유지, 분할점 k=3 에서 재귀.

이미 정렬된 부분에 새 원소의 올바른 위치를 찾아 삽입. 작은 입력에 가장 빠른 O(n²) 정렬.

각 원소가 일차함수 f(t) = m·t + b 로 변할 때, melt point (교차) 를 관리하며 최댓값을 O(log² N) 에 유지.

text='ABABABC' 에서 pattern='ABABC' 찾기. failure 함수로 mismatch 시 효율적 점프