h-contest lessons

입력 제한을 보고 가능한 시간 복잡도와 메모리 사용량을 빠르게 가늠하는 기본 감각을 익힙니다.

선수: 없음

다음: 실전 C++ 제출과 검증 정렬 알고리즘 누적합과 차분 배열 이분 탐색과 파라메트릭 서치

연관: 동적 계획법

함수 구현형 제출 계약과 TC 초기화를 확인하고, STL 없는 ORDERING 기준선을 실제 채점기로 검증합니다.

선수: 복잡도와 입력 크기 감각

다음: 휴리스틱 알고리즘 정렬 알고리즘 BFS/DFS와 격자 탐색

연관: 우선순위 큐와 힙 Testing과 Stress Test STL 없는 공통 라이브러리

• 제출 계약과 상태 초기화 submission-and-state
• ORDERING 기준선 실행과 검증 practice

배열·난수·안정 정렬·큐·최소 힙을 독립된 블록으로 관리하고, 필요한 코드만 제출 풀이에 조합합니다.

선수: 실전 C++ 제출과 검증

다음: 정렬 알고리즘 그리디 알고리즘 우선순위 큐와 힙

연관: 휴리스틱 알고리즘 Testing과 Stress Test BFS/DFS와 격자 탐색

정렬 기준, 안정성, 시간 복잡도, 정수 전용 정렬까지 문제 풀이에 필요한 정렬 감각을 익힙니다.

선수: 복잡도와 입력 크기 감각 실전 C++ 제출과 검증

다음: 누적합과 차분 배열 이분 탐색과 파라메트릭 서치 좌표 압축

연관: 투 포인터와 슬라이딩 윈도우 STL 없는 공통 라이브러리

쉬운 반례부터 대표 증명 패턴까지, 그리디 선택이 왜 최적해로 이어지는지 익힙니다.

선수: 정렬 알고리즘

다음: 우선순위 큐와 힙 동적 계획법 Proof와 Invariant

연관: 휴리스틱 알고리즘 STL 없는 공통 라이브러리

최적해를 증명하기 어려운 문제에서 제한 시간 안에 좋은 해를 만드는 휴리스틱 설계 방법을 세 가지 실전 사례와 함께 익힙니다.

선수: 실전 C++ 제출과 검증

다음: Testing과 Stress Test TSP와 해밀턴 경로

연관: TSP와 해밀턴 경로 그리디 알고리즘 동적 계획법 STL 없는 공통 라이브러리

• 실전 예시: 배송 순서 개선 ordering-route-improvement
• 초기해와 지역 탐색 search-strategies
• 실전 예시: 광고판 도시 배치 placement-and-repair
• 실전 예시: 31일 설치 일정 Beam Search aircontech-beam-search

TSP의 최적 비용, ORDERING의 2-opt 차분과 복구를 검증하고 실패 입력을 저장·축소합니다.

선수: 실전 C++ 제출과 검증 복잡도와 입력 크기 감각

다음: 휴리스틱 알고리즘 Proof와 Invariant

연관: 그리디 알고리즘 동적 계획법 STL 없는 공통 라이브러리

구간 합을 빠르게 구하는 누적합, 여러 구간 업데이트를 한 번에 반영하는 차분 배열, 2차원 누적합까지 익힙니다.

선수: 복잡도와 입력 크기 감각

다음: 투 포인터와 슬라이딩 윈도우 Fenwick Tree Segment Tree

연관: Sqrt Decomposition

정렬된 배열의 양끝 포인터, 조건을 만족하는 연속 구간, 빈도 관리가 필요한 슬라이딩 윈도우를 익힙니다.

선수: 정렬 알고리즘 누적합과 차분 배열

다음: 이분 탐색과 파라메트릭 서치 좌표 압축

연관: 누적합과 차분 배열

정렬된 배열에서 위치를 찾는 이분 탐색부터, 답의 범위를 줄여 가는 파라메트릭 서치까지 익힙니다.

선수: 정렬 알고리즘

다음: 좌표 압축 동적 계획법

연관: 투 포인터와 슬라이딩 윈도우

값의 범위는 크지만 서로 다른 값의 개수가 작을 때 정렬과 lower_bound로 안전한 압축 인덱스를 만드는 방법을 익힙니다.

선수: 정렬 알고리즘 이분 탐색과 파라메트릭 서치

다음: Fenwick Tree Segment Tree Sqrt Decomposition

연관: 정렬 알고리즘 Fenwick Tree

가장 크거나 작은 후보를 빠르게 꺼내는 우선순위 큐와, 이를 구현하는 힙의 원리와 실전 패턴을 익힙니다.

선수: 정렬 알고리즘

다음: Dijkstra 최단거리 Meldable Heap

연관: 그리디 알고리즘 STL 없는 공통 라이브러리

서로소 집합을 빠르게 합치고 조회하는 Union-Find의 구조와 최적화를 익힙니다.

선수: 없음

다음: 그래프와 트리 기본 성질

연관: Meldable Heap

같은 노드 pool을 공유하는 Skew Heap과 Union-Find로 컴포넌트별 후보를 병합합니다.

선수: 우선순위 큐와 힙 Union-Find 알고리즘

다음: Treap과 BST 기본

연관: 우선순위 큐와 힙

방문 표시 시점, 연결 요소와 격자 최단거리, 여러 출발점의 초기화를 BFS와 DFS로 익힙니다.

선수: 없음

다음: 0-1 BFS Dijkstra 최단거리 그래프와 트리 기본 성질

연관: 위상 정렬과 DAG DP

그래프 표현, DFS/BFS, 트리 지름, 센트로이드, 최소 신장 트리까지 문제 풀이에 자주 나오는 기본 성질을 정리합니다.

선수: BFS/DFS와 격자 탐색 Union-Find 알고리즘

다음: 트리 심화: 분할 기법 위상 정렬과 DAG DP Dijkstra 최단거리

연관: TSP와 해밀턴 경로

• 최소 신장 트리 mst-kruskal-prim

큰 문제를 겹치는 부분문제로 나누어 저장하며 푸는 동적 계획법의 상태 설계, 전이, 순회 순서와 대표 기법을 익힙니다.

선수: 누적합과 차분 배열 이분 탐색과 파라메트릭 서치

다음: TSP와 해밀턴 경로 위상 정렬과 DAG DP

연관: 그리디 알고리즘 모듈러 연산과 빠른 거듭제곱

모든 정점을 한 번씩 방문하는 해밀턴 경로와 TSP를 완전탐색, 비트마스크 DP, 휴리스틱 개선으로 연결해 익힙니다.

선수: 동적 계획법 그래프와 트리 기본 성질

다음: 휴리스틱 알고리즘

연관: 트리 심화: 분할 기법

간선 비용이 0 또는 1인 그래프에서 deque로 Dijkstra보다 가볍게 최단거리를 구하는 방법을 익힙니다.

선수: BFS/DFS와 격자 탐색

다음: Dijkstra 최단거리

연관: BFS/DFS와 격자 탐색

방향 비순환 그래프에서 의존 관계를 만족하는 순서를 만들고, 그 순서 위에서 DP를 계산하는 방법을 익힙니다.

선수: BFS/DFS와 격자 탐색 동적 계획법 우선순위 큐와 힙

다음: Dijkstra 최단거리 SCC와 2-SAT

연관: 그래프와 트리 기본 성질

음수 간선이 없는 그래프에서 한 시작점으로부터 각 정점까지의 최단거리를 구하는 Dijkstra 알고리즘을 익힙니다.

선수: BFS/DFS와 격자 탐색 우선순위 큐와 힙

다음: Bellman-Ford와 음수 사이클

연관: 그래프와 트리 기본 성질 0-1 BFS

음수 간선이 있는 그래프에서 최단거리를 계산하고, 시작점에서 도달 가능한 음수 사이클을 판정하는 Bellman-Ford 알고리즘을 익힙니다.

선수: Dijkstra 최단거리

다음: 없음

연관: 그래프와 트리 기본 성질 위상 정렬과 DAG DP 0-1 BFS

모든 정점 쌍 최단거리와 도달 가능성을 중간 정점 DP로 처리하는 Floyd-Warshall 알고리즘을 익힙니다.

선수: Dijkstra 최단거리 동적 계획법

다음: 없음

연관: Bellman-Ford와 음수 사이클 Min-Cost Flow

배열을 작은 블록으로 나누어 구간 질의와 업데이트를 균형 있게 처리하는 제곱근 분할을 익힙니다.

선수: 누적합과 차분 배열

다음: Sparse Table과 RMQ Fenwick Tree Segment Tree

연관: 좌표 압축

배열의 prefix 합을 빠르게 관리하는 Fenwick Tree의 원리와 구간 합, 점 업데이트 구현을 익힙니다.

선수: 누적합과 차분 배열 좌표 압축

다음: Segment Tree

연관: Sqrt Decomposition

배열 구간 정보를 트리로 나누어 점 업데이트, 구간 질의, lazy 구간 업데이트를 처리하는 방법을 익힙니다.

선수: 누적합과 차분 배열

다음: Versioned Data Structures Dynamic Segment Tree 트리 심화: 분할 기법 Offline and Time-Axis Techniques

연관: Fenwick Tree Sqrt Decomposition Sparse Table과 RMQ

이분 assignment 문제를 potential, reduced cost, tight edge, augmenting path로 해석하고 순수 C 배열 구현과 COUPANG2 상품별 재고 매칭 예시까지 익힙니다.

선수: 그리디 알고리즘 그래프와 트리 기본 성질

다음: Matroid Algorithms

연관: Weighted Matching Min-Cost Flow Matching과 Cover Duality

BST가 기울어지는 이유를 이해하고, Treap의 split·merge로 삽입·삭제와 순위 질의를 구현합니다.

선수: 이분 탐색과 파라메트릭 서치 정렬 알고리즘

다음: Euler Tour Tree

연관: Segment Tree 트리 심화: 분할 기법 AVL과 Splay Tree 참고

두 플레이어 game tree에서 minimax 값을 계산하고 alpha-beta pruning으로 불필요한 가지를 줄이는 방법을 익힙니다.

선수: Testing과 Stress Test

다음: Probabilistic Decision AI

연관: Proof와 Invariant 휴리스틱 알고리즘 Game Theory와 Grundy Number

이분 탐색의 답 보존, 회의 선택의 교환 논리, 격자 경로 DP의 중복 없는 전이를 설명합니다.

선수: 그리디 알고리즘 이분 탐색과 파라메트릭 서치 동적 계획법

다음: Divide and Conquer DP Optimization Knuth Optimization

연관: Testing과 Stress Test

좌표 범위가 매우 크고 실제 접근 지점이 적은 상황에서 필요한 node만 생성하는 sparse Segment Tree를 익힙니다.

선수: Segment Tree 좌표 압축

다음: 없음

연관: Versioned Data Structures Link-Cut Tree

큰 경우의 수와 곱셈을 안전하게 다루기 위한 나머지 연산, 빠른 거듭제곱, 모듈러 역원을 익힙니다.

선수: 없음

다음: 동적 계획법 조합론: nCr, 포함-배제, Lucas 정수론 심화: GCD, Extended Euclid, CRT, Sieve 문자열 매칭: KMP, Z, Rolling Hash

연관: 위상 정렬과 DAG DP

방향 그래프의 강한 연결 요소를 구하고, implication graph로 2-SAT 만족 가능성을 판정하는 방법을 익힙니다.

선수: 위상 정렬과 DAG DP

다음: Max Flow, Min Cut, Bipartite Matching

연관: Bellman-Ford와 음수 사이클 그래프와 트리 기본 성질

용량이 있는 방향 그래프에서 최대 유량을 구하고, residual graph로 min cut과 bipartite matching 모델링을 연결해 익힙니다.

선수: SCC와 2-SAT

다음: Matching과 Cover Duality Min-Cost Flow

연관: 그래프와 트리 기본 성질 우선순위 큐와 힙

이분 매칭에서 minimum vertex cover와 maximum independent set, DAG path cover로 이어지는 duality 모델링을 익힙니다.

선수: Max Flow, Min Cut, Bipartite Matching

다음: Min-Cost Flow General Matching

연관: SCC와 2-SAT 위상 정렬과 DAG DP

용량과 비용이 함께 있는 flow에서 정해진 유량을 최소 비용으로 보내는 shortest augmenting path 모델링을 익힙니다.

선수: Max Flow, Min Cut, Bipartite Matching Bellman-Ford와 음수 사이클

다음: Floyd-Warshall

연관: Dijkstra 최단거리 Matching과 Cover Duality 우선순위 큐와 힙

간선마다 최소/최대 유량 제약이 있는 flow를 feasible circulation으로 변환해 가능 여부와 확장 흐름을 판정합니다.

선수: Max Flow, Min Cut, Bipartite Matching Min-Cost Flow

다음: 없음

연관: Matching과 Cover Duality Floyd-Warshall

이분 그래프가 아닌 일반 무향 그래프에서 Edmonds blossom으로 최대 matching을 찾는 방법을 익힙니다.

선수: Matching과 Cover Duality Max Flow, Min Cut, Bipartite Matching

다음: Weighted Matching Dominator Tree

연관: Flow with Lower Bound SCC와 2-SAT

업데이트가 없는 배열에서 구간 최솟값, gcd, LCP RMQ를 빠르게 처리하는 Sparse Table을 익힙니다.

선수: Sqrt Decomposition

다음: Offline and Time-Axis Techniques

연관: Suffix and Periodicity Structures Segment Tree 트리 심화: 분할 기법

시작점에서 각 정점으로 가는 모든 경로가 반드시 지나는 immediate dominator와 dominator tree를 계산합니다.

선수: SCC와 2-SAT 그래프와 트리 기본 성질

다음: Directed MST

연관: 위상 정렬과 DAG DP General Matching

Matching에 가중치가 붙을 때 이분 assignment, small-N DP, 일반 그래프 weighted blossom의 경계를 구분합니다.

선수: General Matching Min-Cost Flow

다음: Hungarian Algorithm Directed MST Matroid Algorithms

연관: Matching과 Cover Duality Flow with Lower Bound Min-Cost Flow

루트에서 모든 정점으로 향하는 최소 비용 arborescence를 Chu-Liu/Edmonds cycle contraction으로 계산합니다.

선수: SCC와 2-SAT 그리디 알고리즘

다음: Offline and Time-Axis Techniques

연관: Min-Cost Flow Weighted Matching Dominator Tree Flow with Lower Bound

persistent segment tree, persistent DSU, versioned stack/queue, sequence query를 persistence/rollback/retroactivity 경계와 함께 정리합니다.

선수: Segment Tree Union-Find 알고리즘 좌표 압축

다음: Offline and Time-Axis Techniques Wavelet Tree

연관: Offline and Time-Axis Techniques Wavelet Matrix

• Persistent Segment Tree persistent-segment-tree
• Persistent Lazy Segment Tree persistent-lazy-segment-tree
• Persistent Union-Find persistent-union-find
• Persistent Queue and Stack persistent-queue-stack

정적 배열에서 구간 kth, rank, frequency 질의를 값 범위와 index 범위를 함께 나누어 처리하는 Wavelet Tree를 익힙니다.

선수: Versioned Data Structures 좌표 압축

다음: Wavelet Matrix Offline and Time-Axis Techniques

연관: Segment Tree Sqrt Decomposition

level별 bitvector와 rank 변환으로 정적 배열의 kth, rank, frequency 질의를 처리하는 Wavelet Matrix를 익힙니다.

선수: Wavelet Tree 좌표 압축

다음: Succinct Bitvector Offline and Time-Axis Techniques

연관: Versioned Data Structures Sparse Table과 RMQ

압축된 bit열 위에서 rank/select를 빠르게 처리하고 Wavelet Matrix의 내부 bitvector를 메모리 효율적으로 구성합니다.

선수: Wavelet Matrix 실전 C++ 제출과 검증

다음: Offline and Time-Axis Techniques

연관: Sparse Table과 RMQ 좌표 압축

트리 기본 성질 위에서 센트로이드 분할, Heavy-Light Decomposition, Euler Tour, LCA 같은 심화 도구를 연결해 익힙니다.

선수: 그래프와 트리 기본 성질 Segment Tree

다음: Treap과 BST 기본 AVL과 Splay Tree 참고 Link-Cut Tree

연관: TSP와 해밀턴 경로

Treap 이후에 참고할 균형 BST로 AVL Tree의 높이 균형과 Splay Tree의 상각 회전 패턴을 정리합니다.

선수: Treap과 BST 기본

다음: Link-Cut Tree

연관: 트리 심화: 분할 기법 Segment Tree

동적으로 변하는 forest에서 link, cut, path query를 splay 기반 preferred path로 처리합니다.

선수: 트리 심화: 분할 기법 AVL과 Splay Tree 참고

다음: Dynamic Segment Tree Offline and Time-Axis Techniques

연관: Segment Tree Versioned Data Structures Offline and Time-Axis Techniques Treap과 BST 기본

긴 텍스트에서 패턴을 빠르게 찾고 부분 문자열을 비교하기 위한 KMP, Z algorithm, rolling hash의 선택 기준과 구현을 익힙니다.

선수: 실전 C++ 제출과 검증 모듈러 연산과 빠른 거듭제곱

다음: Trie와 Aho-Corasick Suffix and Periodicity Structures

연관: 투 포인터와 슬라이딩 윈도우 정렬 알고리즘

여러 문자열을 Trie에 저장하고 실패 링크를 붙여 다중 패턴 매칭을 선형 시간에 처리하는 방법을 익힙니다.

선수: 문자열 매칭: KMP, Z, Rolling Hash BFS/DFS와 격자 탐색

다음: Suffix and Periodicity Structures

연관: 동적 계획법

Suffix Array, Suffix Automaton, Suffix Tree, runs, border automaton, period query를 문자열 구조 선택 기준으로 묶습니다.

선수: 문자열 매칭: KMP, Z, Rolling Hash Trie와 Aho-Corasick 정렬 알고리즘 Sparse Table과 RMQ

다음: Palindrome Structures Lyndon Factorization

연관: Palindrome Structures Trie와 Aho-Corasick 문자열 매칭: KMP, Z, Rolling Hash

• Suffix Array and LCP suffix-array-lcp
• Suffix Automaton suffix-automaton
• 여러 문자열의 Suffix Automaton 질의 generalized-suffix-automaton
• Suffix Tree and Ukkonen suffix-tree-ukkonen
• Runs and Periodicity runs-periodicity
• Border Automaton border-automaton

Palindromic Tree, palindrome query, range DP, suffix-palindrome 응용을 회문 문제 모델 선택 기준으로 묶습니다.

선수: 문자열 매칭: KMP, Z, Rolling Hash Suffix and Periodicity Structures 동적 계획법

다음: Lyndon Factorization Suffix and Periodicity Structures

연관: Trie와 Aho-Corasick Suffix and Periodicity Structures 문자열 매칭: KMP, Z, Rolling Hash

• Palindromic Tree palindromic-tree
• Palindrome Query Structures palindrome-query-structures
• Palindrome Range DP palindrome-range-dp

Lyndon word의 성질과 Duval algorithm을 이용해 문자열을 선형 시간에 분해하고 최소 회전으로 연결합니다.

선수: Palindrome Structures 문자열 매칭: KMP, Z, Rolling Hash

다음: Suffix and Periodicity Structures

연관: Suffix and Periodicity Structures

정수 좌표에서 외적 부호로 방향을 판정하고, 선분 교차와 convex hull을 안정적으로 구현하는 기하 기본기를 익힙니다.

선수: 정렬 알고리즘 실전 C++ 제출과 검증

다음: Rotating Calipers

연관: 복잡도와 입력 크기 감각

볼록 hull 위 포인터를 전진시키며 지름과 최소 폭을 구하고 지지선·접선·직사각형으로 연결합니다.

선수: 기하 기본: CCW, 선분 교차, Convex Hull

다음: Minkowski Sum Sweep Line Geometry

연관: 투 포인터와 슬라이딩 윈도우

기하 이벤트를 한 축으로 정렬하고 active set 또는 구간 자료구조로 직사각형 넓이와 교차 판정을 처리합니다.

선수: 기하 기본: CCW, 선분 교차, Convex Hull Segment Tree

다음: Closest Pair Sweep

연관: Rotating Calipers 투 포인터와 슬라이딩 윈도우

평면 점을 x좌표로 훑으며 active set의 y범위 후보만 검사해 가장 가까운 두 점을 찾습니다.

선수: Sweep Line Geometry 기하 기본: CCW, 선분 교차, Convex Hull

다음: Line Arrangement

연관: Rotating Calipers

직선의 중복, 평행, 교점을 정확히 다루며 arrangement 영역 수와 sweep 확장 관점을 익힙니다.

선수: Sweep Line Geometry Closest Pair Sweep

다음: Voronoi와 Delaunay

연관: 기하 기본: CCW, 선분 교차, Convex Hull Rotating Calipers

Voronoi cell과 Delaunay edge의 쌍대 관계, empty circumcircle 성질, nearest 구조 문제의 활용 기준을 익힙니다.

선수: Line Arrangement Closest Pair Sweep

다음: Half-Plane Intersection Geometry Robustness and Duality

연관: 기하 기본: CCW, 선분 교차, Convex Hull Rotating Calipers

주어진 볼록 영역을 반평면으로 자르는 구현과 각도 정렬 deque의 적용 범위를 구분합니다.

선수: Line Arrangement Voronoi와 Delaunay

다음: Minkowski Sum

연관: 기하 기본: CCW, 선분 교차, Convex Hull Sweep Line Geometry Line Arrangement

gcd, 확장 유클리드 알고리즘, 일반 모듈러 역원, CRT, 최소 소인수 전처리로 정수론 문제를 확장해 풉니다.

선수: 모듈러 연산과 빠른 거듭제곱

다음: 조합론: nCr, 포함-배제, Lucas

연관: 복잡도와 입력 크기 감각

모듈러 조합 계산, 포함-배제, Lucas 정리로 경우의 수 문제를 체계적으로 세는 방법을 익힙니다.

선수: 모듈러 연산과 빠른 거듭제곱

다음: Matrix Exponentiation Polynomial and Recurrence Algorithms 확률과 기대값 Game Theory와 Grundy Number

연관: 정수론 심화: GCD, Extended Euclid, CRT, Sieve 동적 계획법

선형 점화식과 상태 전이를 행렬로 만들고 빠른 거듭제곱으로 큰 반복 횟수를 처리합니다.

선수: 모듈러 연산과 빠른 거듭제곱 동적 계획법 조합론: nCr, 포함-배제, Lucas

다음: Polynomial and Recurrence Algorithms

연관: 정수론 심화: GCD, Extended Euclid, CRT, Sieve 위상 정렬과 DAG DP

FFT/NTT, FPS, 다점평가, 보간, 생성함수, Kitamasa, Bostan-Mori, Berlekamp-Massey를 계수열 알고리즘 흐름으로 묶습니다.

선수: 모듈러 연산과 빠른 거듭제곱 조합론: nCr, 포함-배제, Lucas Matrix Exponentiation

다음: Black-Box Linear Algebra Linear Algebra Applications Sparse Linear Systems

연관: 정수론 심화: GCD, Extended Euclid, CRT, Sieve Convex DP Optimization Randomized Determinant

• FFT and NTT fft-ntt
• Formal Power Series formal-power-series
• Multipoint Evaluation multipoint-evaluation
• Polynomial Interpolation polynomial-interpolation
• Generating Function Modeling generating-function-modeling
• Linear Recurrence and Kitamasa linear-recurrence-kitamasa
• Bostan-Mori bostan-mori
• Berlekamp–Massey: 점화식 추정과 검증 berlekamp-massey

확률 분포와 기대값 DP를 세우고, DAG 전이와 순환 전이, 모듈러 확률 처리를 구분해 익힙니다.

선수: 동적 계획법 모듈러 연산과 빠른 거듭제곱 조합론: nCr, 포함-배제, Lucas

다음: Game Theory와 Grundy Number Probabilistic Decision AI

연관: Matrix Exponentiation Testing과 Stress Test

Impartial game에서 win/lose DP와 Grundy number를 계산하고, 여러 독립 게임의 xor 합성으로 승패를 판정합니다.

선수: 동적 계획법 Proof와 Invariant

다음: Minimax와 Alpha-Beta Pruning Game Theory Applications

연관: 확률과 기대값 Testing과 Stress Test

MDP, MCTS, imperfect information, POMDP, PBVI, POMCP, Bayesian Bandits, online planning evaluation을 reference 트랙으로 묶습니다.

선수: 확률과 기대값 동적 계획법 Minimax와 Alpha-Beta Pruning 휴리스틱 알고리즘

다음: Game Theory Applications Online Convex Optimization Testing과 Stress Test

연관: Game Theory와 Grundy Number Sparse Linear Systems Black-Box Linear Algebra

• MDP: 유한 지평, 할인과 정책 반복 finite-horizon-mdp
• Stochastic Shortest Path stochastic-shortest-path
• Monte Carlo Tree Search monte-carlo-tree-search
• Imperfect Information Search imperfect-information-search
• Partially Observable MDP pomdp
• Point-Based Value Iteration point-based-value-iteration
• POMCP pomcp
• Bayesian Bandits bayesian-bandits
• Online Planning Evaluation online-planning-evaluation

Mo, offline sorting, parallel binary search, rollback, time segment tree, dynamic connectivity, retroactivity를 시간축 모델 선택 기준으로 묶습니다.

선수: Sqrt Decomposition Union-Find 알고리즘 Segment Tree 이분 탐색과 파라메트릭 서치

다음: Versioned Data Structures Dynamic Network Optimization Link-Cut Tree

연관: Fenwick Tree Segment Tree Versioned Data Structures Euler Tour Tree Dynamic Network Optimization

• Parallel Binary Search offline-queries
• Offline Range Query Techniques offline-range-query-techniques
• Rollback Techniques rollback-techniques
• Dynamic Connectivity dynamic-connectivity
• Retroactive Data Structures retroactive-data-structures

최적 분할점 단조성을 이용해 layer DP의 후보 범위를 줄이는 divide-and-conquer DP optimization을 익힙니다.

선수: 동적 계획법 Proof와 Invariant

다음: Knuth Optimization Monge와 SMAWK

연관: Convex DP Optimization 확률과 기대값

Interval DP에서 최적 분할점의 단조 범위를 이용해 `O(N^3)` 전이를 `O(N^2)`로 줄이는 Knuth Optimization을 익힙니다.

선수: 동적 계획법 Proof와 Invariant

다음: Monge와 SMAWK

연관: Divide and Conquer DP Optimization

Monge array와 totally monotone matrix의 row minimum 단조성을 이용해 SMAWK와 monotone optimization을 이해합니다.

선수: Divide and Conquer DP Optimization Knuth Optimization

다음: Parametric Optimization Knuth Optimization

연관: Convex DP Optimization

Alien Optimization, Parametric DP, fractional objectives, Lagrangian relaxation을 하나의 parameter 기반 최적화 흐름으로 묶어 선택 기준과 구현 함정을 정리합니다.

선수: 이분 탐색과 파라메트릭 서치 동적 계획법 Divide and Conquer DP Optimization Monge와 SMAWK

다음: Online Convex Optimization Convex Cost Flow

연관: Convex DP Optimization Flow with Lower Bound

• Fractional Objectives fractional-objectives
• General Lagrangian Relaxation general-lagrangian-relaxation

XOR 기저를 만들고 표현 가능성·최댓값·k번째 값·그래프 cycle과 구간 질의로 이어갑니다.

선수: 모듈러 연산과 빠른 거듭제곱 Proof와 Invariant Polynomial and Recurrence Algorithms

다음: 없음

연관: 조합론: nCr, 포함-배제, Lucas Game Theory와 Grundy Number

CHT, Li Chao Tree, Slope Trick, Min-Plus Convolution, Kinetic/Fully Dynamic Hull을 DP 전이식 선택 기준으로 묶습니다.

선수: 동적 계획법 Segment Tree Divide and Conquer DP Optimization

다음: Convex Cost Flow Offline and Time-Axis Techniques

연관: Monge와 SMAWK Parametric Optimization Versioned Data Structures Geometry Robustness and Duality

• Convex Hull Trick과 Li Chao Tree convex-hull-trick-li-chao
• Slope Trick slope-trick
• Min-Plus Convolution min-plus-convolution
• Kinetic Hull kinetic-hull
• Fully Dynamic CHT fully-dynamic-cht

s-t min cut 이후의 global min cut, Gomory-Hu Tree, sparsification, randomized contraction, cactus cut family를 하나의 흐름으로 정리합니다.

선수: Max Flow, Min Cut, Bipartite Matching Flow with Lower Bound

다음: Offline and Time-Axis Techniques Planar Graph Duality

연관: Proof와 Invariant Dynamic Network Optimization Planar Graph Duality

• Global Min Cut global-min-cut
• Randomized Min Cut randomized-min-cut
• Gomory-Hu Tree gomory-hu-tree
• Cut Sparsification cut-sparsification
• Cactus Representation cactus-representation

dynamic forest를 Euler tour sequence와 balanced binary tree로 표현해 online link, cut, connectivity를 처리합니다.

선수: Link-Cut Tree Offline and Time-Axis Techniques 트리 심화: 분할 기법

다음: Versioned Data Structures

연관: Union-Find 알고리즘 Offline and Time-Axis Techniques

Mobius function으로 약수 합 관계를 되돌리고 gcd, 서로소 pair, divisor transform 문제를 포함-배제로 처리합니다.

선수: 정수론 심화: GCD, Extended Euclid, CRT, Sieve 조합론: nCr, 포함-배제, Lucas

다음: Dirichlet Convolution

연관: XOR Linear Basis Proof와 Invariant

사용량이 늘수록 marginal cost가 증가하는 비용을 edge split으로 표현해 Min-Cost Flow 모델에 결합합니다.

선수: Min-Cost Flow Convex DP Optimization Parametric Optimization

다음: Convex DP Optimization

연관: Convex DP Optimization Flow with Lower Bound

Dynamic Flow, Dynamic MST, offline time-axis, rebuild, residual reuse, cut/cycle property를 하나의 동적 그래프 최적화 선택 흐름으로 묶습니다.

선수: Max Flow, Min Cut, Bipartite Matching Min-Cost Flow 그래프와 트리 기본 성질 Offline and Time-Axis Techniques

다음: Link-Cut Tree Euler Tour Tree

연관: Graph Cut Structures Flow with Lower Bound Versioned Data Structures Planar Graph Duality

• Dynamic Flow dynamic-flow
• Dynamic MST dynamic-mst

약수 관계 위 convolution으로 Mobius Inversion, multiplicative function, divisor transform을 하나의 틀에서 정리합니다.

선수: Mobius Inversion 정수론 심화: GCD, Extended Euclid, CRT, Sieve 조합론: nCr, 포함-배제, Lucas

다음: Multiplicative Functions

연관: 모듈러 연산과 빠른 거듭제곱 XOR Linear Basis

두 convex polygon의 모든 점 합을 edge vector merge로 계산하고 충돌 판정과 거리 모델링으로 연결합니다.

선수: Rotating Calipers Half-Plane Intersection 기하 기본: CCW, 선분 교차, Convex Hull

다음: Rotating Calipers Shape Distance Modeling

연관: Sweep Line Geometry Voronoi와 Delaunay

서로소 곱에서 값이 분리되는 산술 함수를 prime power 공식과 linear sieve로 계산합니다.

선수: Dirichlet Convolution Mobius Inversion 정수론 심화: GCD, Extended Euclid, CRT, Sieve

다음: Summatory Number Theory

연관: 모듈러 연산과 빠른 거듭제곱 조합론: nCr, 포함-배제, Lucas

floor division grouping과 divisor transform으로 큰 n의 정수론 누적합을 빠르게 계산하는 관점을 익힙니다.

선수: Multiplicative Functions Mobius Inversion Dirichlet Convolution

다음: 없음

연관: 정수론 심화: GCD, Extended Euclid, CRT, Sieve 조합론: nCr, 포함-배제, Lucas

Minkowski difference, support function, separating axis로 도형 거리와 충돌 문제를 모델링하는 법을 익힙니다.

선수: Minkowski Sum Rotating Calipers 기하 기본: CCW, 선분 교차, Convex Hull

다음: Circle Geometry

연관: Half-Plane Intersection Sweep Line Geometry Voronoi와 Delaunay

원-직선, 원-원 교점과 접선 construction, 각도 구간 sweep의 case 분기를 익힙니다.

선수: Shape Distance Modeling 기하 기본: CCW, 선분 교차, Convex Hull Closest Pair Sweep

다음: Circle Arrangement Geometry Robustness and Duality Inversion Geometry

연관: Voronoi와 Delaunay Sweep Line Geometry

여러 원의 교점으로 arc를 나누고 union area, perimeter, depth를 angular sweep으로 계산합니다.

선수: Circle Geometry Sweep Line Geometry Shape Distance Modeling

다음: 없음

연관: Half-Plane Intersection Voronoi와 Delaunay

Robust predicate, Power Diagram, Robust Delaunay, 3D Convex Hull, Regular Triangulation을 계산기하 안정성과 duality 흐름으로 묶습니다.

선수: 기하 기본: CCW, 선분 교차, Convex Hull Circle Geometry Sweep Line Geometry Half-Plane Intersection

다음: Voronoi와 Delaunay Planar Graph Duality

연관: Shape Distance Modeling Circle Arrangement Inversion Geometry

• Robust Geometry Predicates robust-geometry-predicates
• Power Diagram power-diagram
• Robust Delaunay robust-delaunay
• 3D Convex Hull 3d-convex-hull
• Regular Triangulation regular-triangulation

Sparse matrix-vector product만으로 Krylov sequence와 Wiedemann 계열 선형대수 모델을 다룹니다.

선수: Polynomial and Recurrence Algorithms 모듈러 연산과 빠른 거듭제곱

다음: Sparse Linear Systems Linear Algebra Applications

연관: Matrix Exponentiation Polynomial and Recurrence Algorithms

Grundy, minimax, MDP, hidden information 모델을 문제 신호별로 고르는 게임 이론 응용 기준을 정리합니다.

선수: Game Theory와 Grundy Number Minimax와 Alpha-Beta Pruning Probabilistic Decision AI

다음: Probabilistic Decision AI

연관: Probabilistic Decision AI

원과 직선을 inversion으로 변환해 접선, 교점, 원다발 문제를 단순화하는 기하 모델링을 익힙니다.

선수: Circle Geometry Geometry Robustness and Duality Shape Distance Modeling

다음: 없음

연관: Circle Arrangement Voronoi와 Delaunay Half-Plane Intersection

Matroid greedy, exchange, intersection, union, parity를 구현 완성도별 reference 트랙으로 정리합니다.

선수: General Matching Weighted Matching XOR Linear Basis Proof와 Invariant

다음: Randomized Determinant Sparse Linear Systems

연관: Linear Algebra Applications Max Flow, Min Cut, Bipartite Matching Proof와 Invariant

• Matroid Basics and Exchange matroid-basics-and-exchange
• Matroid Intersection matroid-intersection
• Matroid Union matroid-union
• Matroid Parity matroid-parity

대부분의 계수가 0인 큰 연립방정식에서 sparse row, matvec oracle, rank consistency를 구분해 풉니다.

선수: Black-Box Linear Algebra 모듈러 연산과 빠른 거듭제곱 Matrix Exponentiation

다음: Linear Algebra Applications

연관: Polynomial and Recurrence Algorithms Summatory Number Theory

rank, determinant, xor basis, sparse solver, recurrence, graph counting을 먼저 선택표로 구분한 뒤 vector space 모델로 번역하는 선형대수 모델링 허브입니다.

선수: XOR Linear Basis Sparse Linear Systems Black-Box Linear Algebra

다음: Randomized Determinant Matrix-Tree Theorem Applications

연관: XOR Linear Basis Polynomial and Recurrence Algorithms Matroid Algorithms Matrix Exponentiation

regret minimization, projected gradient descent, mirror descent, dual averaging을 하나의 online optimization 흐름으로 정리합니다.

선수: Convex DP Optimization 확률과 기대값

다음: Probabilistic Decision AI

연관: Parametric Optimization Probabilistic Decision AI Convex DP Optimization

• Online Decision and Regret online-decision-and-regret
• Mirror Descent and Multiplicative Weights mirror-descent-and-multiplicative-weights
• Dual Averaging dual-averaging

determinant polynomial에 무작위 값을 대입해 rank, matching 존재성, polynomial identity를 확률적으로 판정합니다.

선수: Black-Box Linear Algebra 모듈러 연산과 빠른 거듭제곱 확률과 기대값

다음: Matrix-Tree Theorem Applications

연관: General Matching Linear Algebra Applications Testing과 Stress Test

Laplacian cofactor determinant로 spanning tree, rooted arborescence, edge 포함 조건을 계산합니다.

선수: 그래프와 트리 기본 성질 모듈러 연산과 빠른 거듭제곱 Randomized Determinant

다음: 없음

연관: Linear Algebra Applications Sparse Linear Systems Proof와 Invariant

평면 그래프의 half-edge face traversal, dual graph 구성, cut-cycle duality, planar min-cut 변환을 정리합니다.

선수: 그래프와 트리 기본 성질 Max Flow, Min Cut, Bipartite Matching 기하 기본: CCW, 선분 교차, Convex Hull

다음: 없음

연관: Sweep Line Geometry Matrix-Tree Theorem Applications Graph Cut Structures

• Face 순회와 Dual Graph 구성 half-edge-and-face-traversal
• Cut-Cycle Duality cut-cycle-duality