나 빼고 다 아는 그들만의 웰노운 테크닉 모음
목표
- 고인물의 대화를 이해하자
- 나도 아는 척해보자
- 랭작 좀 해보자
TODO
- 주제별 설명글 링크 달기
- 주제별 설명 내 블로그에 올리기
- 연습 문제 풀이 올리기
목차
- 그들만의 웰노운 사전지식
- 동적 계획법 관련
- Berlekamp-Massey
- Aliens Trick
- Slope Trick
- 자료구조
- Segment Tree Beats
- Kinetic Segment Tree
- BBST(Splay Tree, Treap)
- Dynamic Tree(Link/Cut Tree, Euler Tour Tree, Top Tree)
- Stern-Brocot Tree
- Permutation Tree
- 그래프 이론
- Push Relabel Algorithm, Cost Scaling Algorithm
- Dual of Planar Graph
- Dominator Tree
- Directed MST
- Offline Incremental SCC, Offline Dynamic MST
- Chordal Graph
- Treewidth, Tree Decomposition
- General Graph Matching
- 문자열
- Palindrome Tree(A.K.A. eerTree)
- Suffix Automaton, Suffix Tree
- Run Enumerate
- 수학
- FFT, NTT
- Polynomial Division, Kitamasa
- FWHT
- Multipoint Evaluation
- Polynomial Interpolation
- Generating Function
- Mobius Function
- Young Tableau Diagram, RSK Correspondence
- Matroid
- LGV Theorem
- 기하
- Voronoi Diagram, Dulaunay Triangulation
- 동적 계획법 관련
- 그들만의 웰노운 문제 유형
- 민코프스키 합 DP
- Regions Trick
- Bulldozer Trick
- 쿼리를
$\sqrt N$ 또는$\sqrt Q$ 개씩 묶어서 처리하는 유형 - 세그먼트 트리를 이용해 그래프의 간선 개수를 줄이는 유형
- 볼록 다각형의 접선을 이용해 최적화하는 유형
- 트리 위에서 exchange argument
- 그들만의 이상한 최적화
- Fast I/O
- Bitset을 이용한 최적화
- SIMD
- Barrett Reduction
- 그들만의 이상한 밈
그들만의 웰노운 사전지식
Berlekamp-Massey
- 튜토리얼
- (한글) koosaga
- 연습 문제 - 점화식 계산
- 연습 문제 - 최소 다항식
Aliens Trick
- 튜토리얼
- (한글) koosaga
- (영어) robert1003
- (영어) USACO Guide
- 연습 문제 - 최적값 구하기
- 연습 문제 - 역추적
Slope Trick
- 튜토리얼
- (한글) jwvg0425
- (한글) koosaga
- (영어) USACO Guide
- (한글) lobo_prix
- 연습 문제
Segment Tree Beats
- 튜토리얼
- 연습 문제
Kinetic Segment Tree
- 튜토리얼
- (한글) koosaga
- 연습 문제
BBST(Splay Tree, Treap)
- 튜토리얼 - Splay Tree
- 튜토리얼 - Treap
- (영어) SecondThread
- 연습 문제
- 연습 문제 - Persistent BBST
Dynamic Tree(Link/Cut Tree, Euler Tour Tree, Top Tree)
- 튜토리얼 - Link/Cut Tree
- (한글) imeimi
- 튜토리얼 - Euler Tour Tree
- (영어) PurpleCrayon
- 튜토리얼 - Top Tree
- (한글) koosaga
- 연습 문제 - 공통
- 연습 문제 - Link/Cut Tree
- 연습 문제 - Euler Tour Tree
- 연습 문제 - Top Tree
Stern-Brocot Tree
- 튜토리얼
- (한글) myungwoo
- 연습 문제
Permutation Tree
- 튜토리얼
- 연습 문제
Push Relabel Algorithm, Cost Scaling Algorithm
- 튜토리얼 - Push Relabel Algorithm
- (한글) koosaga
- 튜토리얼 - Cost Scaling Algorithm
- (한글) koosaga
- 연습 문제 - Push Relabel Algorithm
- 연습 문제 - Cost Scaling Algorithm
Dual of Planar Graph
- 튜토리얼
- (한글) ahgus89
- 연습 문제
Dominator Tree
- 튜토리얼
- 연습 문제 - DAG
- 연습 문제
Directed MST
- 튜토리얼
- 연습 문제
Offline Incremental SCC, Offline Dynamic MST
Chordal Graph
- 튜토리얼
- (한글) ainta
- 연습 문제
Treewidth, Tree Decomposition
- 튜토리얼
- (한글) koosaga
- (영어) Ignasi Sau
- 연습 문제 - 트리 분할
- BOJ 16183 Electronic Circuit - 주어진 그래프가 Series-Parallel Graph인지 판별
- Library Checker - Tree Decomposition (Width 2) - Series-Parallel Graph의 Tree Decomposition을 구하는 문제
- BOJ 26415 Ghost - Halin Graph의 Tree Decomposition을 구하는 문제
- 연습 문제 - DP
- 연습 문제 - 최단 경로 쿼리
General Graph Matching
- 튜토리얼
- (한글) koosaga
- 연습 문제 - 무가중치
- 연습 문제 - 가중치
Palindrome Tree (A.K.A. eerTree)
- 튜토리얼
- (한글) Karuna
- (영어) Alessio Piergiacomi
- 연습 문제
Suffix Automaton, Suffix Tree
- 튜토리얼
- (한글) koosaga
- 연습 문제
Run Enumerate
- 튜토리얼
- (영어) koosaga
- 연습 문제
FFT, NTT
- 튜토리얼
- 연습 문제
Polynomial Division, Kitamasa
- 튜토리얼 - Polynomial Division
- (한글) ho94949
- (한글) hyperbolic
- (한글) cubelover
- 튜토리얼 - Kitamasa
- (한글) jhnah917
- 연습 문제
FWHT
- 튜토리얼
- 연습 문제
Multipoint Evaluation
- 튜토리얼
- (한글) ho94949
- (한글) hyperbolic
- 연습 문제
Polynomial Interpolation
- 튜토리얼
- (한글) hyperbolic
- 연습 문제
Generating Function
- 튜토리얼
- (한글) evenharder
- (한글) yclock - 1, yclock - 2
- 연습 문제
Mobius Function
- 튜토리얼
- (한글) rkm0959 - 1, rkm0959 - 2
- (한글) snowflake - 1, snowflake - 2, snowflake - 3, snowflake - 4
- (한글) ahgus89
- 연습 문제
Young Tableau Diagram, RSK Correspondence
- 튜토리얼
- (영어) mango_lassi
- (한글) yclock
- 연습 문제
Matroid
- 튜토리얼
- 연습 문제
LGV Theorem
- 튜토리얼
- 연습 문제
Voronoi Diagram, Dulaunay Triangulation
- 연습 문제
그들만의 웰노운 문제 유형
민코프스키 합 DP
- 튜토리얼
- (한글) arnold518
- 연습 문제
Regions Trick
- 튜토리얼
- (한글) jhnah917 - 쿼리 캐싱 파트
- 연습 문제
Bulldozer Trick
- 튜토리얼
- (한글) jhnah917
- 연습 문제
쿼리를 $\sqrt N$ 또는 $\sqrt Q$ 개씩 묶어서 처리하는 유형
- 튜토리얼
- (한글) jhnah917 - 쿼리에 대한 버킷 파트
- 연습 문제
세그먼트 트리를 이용해 그래프의 간선 개수를 줄이는 유형
- 튜토리얼
- (한글) jhnah917
- 연습 문제
볼록 다각형의 접선을 이용해 최적화하는 유형
- 튜토리얼
- (한글) jhnah917 - 볼록 다각형의 접선을 이용한 최적화 파트
- 연습 문제
트리 위에서 exchange argument
- 튜토리얼
- 연습 문제
그들만의 이상한 최적화
Fast I/O
- 튜토리얼
- (한글) cgiosy
- 연습 문제
- BOJ 11921 0.1
- BOJ 18702 Array Queries - 수열과 쿼리 28 + Fast I/O
Bitset을 이용한 최적화
- 튜토리얼
- (영어) Errichto
- 연습 문제
- BOJ 20501 Facebook
- BOJ 9423 레슬링 팀 선발
-
BOJ 9789 Friendship Graph -
$O(N^3/w)$ -
BOJ 23373 Jack the Mole -
$O(N^3W/w)$ - BOJ 17184 Nautilus
- BOJ 18439 LCS 6
SIMD
- 튜토리얼
- (한글) jhnah917
- 연습 문제
-
BOJ 14438 수열과 쿼리 17 -
$O(Q \log N)$ vs$O(NQ/8)$ -
BOJ 3847 Comparing answers -
$O(N^2)$ vs$O(N^3/8)$ -
BOJ 13925 수열과 쿼리 13 -
$O(Q \log N)$ vs$O(NQ/8)$ -
BOJ 23577 Trio -
$O(81N^2)$ vs$O(N^3/96)$ vs$O(20000N^2/512)$
-
BOJ 14438 수열과 쿼리 17 -
Barrett Reduction
- 튜토리얼
- (영어) Spheniscine
- 연습 문제
그들만의 이상한 밈
추가 예정