알고리즘 공부방

https://arnold518.github.io/ps-notes/ Problem Solving Notes arnold518.github.io Github 블로그로 이전합니다!

gazelle-and-cs.tistory.com/10 en.wikipedia.org/wiki/Hall%27s_marriage_theorem 이분그래프 $G=(L+R, E)$에서, $L$의 부분집합 $S$에 대해 이와 연결된 $R$의 부분집합을 $N(S)$라 하자. 이 이분그래프에서 L의 모든 정점이 참여하는 매칭이 존재할 필요충분조건은 모든 $S$에 대하여 $|S| \leq |N(S)|$ 가 성립하는 것이다.

1. Walk Sequence of vertices and edges of a graph. Vertex can be repeated. Edges can be repeated. Open Walk : starting vertex != ending vertex Closed Walk : starting vertex == ending vertex 2. Trail Open walk in which no edge is repeated. Vertex can be repeated. Edges cannot be repeated. 3. Circuit Closed walk in which no edge is repeated. Closed trail. Vertex can be repeated. Edges cannot be re..

1. 모든 $a \leq b$, $c \leq d$에 대해, $f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$가 성립한다면, $f(i, j)$는 사각 부등식 (Quadrangle Inequality), Monge Property를 만족한다. $f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$를 다음과 같이 해석할 수 있다. 구간 $[a, d]$와 $[b, c]$를 선택하는 대신에 구간 $[a, c]$와 $[b, d]$를 선택하도록 바꿔주는 것이 이득이다. 2. $[l, r]$의 값들을 SUM한 함수와 MIN을 취한 함수는 Monge Property를 만족한다. SUM 함수는 항상 $f(a, c)+f(b, d)=f(a, d)+f(b, c)$이니 성립한다. MIN 함수는..

blog.naver.com/kks227/220917078260 KMP 알고리즘(Knuth–Morris–Pratt Algorithm) (수정: 2019-09-01) KMPlayer가 아니다 안녕하세요. 한동안 그래프를 줄창 했듯이 이제부터는 문자열을 줄창 하게 될 겁니다... blog.naver.com $S[1, i]$ 에서 prefix와 suffix가 같은 최대 길이를 fail[i]라 저장한 전처리 배열을 먼저 만든다. 그 후, 위 그림과 같이 불일치가 발생하였을 때마다, fail에 해당하는 값만큼 건너뛰어, i는 절대 감소하지 않고, j만 이동하도록 만들어 주면 시간복잡도가 $O(N+M)$이 보장된다. fail 함수를 구하는 방법은 단순히 위 알고리즘을 S에서 S를 탐색하는 방향으로 바꾸고, 일치가 발..

2021/02/01 www.acmicpc.net/problem/10128 10128번: Supercomputer In the first line of standard input, there are two integers, n and q(1 ≤ n,q ≤ 1,000,000), separated by a single space, that specify the number of instructions in Byteasar's program and the number of running time queries (for different numbers of proce www.acmicpc.net arnold518.tistory.com/117 www.acmicpc.net/problem/20172 20172번: El..

문제 www.acmicpc.net/problem/10128 10128번: Supercomputer In the first line of standard input, there are two integers, n and q(1 ≤ n,q ≤ 1,000,000), separated by a single space, that specify the number of instructions in Byteasar's program and the number of running time queries (for different numbers of proce www.acmicpc.net 루트가 정해진 트리가 하나 주어지고, 트리의 각 노드는 프로세스로, 어떤 노드의 프로세스를 실행하기 위해서는 그 노드의 조상 노드를 ..

#include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution(l, r)(rng); } void compile() { system("g++ -std=c++17 -O2 -o PROBLEM grader.cpp PROBLEM.cpp"); system("g++ -std=c++17 -O2 -o PROBLEM2 grader.cpp PROBLEM2.cpp"); } void input() {..