알고리즘 공부방

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() {..

1. 문제에서 구하고 싶은 구조 (트리에서의 경로 / 트리에서의 연속 컴포넌트)를 루트를 정해놓고, 그 루트를 지나는 것들만 고려했을 때 쉽게 풀 수 있다면 Centroid Decomposition을 이용하여 전체 문제를 해결할 수 있다. 만약 트리에서의 루트가 고정되어 있고, 루트를 지나는 구조들에 대해서는 쉽게 풀 수 있다면, 이제 그 루트를 지나지 않는 경우에 대해서는 Centroid Decomposition의 분할정복 과정에서 다음으로 탐색할 것이다. 이와 같이 생각하면 장점이, 루트를 지나는 경로 / 컴포넌트 등은 각 서브트리에서 문제를 독립적으로 해결할 수 있으니, 가능한 모든 정점쌍 / 집합쌍을 고려하는 대신, 한 서브트리의 정점들을 자료구조 안에 삽입한 후 다른 정점들을 빠르게 찾을 수도 ..

문제 oj.uz/problem/view/JOI18_bitaro 문제 보기 - Bitaro’s Party (JOI18_bitaro) :: oj.uz 문제 보기 - Bitaro’s Party (JOI18_bitaro) oj.uz 정점 개수 N, 간선 개수 M개의 DAG가 주어진다. 이 때, 다음과 같은 쿼리에 답해야 한다. 정점 v로 오는 경로들 중, 시작점이 u1, u2, ..., uk 중 하나인 경로들을 제외했을 때 최장경로의 길이룰 구하라. $N