그냥 자주 나오는 것들


(1) 이산수학

a^b mod p 빠르게 구하기

모듈러 인버스 (Extended GCD 또는 위의 트릭과 페르마 소정리 이용)

n C r 빠르게 구하기

ax + by = c의 해 오버플로우 걱정없이 구하기

gcd, lcm

소수 구하기, 소수 판별, 소인수분해

중국인의 나머지 정리 (CRT)

조합, 중복조합, 등등


(2) 자료구조

맵, 셋, 힙, 큐, 해시맵

세그먼트 트리 (with lazy propagation)

펜윅 트리

Union find (Disjoint set 이라고도 부름)

BBST (Treap이나 Splay tree처럼 merge split 효율적으로 구현되는 것이 좋음)


(3) 알고리즘

정렬

최단거리 (다익스트라, 플로이드, SPFA)

네트워크 플로우(+ Min-cut, Minimum vertex cover, Maximum indepedent set 등으로 변형되서 나옴)

이분탐색, 삼분탐색

투 포인터

그래프와 DFS


(4) 아이디어

파라메트릭 => 답이 되는 것 중에서 최대 or 최소를 찾을 때 이용

DP => 부분문제에서 큰 문제를 쉽게 해결할 수 있는가?

반복되는 연산을 줄일 수 있는가? -> 전처리 가능?

Sqrt로 나누어서 해결할 수 있는가?

특이한 성질이 있어서 모든 경우를 계산할 필요가 없는가?

입력의 범위를 나누어서 각자 다른 알고리즘으로 해결할 수 있는가?