<style> .bronze { background-color:#CE8946 } .silver { background-color:#C5D5D5 } .gold { background-color:#FFF5B1 } .platinum { background-color:#DCFFE4 } .diamond { background-color:#C0FFFF } .ruby { background-color:#FFC0C0 } .additional { background-color:#E4BBFE } .information { background-color:#ABCDEF } </style>

time complexity

constraints	time complexity	algorithm
$n \le 12$	$O(n!)$
$n \le 25$	$O(2^n)$, $O(n^2 \cdot 2^n)$
$n \le 50$	$O(\sqrt2^n)$
$n \le 100$	$O(n^4)$
$n \le 500$	$O(n^3)$
$n \le 2,000$	$O(n^2 \log{n})$, $O(\dfrac{n^3}{16})$	SIMD
$n \le 5,000$	$O(n^2)$
$n \le 50,000$	$O(\dfrac{n^2}{64})$
$n \le 100,000$	$O(n \sqrt n)$, $O(n \log^2n)$	bitset
$n \le 1,000,000$	$O(n \log n)$
$n \le 5,000,000$	$O(n \log n)$
$n \le 100,000,000$	$O(n)$
$n \gt 10^8 $	$O(logn)$, $O(1)$

ps algorithm

티어 분류 : 실버(S) 골드(G) 플레(P) 다이아(D) 루비(R) 기타(A)

• 자료구조

  자료구조 구현할 때 주의사항

  • 세그먼트 트리

    • 펜윅 트리(G+)
    • 세그먼트 트리(G+), 세그 이분 탐색(P-)
    • 2D 세그(P-)
    • 다차원 펜윅(P-)
    • 머지소트 트리(P-)
    • 레이지 세그(P-)
    • 다이나믹 세그(P-)
    • 다이나믹 레이지 세그(P+)
    • GCD 세그(P+)
    • 금광 세그(최대 연속 부분합 세그)(P+)
    • [퍼시스턴트 세그(P+)]
    • [세그트리비츠(D+)]
    • [Kinetic Segment Tree]

  • BBST

    • [treap]
    • 스플레이 트리(D-)
    • [Persistent BBST, Weight-Balanced Tree]
    • [레드-블랙 트리]

  • 기타

    • DSU(유니온 파인드)(G-)
    • [유니온 파인드 롤백]
    • Erasable Priority Queue(G)
    • [meldable pq]
    • [amortized 시간복잡도, 자료구조 롤백 지원하기]
    • 희소 배열(G+)
    • Small To Large(작은 집합에서 큰 집합으로 합치는 테크닉) (P-)
    • XOR 트라이(P-)
    • 유니온 파인드 with Potential(P+)
    • 로프(P-)
    • ordered set(P-)
    • [wavelet 트리]
    • [데카르트 트리(Cartesian tree)]
    • [Farach-Colton and Bender Algorithm]
    • Line Container(D-)
    • [리-차오 트리(D-)]
    • [Persistent Convex Hull(D+)]
    • [SPQR tree]
    • [PQ tree]

• 그래프 이론

  • 그래프

    • [flood fill]
    • [0-1 bfs(G-)]
    • 이분그래프 판정(G-)
    • 다익스트라(G-)
    • [dial's algorithm]
    • [A*]
    • 벨만-포드(G-)
    • SPFA(G-)
    • 플로이드 워셜(G-)
    • 최소 스패닝 트리: Kruskal(G-)
    • [최소 스패닝 트리: Prim(G-)]
    • [최소 스패닝 트리: Borůvka]
    • 정점 착색수(G+)
    • [간선 착색수]
    • 위상정렬(G+)
    • [kth 최단 경로]
    • 오일러 회로(P-)
    • SCC(강한 연결 요소) (P-)
    • 2-SAT(P-)
    • 단절점(P-)
    • 단절선(P-)
    • BCC(이중 연결 요소) (P-)
    • 선인장(P+)
    • [블록 컷 트리]
    • [Dynamic MST]
    • [2th MST(D-)]
    • [쌍대 그래프(D-)]
    • [그래프 채색]
    • [도미네이터 트리]
    • [오프라인 동적 연결성 판정]
    • [3-cycles 찾기]
    • [평면 그래프]
    • [쌍대 그래프]
    • [현 그래프 판정]
    • [현 그래프(D+)]
    • [Perfect Elimination Ordering]
    • 유향 MST(D+)
    • offline incremental SCC(R-)
    • [온라인 동적 연결성 판정(R+)]

  • 네트워크 플로우

    • 이분 매칭(P-)
    • 최대유량: Edmonds-Karp (P-)
    • 최대유량: Dinic (P-)
    • 이분 매칭: Hopcraft-Karp(P-)
    • [최대유량: Push-Relabel (P-)]
    • 최소 비용 최대 유량(P+)
    • [zkw mcmf]
    • 서큘레이션, L-R flow(D-)
    • 헝가리안(D-)
    • [일반 매칭(D+)]
    • [Stoer-Wagner Algorithm(스토어-바그너)]
    • [Gomory-Hu Tree]

  • 트리

    • LCA(최소 공통 조상) (P-)
    • [O(1) LCA]
    • LCA를 이용한 트리 쿼리(P-)
    • ETT(오일러 경로 테크닉) (P-)
    • HLD(heavy-light 분할) (P+)
    • 센트로이드(P-)
    • [트리 압축]
    • [센트로이드 분할(D-)]
    • [트리 동형 사상]
    • [tree width]
    • 링크/컷 트리(D+)
    • [탑 트리(R-)]

• DP

  • Kadane algorithm(S+)
  • LIS(S+)
  • LCS(G-)
  • 동전 교환 문제(G-)
  • 배낭문제(G-)
    • 0-1 Knapsack(G-)
    • Unbounded Knapsack(G-)
    • Bounded Knapsack(Binary Splitting) (P-)
    • 비트셋 배낭(P-)
    • O(W sqrt(W)) 비트셋 배낭(D-)
  • 최단거리 역추적(G-)
  • 달걀 낙하(G+)
  • 비트마스크 DP(G+)
  • digit DP(G+)
  • Valid Permutations for DI Sequence(P-)
  • Hall DP
  • O(NlogN) The Ultimate Reroot Template
  • O(N) Rerooting
  • 괄호 문자열(P-)
  • [bitonic tour]
  • 토글링(P-)
  • 볼록 껍질을 이용한 최적화(P+)
  • 분할 정복을 이용한 최적화(P+)
  • SOS DP(D-)
  • [검은 돌 트릭]
  • [히르쉬버그(D+)]
  • [aliens 트릭]
  • [Connection Profile DP]
  • [크누스 최적화]
  • [단조 큐를 이용한 최적화]
  • [함수 개형을 이용한 최적화(Slope trick) (D-)]
  • [aliens 트릭(라그랑주 최적화)]
  • [SMAWK]
  • [벌레캠프-매시(D+)]
  • [커넥션 프로파일을 이용한 다이나믹 프로그래밍]
  • 비트셋 LCS(R-)

• 그리디

  • 저울문제(G+)
  • [그리디 알고리즘의 증명]
  • [exchange arguement]

• 문자열

  • [괄호문자열]
  • 트라이(G+)
  • 매내처(P-)
  • z(P-)
  • 롤링 해시(P-)
  • 라빈 카프(P-)
  • KMP(P-)
  • 아호 코라식(P+)
  • [bitap algorithm]
  • 접미사 배열과 lcp 배열(P+)
  • [LCE]
  • [Lyndon Factorization(Duval algorithm)]
  • [Z algorithm]
  • [와일드카드 문자열 매칭]
  • 회문 트리(D+)
  • [run enumerate(R-)]
  • [접미사 트리(R-)]
  • [suffix automaton]

• 기하학

  • 기하학 헤더
    • 외적, CCW(G-)
    • 거리 계산 : point-point, line-point
    • 넓이 계산 : 단순다각형, 헤론, 브라마굽타, 활꼴
    • 점-직선 포함여부 판정
    • 제2 cos
    • 삼각함수 합성
    • 좌표 계산 : 수선의 발, 대칭이동, 회전이동
    • 좌표 계산 : 오심 좌표
  • 볼록다각형 부분넓이(G)
  • 선분교차판정(G+)
  • 각도 정렬(G+)
  • 선분교차점 계산(P-)
  • 볼록 껍질:Graham Scan(P-)
  • 볼록 껍질:Monotone Chain(P-)
  • 가장 먼 두 점 : 회전하는 캘리퍼스(P-)
  • plane sweeping(P-)
  • [radial sweeping]
  • [point location in planar subdivision]
  • 다각형 내부의 점 판정(P-)
  • 볼록 다각형 내부의 점 판정(P+)
  • 등적등주 분할(P+)
  • 가장 가까운 두 점(P+)
  • 최소 외접원(P+)
  • [Shamos-Hoey]
  • 반평면 교집합(D-)
  • [Bentley-Ottmann]
  • 점-볼록다각형 접선(D-)
  • [볼록다각형-볼록다각형 접선]
  • [점-원 접선, 원-원 접선]
  • [Dynamic Convex Hull]
  • [Convex Layers]
  • [구분구적법]
  • [심슨 적분]
  • 불도저 트릭(Rotating Line Sweep)(D+)
  • [KD tree]
  • [Polygon Clipping]
  • 그린 정리(D+)
  • 도형에서의 불 연산: Circle Union(D+)
  • 도형에서의 불 연산: Ring Union(D+)
  • [도형에서의 불 연산: Polygon Union]
  • [델로네 삼각분할, 보로노이 다이어그램(D+)]
  • [Euclidean MST]
  • 3차원 기하학 헤더
    • 외적, 면 법선 벡터 계산
    • 거리 : point-face
    • 좌표 계산 : 회전이동
  • 3D Convex Hull(D+)
  • [Disk Convex Hull(R)]

• 수학

  • 조합론, 수열

    • 이항계수 nCr
      • 파스칼의 삼각형(S+)
      • 모듈러 역원을 이용한 계산(G+)
      • 뤼카정리(P-)
      • p-지수를 이용한 계산(P-)
      • nCr mod p^e 계산(D-)
    • 교란수(G+)
    • [카탈란]
    • 거듭제곱 피보나치(G+)
    • 분할수(자연수 분할 P(n, k))
    • 제2종 스털링 수(집합 분할)(P-)
    • [생성 함수(D-)]
    • O(K^2 logN) 키타마사(D-)
    • [Bostan-Mori]

  • 선형대수학

    • 행렬(S-)
    • [가우스 소거법(P-)]
    • [키르히호프(P-)]
    • [strassen algorithm]
    • Freivalds' algorithm(P+)

  • 기타

    • 부등식
    • 분할정복 거듭제곱(S+)
    • 에라토스테네스의 체(S+)
    • Linear sieve 소수 판별(G-)
    • 프로베니우스의 동전 문제(G)
    • 약수 리스트 계산(G-)
    • harmonic lemma 조화 수열 계산(G+)
    • harmonic lemma 배수 개수 계산(G+)
    • p-지수(G+)
    • 확장 유클리드 호제법, 모듈러 역원(G+)
    • [Canonical Extended GCD]
    • 오일러 파이 함수(G+)
    • 중국인의 나머지 정리(P-)
    • [Garner's algorithm]
    • [Barrett reduction]
    • [fast mod]
    • [프뤼퍼 수열]
    • [베르누이 수]
    • [벨만-포드를 이용한 단순연립부등식]
    • XOR Basis(P+)
    • Faulhaber(P+)
    • [Stern-Brocot 트리]
    • 밀러-라빈 소수 판별법(P+)
    • 폴라드 로(P+)
    • [카라츠바]
    • 다항식 연산, FFT(P+)
      • 다항식곱셈: FFT(P+)
      • 정확도 높은 FFT(D-)
      • 다항식곱셈: NTT(D-)
      • 다항식 나눗셈, O(K logK logN) 키타마사(D+)
      • [다중 대입값 계산(D+)]
      • [Formal Power Series]
    • [이산 로그(P+)]
    • 유리 등차수열의 내림 합(D-)
    • 이산 제곱근(D-)
    • [이산 k제곱근]
    • Cornacchia's algorithm(D-)
    • Power tower(D-)
    • [CDQ Convolution(online FFT)]
    • [XOR Convolution, FWHT]
    • [OR/AND Convolution]
    • [subset, GCD, LCM Convolution]
    • [LP(선형 계획법), 쌍대성(D-)]
    • Simplex Method(D)
    • [번사이드 보조정리]
    • [포여 열거 정리]
    • [홀의 결혼 정리]
    • [린드스트롬-게셀-비엔노 보조정리(LGV Lemma)]
    • 라그랑주 보간법(D-)
    • Linear sieve 곱셈적 함수(D-)
    • 뫼비우스 함수(D-)
    • 뫼비우스 반전(D-)
    • 메르텐스 함수(D+)
    • 메르텐스 트릭, Xudyh's sieve (D+)
    • [min_25's sieve]
    • [매트로이드(R-)]

• 게임 이론

  • [스프라그-그런디 정리]
  • [Coldgame]
  • [Hackenbush(D-)]
  • [Blue-Red Hackenbush(R-)]

• 기타

  • [정렬, std::sort() strict weak ordering]
  • [계수 정렬]
  • 기수 정렬(S-)
  • 보이어–무어 다수결 투표(S+)
  • 이분 탐색(S-)
  • [Fractional Cascading]
  • 투 포인터(S-)
  • 비트마스크(S-)
  • 좌표 압축(S-)
  • 순열 사이클 분할(S+)
  • [최적화]
  • [Log Decomp]
  • [모노톤 스택]
  • [모노톤 큐]
  • [XOR Hashing]
  • [트리 해싱]
  • [누적합, imos]
  • [SIMD]
  • Gray code
  • 후위 표기식(G+)
  • [중간에서 만나기(G+)]
  • 반전수(P-)
  • [스위핑]
  • [슬라이딩 윈도우]
  • 덱을 이용한 구간 최댓값 트릭(P-)
  • RMQ(Range Minimum Query)(P-)
  • 삼분 탐색(P-)
  • Mo's algorithm(P+)
  • [hilbert Mo]
  • 제곱근 분할법(P+)
  • [병렬 이분 탐색(P+)]
  • [차이 부등식]
  • [range mode query]
  • [춤추는 링크, 크누스 X]
  • [임의 정밀도(epsilon값 계산)(A)]
  • [담금질 기법]
  • [DLAS]
  • [Fracturing Search(D+)]

• utils

  • fastio
  • 비트 연산
  • 비트셋 덧셈, 뺄셈
  • 문자열 압축
  • 개수 계산
  • 랜덤
  • 고합성수 검색
  • 배열 연산
  • 가까운 2의 멱수 계산
  • [시간 초 변환]
  • 날짜 변환
  • __int128 입출력
  • [파싱]
  • utf-8 입력 처리
  • n!, nCr, nHr 브루트포스 순회
  • modInt
  • [infInt]
  • [bigInt]
  • 문자열 관련
  • BaseInt

C++ 유용한 기능

• 문법

  • Range-based for loop, 구조적 바인딩
  • 람다 캡처, 재귀
  • constexpr
  • ifdef
  • [사전 정의 매크로]
  • [register]
  • 리터럴
  • [실수형 inf]
  • [using]
  • [저장 유형 지정자]
  • template argument deduction
  • 코드 여러줄 이어쓰기

• 함수

  • 수학 관련 함수들
  • 배열 관련 함수들
  • 비트셋
  • [regex]
  • std array
  • [constexpr, static_assert]
  • multiset
  • permutation
  • casting
  • GCC built-in
  • GCC 최적화
  • 문자관련
  • 문자열 관련 함수들
  • 이분탐색 람다함수
  • custom pq
  • io manip

• ps용 환경설정

  • [cph, competitive-companion]
  • define
  • vsc snippet
  • vim script
  • [debug, c_cpp_properties.json 설정]
  • [Pre-defined Compiler Macros]
  • [percompiled header]

• 기타

  • 비트 트릭
  • 자주 쓰는 변수명
  • 코딩 아이디어

파이썬

• 유용한 함수

  • [itertools]
  • [regex]
  • [eval]

• 숏코딩 팁

  • [숏코딩 팁]

참고링크

백준 알고리즘 분류
https://www.acmicpc.net/problem/tags

https://codeforces.com/blog/entry/125257

tlsdydaud1
https://00ad-8e71-00ff-055d.tistory.com/3

jh05013
https://jh05013.github.io/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

jhnah917
https://justicehui.github.io/tutorial/
https://github.com/justiceHui/Unknown-To-Wellknown

jinhan814
https://blog.naver.com/jinhan814/222439886998
https://blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222689836982&parentCategoryNo=&categoryNo=6&viewDate=&isShowPopularPosts=false&from=postView

rkm0959 - PS 정수론 가이드
https://rkm0959.tistory.com/category/PS/PS%20%EC%A0%95%EC%88%98%EB%A1%A0%20%EA%B0%80%EC%9D%B4%EB%93%9C

ahgus89 - 정수론
https://ahgus89.github.io/

kcm1700 - 알고리즘 대회에 필요한 수학, 기하
https://algospot.com/wiki/read/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8C%80%ED%9A%8C%EC%97%90_%ED%95%84%EC%9A%94%ED%95%9C_%EC%88%98%ED%95%99
https://algospot.com/wiki/read/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8C%80%ED%9A%8C%EC%97%90_%ED%95%84%EC%9A%94%ED%95%9C_%EA%B8%B0%ED%95%98

topology - 선형대수학
https://tistory.joonhyung.xyz/18

bowbowbow
https://bowbowbow.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

kks227
https://m.blog.naver.com/kks227?categoryNo=299&tab=1

MJ Studio
https://ps.mjstudio.net/categories/algorithm

cubelover
https://cubelover.tistory.com/

koosaga
https://koosaga.com/242

leo020630
https://leo630.tistory.com/

yclock
https://youngyojun.github.io/

S/W 멤버십 기술 블로그
https://infossm.github.io/blog/

gratus907
https://gratus-blog.tistory.com/

snowflake - 정수론 시리즈
https://xy-plane.tistory.com/16

snowflake - 그린정리
https://xy-plane.tistory.com/22

myungwoo
https://blog.myungwoo.kr/

Nyaan
https://nyaannyaan.github.io/library/data-structure/union-find-with-potential.hpp.html

stonejjun03
https://stonejjun.tistory.com/category/%EC%BD%94%EB%94%A9/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%26%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

궁극의 웰노운 알고리즘
https://cocoachan.tistory.com/

pentagon03
https://howtoliveworldnice.tistory.com/category/Algorithm/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EC%9D%B4%EB%A1%A0%20%EC%A0%95%EB%A6%AC

zigui - 기하학
https://zigui.tistory.com/34

algoshitpo
https://algoshitpo.github.io/

imeimi2000
https://imeimi.tistory.com/

koosaga - olympiad Library codes
https://github.com/koosaga/olympiad/tree/master/Library/codes

kimjihoon
https://etyu39.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

TAMREF
https://tamref.com/

h0ngjun7
https://hongjun7.tistory.com/