애니메이션

P(A|B) = P(B|A) * P(A) / P(B). Prior=1%, Likelihood=99%, FalsePos=1%. Posterior = 50%.

키는 BST 순서, priority 는 heap 순서를 동시 유지. split(t, k) 와 merge(a, b) 로 구간 연산 O(log N).

주어진 수열의 최단 선형 점화식을 O(N²)에 복원. 각 step마다 discrepancy 계산, 불일치시 이전 실패 점화식과 결합해 차수 갱신.

Allison-Dix bitset LCS. A=ABC, B=AC 에서 cur/u/v 의 비트셋 변화. (u - v) & ~u 로 한 번에 DP 전이.

불린 행렬곱을 비트 연산으로 가속화하는 방법을 시각화합니다. 4x4 행렬을 한 번에 한 비트씩 처리하는 대신 bitset으로 4비트를 동시에 처리합니다.

[5, 2, 8, 1, 4] 를 정렬하는 모든 pass 의 비교와 swap 을 명확히 시각화. 비교 중인 두 원소는 노란색, 정렬 완료된 원소는 녹색으로 표시.

평면 위 점들을 직선에 정사영하면서 회전, 정사영 순서가 바뀌는 순간 = 이벤트 발생, O(n² log n)

x 정렬 후 y merge + z Fenwick, 왼쪽 점이 오른쪽 점에 기여, O(N log² N)

모든 4-cycle 이상이 chord 를 가지는 그래프. MCS (Maximum Cardinality Search) 로 정점을 뽑으며 각 단계에서 이웃들이 클리크를 이루면 PEO. max clique, chromatic, max independent set 모두 O(V+E) 에 해결.

Skip List 의 다단계 link 가 정렬된 키 안에서 빠른 검색을 가능하게 하고, 동시 수정 시 lock-free CAS 로 갱신되는 원리.

3 직선의 lower envelope. 새 직선이 기존 직선을 영구히 가리면 pop. 쿼리 시 envelope 위 이분 탐색.

9개 점의 볼록 껍질을 Andrew monotone chain O(N log N) 으로 구성. Lower hull (blue) + Upper hull (purple).

목적 함수가 볼록한 제약 집합과 접하는 지점이 최적해. 접선 조건으로 빠르게 찾는다.

4x4 0-1 행렬의 DLX 구조. cover(c1) 으로 c1 열과 r1/r4 행 제거 후 uncover 역순 복원.

슬라이딩 윈도우 최댓값. 덱에 인덱스를 단조 내림차순으로 유지하며 O(N) 에 각 윈도우의 최댓값을 구한다. 새 원소가 들어올 때 작은 값은 pop_back, 윈도우 이탈 인덱스는 pop_front.

4개 정점 그래프, maxW=5. s=0 시작. 버킷 배열로 extract-min O(1).

루트 r 에서 모든 정점으로 도달 가능한 최소 비용 간선 집합 (arborescence). 사이클이 생기면 contract 후 재귀로 해결.

분할정복 DP 최적화. dp[k][i] = min(dp[k-1][j] + cost(j+1, i)) 에서 opt[i] 단조성을 이용, 각 레이어를 O(N log N) 에 채운다. mid 의 최적 분할점을 찾고 좌/우 재귀.

출발점 s 에서 정점 v 로 가는 모든 경로가 반드시 지나는 정점 (dominator) 을 찾아 immediate dominator 를 부모로 하는 트리를 만든다.

LCS 문자열 "ABC" 와 "ACB" 의 DP 표를 채우고 parent 배열을 따라 traceback 으로 LCS "AB" 또는 "AC" 를 복원.

평면 그래프의 쌍대로 가면 min-cut 이 shortest path 가 된다. 면을 정점으로, 면 공유 간선을 dual 간선으로 변환하면 O(V² E) 흐름을 O((V+E) log V) 다익스트라로 해결.

Link/Cut Tree 는 트리에 간선 추가/제거가 섞여도 경로 집계를 O(log N) 에 처리. Preferred path 를 splay tree 로 유지.

유클리드 호제법으로 GCD 구하고, 확장 유클리드로 모듈러 역원 계산.

오일러 지표 χ = V - E + F. 볼록 다면체는 항상 χ=2, 위상 불변량으로 다면체를 분류.