main.tex

% teamnote.sty from https://github.com/ho94949/teamnote.sty

% Team Note of SCCC
% These codes should be guaranteed, fast enough, short and easy to type.

\documentclass[landscape, 8pt, a4paper, twocolumn]{extarticle} % twocolumn
\usepackage{kotex}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{import}
\usepackage{multicol}
\usepackage{teamnote}

\teamnote{Soongsil University}{팀명}{이름1, 이름2, 이름3}

% Guide to use
  % Fix school name, team name, and teammate name at line 14
  % If you want to change to 3 columns document...
    % Erase `twocolumn' at line 6
    % Add `\begin{multicols*}{3}' after `\begin{document}'
    % Add `\end{multicols*}' before `\end{document}'
    % (optional) Add `\vfill\null\columnbreak' after `\maketitlepage' and Erase `\pagebreak' before first section
  % If you want to reduce margin size
    % Change teamnote.sty line 3 to...
    % \usepackage[left=0.3cm,right=0.3cm,top=0.6cm,bottom=0.3cm,headsep=0.1cm,a4paper]{geometry}

\ShowUsage
\ShowComplexity
\HideAuthor

\begin{document}

\maketitlepage

% Make Pagebreak if you want.
\pagebreak 

\section{정렬 / 이분 탐색 관련}

\Algorithm{정렬 비교 함수 구현}
{}{}
{cpp}{code/Sorting/Compare.cpp}
{JusticeHui}

\Algorithm{좌표 압축}
{}{$O(N \log N)$}
{cpp}{code/Sorting/CoordCompress.cpp}
{JusticeHui}

\Algorithm{이분 탐색 관련 STL}
{}{}
{cpp}{code/Sorting/STL.cpp}
{JusticeHui}

\section{그래프/트리 (Easy)}

\Algorithm{인접 리스트, DFS, BFS}
{}{$O(V+E)$}
{cpp}{code/Graph1/DFSBFS.cpp}
{JusticeHui}

\Algorithm{위상 정렬}
{}{$O(V+E)$}
{cpp}{code/Graph1/TopSort.cpp}
{JusticeHui}

\Algorithm{최단 거리 - Floyd Warshall}
{}{$O(V^3)$}
{cpp}{code/Graph1/Floyd.cpp}
{JusticeHui}

\Algorithm{최단 거리 - Dijkstra}
{}{$O(E\log E)$}
{cpp}{code/Graph1/Dijkstra.cpp}
{JusticeHui}

\Algorithm{최단 거리 - Bellman Ford}
{}{$O(VE)$}
{cpp}{code/Graph1/Bellman.cpp}
{JusticeHui}

\Algorithm{유니온 파인드 + 최소 신장 트리(Kruskal)}
{}{UF: 연산마다 $O(log N)$, MST: $O(E \log E)$}
{cpp}{code/Graph1/Kruskal.cpp}
{JusticeHui}

\section{자료구조}

\Algorithm{세그먼트 트리}
{}{$O(\log N)$}
{cpp}{code/DataStructure/SegmentTree.cpp}
{JusticeHui}

\Algorithm{세그먼트 트리 + 레이지 프로퍼게이션}
{}{$O(\log N)$}
{cpp}{code/DataStructure/SegmentTreeLazy.cpp}
{JusticeHui}

\Algorithm{Convex Hull Trick}
{call init() before use}{}
{cpp}{code/DataStructure/ConvexHullTrick.cpp}
{JusticeHui}

\Algorithm{퍼시스턴트 세그먼트 트리}
{call init(root[0], s, e) before use}{}
{cpp}{code/DataStructure/PersistentSegmentTree.cpp}
{JusticeHui}

\section{그래프/트리 (Hard)}

\Algorithm{SCC - Kosaraju}
{}{$O(V+E)$}
{cpp}{code/Graph2/SCC.cpp}
{JusticeHui}

\Algorithm{BCC - Tarjan}
{}{$O(V+E)$}
{cpp}{code/Graph2/BCC.cpp}
{JusticeHui}

\Algorithm{최대 유량 - Dinic}
{}{$O(V^2E)$, 모든 간선의 용량이 1이면 $O(\min(V^{2/3},E^{1/2})E)$}
{cpp}{code/Graph2/Dinic.cpp}
{JusticeHui}

\Algorithm{MCMF}
{}{}
{cpp}{code/Graph2/MCMF.cpp}
{JusticeHui}

\Algorithm{이분 매칭 - Hopcroft Karp}
{}{$O(E \sqrt V)$}
{cpp}{code/Graph2/Hopcroft.cpp}
{JusticeHui}

\Algorithm{최소 공통 조상(LCA)}
{}{전처리 $O(N \log N)$, 쿼리 $O(\log N)$}
{cpp}{code/Graph2/LCA.cpp}
{JusticeHui}

\Algorithm{Heavy Light Decomposition}
{}{전처리 $O(N)$, 쿼리 $O(T(N) \log N)$}
{cpp}{code/Graph2/HLD.cpp}
{JusticeHui}

\section{수학}

\Algorithm{나눗셈, 최대공약수, 최소공배수}
{}{}
{cpp}{code/Math/Division.cpp}
{JusticeHui}

\Algorithm{빠른 거듭제곱}
{$a^b \pmod c$를 구하는 함수}{$O(\log b)$}
{cpp}{code/Math/PowMod.cpp}
{JusticeHui}

\Algorithm{소수 판별, 소인수분해}
{}{$O(\sqrt N)$}
{}{code/Math/Primes.cpp}
{JusticeHui}

\Algorithm{에라토스테네스의 체, 소인수분해}
{}{Sieve: $O(N \log \log N)$, Factorize: $O(\log N)$}
{}{code/Math/Sieve.cpp}
{JusticeHui}

\Algorithm{선형 시간 체, 곱셈적 함수 전처리}
{}{}
{}{code/Math/LinearSieve.cpp}
{ahgus89}

\Algorithm{확장 유클리드 알고리즘}
{}{$O(\log \max(a,b))$}
{cpp}{code/Math/ExtendedEuclidean.cpp}
{JusticeHui}

\Algorithm{중국인의 나머지 정리}
{}{$O(k \log m)$}
{cpp}{code/Math/ChineseRemainderTheorem.cpp}
{JusticeHui}

\Algorithm{이항 계수를 소수로 나눈 나머지}
{}{전처리 $O(P)$, 쿼리 $O(\log P)$}
{cpp}{code/Math/LucasTheorem.cpp}
{JusticeHui}

\Algorithm{빠른 소수 판별, 소인수분해 - Miller Rabin, Pollard Rho}
{처음에 Sieve() 호출해야 함}{IsPrime: $O(\log^2 N)$, Factorize: 약 $O(N^{1/4})$}
{cpp}{code/Math/MillerRabin-PollardRho.cpp}
{JusticeHui}

\Algorithm{가우스 소거법 - RREF, 랭크, 행렬식, 역행렬}
{}{$O(N^3)$}
{cpp}{code/Math/Matrix.cpp}
{JusticeHui}

\Algorithm{다항식 곱셈(FFT)}
{}{$O(N \log N)$}
{cpp}{code/Math/Convolution.cpp}
{JusticeHui}

\section{문자열}

\Algorithm{문자열 해싱}
{}{build: $O(N)$, get: $O(1)$}
{cpp}{code/String/Hashing.cpp}
{JusticeHui}

\Algorithm{문자열 매칭 - KMP}
{}{GetFail: $O(\vert P\vert)$, $O(\vert S\vert + \vert P\vert)$}
{cpp}{code/String/KMP.cpp}
{JusticeHui}

\Algorithm{가장 긴 팰린드롬 부분 분자열 - Manacher}
{}{$O(N)$}
{cpp}{code/String/Manacher.cpp}
{JusticeHui}

\Algorithm{문자열 매칭 - Z}
{}{$O(N)$}
{cpp}{code/String/Z.cpp}
{JusticeHui}

\Algorithm{접미사 배열}
{}{$O(N \log N)$}
{cpp}{code/String/SuffixArray.cpp}
{JusticeHui}

\section{계산 기하}

\Algorithm{2차원 계산 기하 템플릿 + CCW}
{}{}
{cpp}{code/Geometry/Template.cpp}
{JusticeHui}

\Algorithm{360도 각도 정렬}
{}{}
{cpp}{code/Geometry/PolarSort.cpp}
{JusticeHui}

\Algorithm{다각형 넓이}
{}{}
{cpp}{code/Geometry/PolygonArea.cpp}
{JusticeHui}

\Algorithm{선분 교차 판정}
{}{}
{cpp}{code/Geometry/SegmentIntersection.cpp}
{JusticeHui}

\Algorithm{다각형 내부 판별}
{}{}
{cpp}{code/Geometry/PointInPolygon.cpp}
{JusticeHui}

\Algorithm{볼록 껍질 - Graham Scan}
{}{}
{cpp}{code/Geometry/ConvexHull.cpp}
{JusticeHui}

\Algorithm{가장 먼 두 점 - Rotating Calipers}
{}{}
{cpp}{code/Geometry/Calipers.cpp}
{JusticeHui}

\Algorithm{볼록 다각형 내부 판별}
{}{}
{cpp}{code/Geometry/PointInConvexPolygon.cpp}
{JusticeHui}

\section{기타}

\Algorithm{가장 긴 증가하는 부분 수열(LIS)}
{}{$O(N \log N)$}
{cpp}{code/Misc/LIS.cpp}
{JusticeHui}

\Algorithm{이분 탐색}
{}{}
{cpp}{code/Misc/BinarySearch.cpp}
{JusticeHui}

\Algorithm{삼분 탐색}
{}{}
{cpp}{code/Misc/TernarySearch.cpp}
{JusticeHui}

\Algorithm{C++ 랜덤, GCC 확장, 비트마스킹 트릭}
{}{}
{cpp}{code/Misc/Cpp-Grammer.cpp}
{JusticeHui}

\Algorithm{빠른 입력(Fast Input from STDIN)}
{}{}
{cpp}{code/Misc/FastIO.cpp}
{cgiosy}

\Algorithm{구간별 약수 최대 개수, 최대 소수}{}{}{}{}{koosaga}
\begin{minted}{cpp}
< 10^k          number     divisors   2 3 5 71113171923293137
-------------------------------------------------------------
1                    6            4   1 1
2                   60           12   2 1 1
3                  840           32   3 1 1 1
4                 7560           64   3 3 1 1
5                83160          128   3 3 1 1 1
6               720720          240   4 2 1 1 1 1
7              8648640          448   6 3 1 1 1 1
8             73513440          768   5 3 1 1 1 1 1
9            735134400         1344   6 3 2 1 1 1 1
10          6983776800         2304   5 3 2 1 1 1 1 1
11         97772875200         4032   6 3 2 2 1 1 1 1
12        963761198400         6720   6 4 2 1 1 1 1 1 1
13       9316358251200        10752   6 3 2 1 1 1 1 1 1 1
14      97821761637600        17280   5 4 2 2 1 1 1 1 1 1
15     866421317361600        26880   6 4 2 1 1 1 1 1 1 1 1
16    8086598962041600        41472   8 3 2 2 1 1 1 1 1 1 1
17   74801040398884800        64512   6 3 2 2 1 1 1 1 1 1 1 1
18  897612484786617600       103680   8 4 2 2 1 1 1 1 1 1 1 1

< 10^k    prime   # of prime          < 10^k            prime
-------------------------------------------------------------
1             7            4          10           9999999967
2            97           25          11          99999999977
3           997          168          12         999999999989
4          9973         1229          13        9999999999971
5         99991         9592          14       99999999999973
6        999983        78498          15      999999999999989
7       9999991       664579          16     9999999999999937
8      99999989      5761455          17    99999999999999997
9     999999937     50847534          18   999999999999999989
\end{minted}

\Algorithm{카탈란 수, 심슨 적분, 그런디 정리, 픽의 정리, 페르마 포인트, 오일러 정리}
{}{}{}{}{}
\begin{itemize}
\setlength\itemsep{0.1em}
    
\item 카탈란 수\\
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,742900\\
$C_n = binomial(n * 2, n) / (n + 1);$\\
- 길이가 2n인 올바른 괄호 수식의 수\\
- n + 1개의 리프를 가진 풀 바이너리 트리의 수\\
- n + 2각형을 n개의 삼각형으로 나누는 방법의 수

\item Simpson 공식 (적분) : Simpson 공식, $S_n(f) = \frac{h}{3}[f(x_0)+f(x_n)+ 4\sum f(x_{2i+1}) + 2\sum f(x_{2i})]$\\
- $M = \max \vert f^4(x) \vert$이라고 하면 오차 범위는 최대 $E_n \leq \frac{M(b-a)}{180}h^4$

\item 알고리즘 게임\\
- Nim Game의 해법 : 각 더미의 돌의 개수를 모두 XOR했을 때 0 이 아니면 첫번째, 0 이면 두번째 플레이어가 승리.\\
- Grundy Number : 어떤 상황의 Grundy Number는, 가능한 다음 상황들의 Grundy Number를 모두 모은 다음, 그 집합에 포함 되지 않는 가장 작은 수가 현재 state의 Grundy Number가 된다. 만약 다음 state가 독립된 여러개의 state들로 나뉠 경우, 각각의 state의 Grundy Number의 XOR 합을 생각한다.\\
- Subtraction Game : 한 번에 k 개까지의 돌만 가져갈 수 있는 경우, 각 더미의 돌의 개수를 k + 1로 나눈 나머지를 XOR 합하여 판단한다.\\
- Index-k Nim : 한 번에 최대 k개의 더미를 골라 각각의 더미에서 아무렇게나 돌을 제거할 수 있을 때, 각 binary digit에 대하여 합을 k + 1로 나눈 나머지를 계산한다. 만약 이 나머지가 모든 digit에 대하여 0이라면 두번째, 하나라도 0이 아니라면 첫번째 플레이어가 승리.\\
- Misere Nim : 모든 돌 무더기가 1이면 N이 홀수일 때 후공 승, 그렇지 않은 경우 XOR 합 0이면 후공 승

\item Pick’s Theorem\\
격자점으로 구성된 simple polygon이 주어짐. I 는 polygon 내부의 격자점 수, B 는 polygon 선분 위 격자점 수, A는 polygon의 넓이라고 할 때, 다음과 같은 식이 성립한다. $A=I+B/2-1$
\begin{minted}{cpp}
// number of (x, y) : (0 <= x < n && 0 < y <= k/d x + b/d)
ll count_solve(ll n, ll k, ll b, ll d) { // argument should be positive
  if (k == 0) {
    return (b / d) * n;
  }
  if (k >= d || b >= d) {
    return ((k / d) * (n - 1) + 2 * (b / d)) * n / 2 + count_solve(n, k % d, b % d, d);
  }
  return count_solve((k * n + b) / d, d, (k * n + b) % d, k);
}
\end{minted}

\item 페르마 포인트 : 삼각형의 세 꼭짓점으로부터 거리의 합이 최소가 되는 점\\
$2\pi/3$ 보다 큰 각이 있으면 그 점이 페르마 포인트, 그렇지 않으면 각 변마다 정삼각형 그린 다음, 정삼각형의 끝점에서 반대쪽 삼각형의 꼭짓점으로 연결한 선분의 교점\\
$2\pi/3$ 보다 큰 각이 없으면 거리의 합은 $\sqrt{(a^2 + b^2 + c^2 + 4\sqrt 3 S) / 2}$, $S$는 넓이

\item 오일러 정리: 서로소인 두 정수 $a,n$에 대해 $a^{\phi(n)}\equiv 1 \pmod n$\\
모든 정수에 대해 $a^n \equiv a^{n-\phi(n)} \pmod n$\\
$m\geq log_2 n$이면 $a^m\equiv a^{m\%\phi(n)+\phi(n)}\pmod n$

\item $g^0+g^1+g^2+\cdots g^{p-2}\equiv -1 \pmod p$ iff $g=1$, otherwise $0$.

\end{itemize}

\Algorithm{경우의 수 - 포함 배제, 스털링 수, 벨 수}
{}{}{}{}{}
\begin{itemize}
\setlength\itemsep{0.1em}

\item 공 구별 X, 상자 구별 O, 전사함수 : 포함배제 $\sum_{i=1}^{k} (-1)^{k-i} \times kCi \times i^n$
\item 공 구별 O, 상자 구별 X, 전사함수 : 제 2종 스털링 수 $S(n,k)=k\times S(n-1,k) + S(n-1, k-1)$\\
포함배제하면 $O(K \log N)$, $S(n,k) = 1/k! \times \sum_{i=1}^{k} (-1)^{k-i} \times kCi \times i^n$
\item 공 구별 O, 상자 구별 X, 제약없음 : 벨 수 $B(n,k) = \sum_{i=0}^{k} S(n,i)$ 몇 개의 상자를 버릴지 다 돌아보기\\
수식 정리하면 $O(\min(N,K)\log N)$에 됨. $B(n,n) = \sum_{i=0}^{n-1} (n-1)Ci \times B(i,i)$\\
$B(n,k)=\sum_{j=0}^{k}S(n,j) = \sum_{j=0}^{k} 1/j! \sum_{i=0}^{j} (-1)^{j-i} jCi \times i^n=\sum_{j=0}^{k}\sum_{i=0}^{j} \frac{(-1)^{j-i}}{i!(j-i)!}i^n$\\
$=\sum_{i=0}^{k}\sum_{j=i}^{k}\frac{(-1)^{j-i}}{i!(j-i)!}i^n = \sum_{i=0}^{k}\sum_{j=0}^{k-i}\frac{(-1)^j}{i!j!}i^n = \sum_{i=0}^k \frac{i^n}{i!}\sum_{j=0}^{k-i} \frac{(-1)^j}{j!}$

\item Derangement: $D(n)=(n-1)(D(n-1)+D(n-2))$
\item Signed Stirling 1: $S_1(n,k)=(n-1)S_1(n-1,k)+S_1(n-1,k-1)$
\item Unsigned Stirling 1: $C_1(n,k)=(n-1)C_1(n-1,k)+C_1(n-1,k-1)$
\item Stirling 2: $S_2(n,k)=kS_2(n-1,k)+S_2(n-1,k-1)$
\item Stirling 2: $S_2(n,k)=\frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}{k \choose j}j^n$
\item Partition: $p(n,k)=p(n-1,k-1) + p(n-k,k)$
\item Partition: $p(n)=\sum (-1)^kp(n-k(3k-1)/2)$
\item Bell: $B(n)=\sum_{k=1}^n {n-1\choose k-1}B(n-k)$
\item Catalan: $C_n=\frac{1}{n+1}{2n\choose n}$
\item Catalan: $C_n={2n\choose n}-{2n\choose n+1}$
\item Catalan: $C_n=\frac{(2n)!}{n!(n+1)!}$
\item Catalan: $C_n=\sum C_iC_{n-i}$

\end{itemize}

\Algorithm{삼각형의 오심 - 외심, 내심, 무게중심, 수심, 방심}
{}{}{}{}{Ryute}

변 길이 $a, b, c; p = (a+b+c)/2$ \\
넓이 $A = \sqrt{p(p-a)(p-b)(p-c)}$ \\
외접원 반지름 $R = abc/4A$, 내접원 반지름 $r = A/p$ \\
중선 길이 $m_a = 0.5\sqrt{2b^2 + 2c^2 - a^2}$ \\
각 이등분선 길이 $s_a = \sqrt{bc(1-\frac{a}{b+c}^2)}$ \\
사인 법칙 $\frac{sin A}{a} = 1/2R$, 코사인 법칙 $a^2 = b^2 + c^2 - 2bc\cos A$, 탄젠트 법칙 $\frac{a+b}{a-b} = \frac{\tan (A+B)/2}{\tan (A-B)/2}$ \\
중심 좌표 $(\frac{\alpha x_a + \beta x_b + \gamma x_c}{\alpha+\beta+\gamma}, \frac{\alpha y_a + \beta y_b + \gamma y_c}{\alpha+\beta+\gamma})$ \\

\begin{tabular}{|c|c|c|c|c|}
    이름 & $\alpha$ & $\beta$ & $\gamma$ & \\ \hline
    외심 & $a^2\mathcal{A}$ & $b^2\mathcal{B}$ & $c^2\mathcal{C}$ & $\mathcal{A}=b^2+c^2-a^2$ \\
    내심 & $a$ & $b$ & $c$ & $\mathcal{B} = a^2 + c^2 - b^2$ \\
    무게중심 & $1$ & $1$ & $1$ & $\mathcal{C} = a^2 + b^2 - c^2$ \\
    수심 & $\mathcal{BC}$ & $\mathcal{CA}$ & $\mathcal{AB}$ & \\
    방심(A) & $-a$ & $b$ & $c$ & 
\end{tabular}

\Algorithm{미적분, 뉴턴 랩슨법}{}{}{}{}{}
\begin{itemize}
    \setlength\itemsep{0.1em}
    \item $(\arcsin x)'=1/\sqrt{1-x^2}$
    \item $(\tan x)'=1+\tan^2 x$
    \item $\int tan ax=-\ln |\cos ax|/a$
    \item $(\arccos x)'=-1/\sqrt{1-x^2}$
    \item $(\arctan x)'=1/(1+x^2)$
    \item $\int x \sin ax=(\sin ax - ax\cos ax)/a^2$
    \item Newton: $x_{n+1}=x_{n}-f(x_n)/f'(x_n)$
    \item $\oint_C (Ldx+Mdy)=\int\int_D (\frac{\partial M}{\partial x}-\frac{\partial L}{\partial y})dxdy$
    \item where $C$ is positively oriented, piecewise smooth, simple, closed; $D$ is the region inside $C$; $L$ and $M$ have continuous partial derivatives in $D$.
\end{itemize}

\Algorithm{문제 풀이 체크리스트}{}{}{}{}{}
\begin{itemize}
    \setlength\itemsep{0.1em}
    \item 비슷한 문제를 풀어본 적이 있던가?
    \item 단순한 방법에서 시작할 수 있을까? (Brute Force)
    \item 내가 문제를 푸는 과정을 수식화할 수 있을까? (예제를 직접 해결해보면서)
    \item 문제를 단순화할 수 없을까?
    \item 그림으로 그려볼 수 있을까?
    \item 수식으로 표현할 수 있을까?
    \item 문제를 분해할 수 있을까?
    \item 뒤에서부터 생각해서 풀 수 있을까?
    \item 순서를 강제할 수 있을까?
    \item 특정 형태의 답만을 고려할 수 있을까? (정규화)
    \item 구간을 통째로 가져간다 : 플로우 + 적당한 자료구조 $(i,i+1,k,0),(s,e,1,w),(N,T,k,0)$
    \item a = b : a만 움직이기, b만 움직이기, 두 개 동시에 움직이기, 반대로 움직이기
    \item 말도 안 되는 것들을 한 번은 생각해보기 / "당연하다고 생각한 것" 다시 생각해보기
    \item 확률 : DP, 이분 탐색(NYPC 2019 Finals C)
    \item 최대/최소 : 이분 탐색, 그리디(Prefix 고정, Exchange Argument), DP(순서 고정)
\end{itemize}

\end{document}