애니메이션

크누스 최적화로 구간 DP O(N^3) -> O(N^2). DP 테이블을 구간 길이 순으로 채우며, 각 dp[i][j]의 k 탐색 범위를 opt[i][j-1] <= k <= opt[i+1][j] 로 제한한다.

4x4 0-1 행렬에서 모든 열을 정확히 한 번 커버하는 행 집합을 backtracking 으로 탐색. 선택된 행(초록)과 제거된 열/행(회색)을 표시. Dancing Links 로 O(1) cover/uncover.

6 정점 / 8 간선의 가중 그래프에서 가중치 정렬 + Union-Find 로 사이클 없는 최소 신장 트리 구축

A=ABCD, B=ACBD의 LCS. dp[i][j] = A[0..i-1]과 B[0..j-1]의 LCS 길이. 최종 dp[4][4]=3 (ACB 또는 ACD).

2x2 격자에서 시작점 (0,0), (0,1) 에서 끝점 (2,0), (2,1) 로 가는 non-intersecting path 개수 = det(M).

동적 CHT, 직선 추가 후 x 좌표의 최솟값 쿼리 O(log N)

두 선분 A(1,1)-B(7,3) 와 C(2,4)-D(6,1) 의 교차 판정. CCW(a,b,c)?CCW(a,b,d) < 0 and CCW(c,d,a)?CCW(c,d,b) < 0.

기댓값 선형성: 독립이 아니어도 E[X+Y] = E[X] + E[Y] 항상 성립

LinkedHashMap 의 doubly-linked list 가 삽입 순서를 유지하고, accessOrder=true 일 때 get/put 마다 노드가 tail 로 이동해 LRU 캐시를 구현한다.

양방향 연결 리스트의 addFirst, addLast, get(인덱스 탐색), remove 가 노드 포인터를 어떻게 바꾸는지 보여준다.

O(N log N) binary search approach: maintain tail array of minimum ending values for each length

get, set, add, remove 네 가지 핵심 연산이 인덱스 기반 List 에서 어떻게 동작하는지 추상화된 셀로 시각화한다.

PUT(A), PUT(B), PUT(C), GET(A), PUT(D), D 삽입 시 가장 오래된 B 가 evict

Lifting The Exponent lemma. v_p(a^n - b^n) = v_p(a-b) + v_p(n) when p|a-b, p not|a, p not|b.

n=7, r=3, p=5 에 대해 Lucas 정리로 nCr mod p 계산. 각 p진수 자릿수 조합의 곱.

Graphic matroid (3 간선, forest) 과 partition matroid (3 색, 각 색 최대 1 개) 의 교집합으로 최대 독립 집합 찾기.

O(N) greedy/DP approach: discard negative prefix, keep positive cumulative sum

세그먼트 트리 각 노드에 정렬된 배열 저장, 구간 내 k 이상 개수 쿼리

배열을 반으로 나눠 각각 정렬한 뒤 합친다. 항상 O(n log n) 보장, 안정 정렬.

5개 점에 대한 최소 외접원 탐색. 무작위 순서로 점을 추가하며 원 밖의 점을 경계에 편입. 최종 원은 3개 support point 로 결정.

N=6 배열을 N/2=3 씩 분할. 각각 모든 부분집합 합(8개) 열거 후 정렬, 이분 탐색으로 target 조합.

8개 원소 배열, 3개 쿼리. L,R 포인터가 블록 정렬 순서로 움직이며 구간 정보 갱신, O((N+Q)√N)

P(x) = x³ + 2x + 1을 {1,2,3,4}에서 평가. 평가점 세그먼트 트리 구축, P mod 각 subtree poly로 차수 절반씩 감소, 리프에서 상수 추출.

간선이 시간 순서로 추가되는 유향 그래프에서 두 정점이 같은 SCC 에 속한 최초 시각을 병렬 이분탐색으로 O((N+M) log T) 에 해결. 같은 mid 를 가진 쿼리들을 묶어 한 번의 SCC 판정으로 모두 처리.