알고리즘 공부방

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를 탐색하는 방향으로 바꾸고, 일치가 발..

Andrew's Chain은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구할 수 있게 해주는 Graham's Scan과는 다른 알고리즘이다. Graham's Scan과는 다르게 Upper Hull과 Lower Hull로 분리해낼 수 있다는 장점이 있고, 정렬 또한 각도 정렬이 아닌 단순한 x축 기준 정렬만 필요하다. 1. 전체 점들을 x축 기준, x축이 같다면 y축 기준으로 정렬한다. 2. 스택에 점들을 하나씩 넣으며, 다음 불변식을 유지하도록 삽입한다. 스택의 점들은 시계 방향으로, 즉 ccw가 음수인 방향으로 굽어 있다는 불변식을 만족해야 한다. 불변식을 만족하지 않다면 점들을 위에서부터 삭제하고 현재 점을 삽입한다. 이 과정을 통해 Upper Hull을 구할 수 있다. 3. 배..

Graham's Scan은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구하는 알고리즘이다. 1. Convex Hull에 무조건 포함되는 한 점 S를 잡는다. 일반적으로 x좌표가 최소인 점, 만약 여러개 있다면 y좌표가 최소인 점으로 잡는다. 2. S를 기준으로 전체 점들을 각도 순으로 정렬한다. 만약 S, p, q가 일직선 위에 있다면 S와의 거리 순으로 정렬한다. 3. 정렬한 순서대로 점들을 하나씩 보며, 스택에 점들을 하나씩 추가한다. 단, 스택의 점들은 들어가 있는 순서대로 시계 반대 방향으로, 즉 ccw가 양수로 유지되어야 한다. 이 불변식을 만족할 수 있도록 적절히 스택에서 점들을 제거해준 후, 새로운 점을 추가해준다. #include using namespace std; ..

Biconnected Component는 biconnected (단절점이 없는) maximal subgraph이다. BCC는 그래프를 단절점/단절선을 기준으로 쪼갠 후, 이를 기준으로 정점/간선들을 묶어 트리로 만든다. 크게 2가지의 BCC가 있다. 1. Edge disjoint BCC = 단절점을 기준으로 쪼갠 간선의 집합 2. Vertex disjoint BCC = 단절선을 기준으로 쪼갠 정점의 집합 Vertex disjoint BCC의 경우에는 단절선을 모두 자른 후, 남은 컴포넌트들이 하나의 BCC를 구성하고, 이를 하나의 정점으로 압축한다면 트리가 된다. Edge disjoint BCC의 경우에는 BCC가 간선의 집합으로 구성되어 있기 때문에, 한 정점은 여러 개의 BCC에 포함될 수 있다. 특..

Li Chao Tree는 일차함수들의 볼록 껍질을 관리하는 자료 구조로, 기울기가 단조성을 보이지 않는 경우의 CHT 문제들을 해결하기 위하여 사용된다. https://cp-algorithms.com/geometry/convex_hull_trick.html 기본적인 꼴은 segment tree와 동일하다. 각 노드에는 그 노드의 구간을 담당하는 직선이 하나씩 있는데, 이때 주의할 점이 이 구간에서 이 직선이 항상 최대라는 것이 아니라 최댓값 후보 직선들 중 하나라는 것이다. 업데이트는 그 구간에 이미 들어 있던 직선과 지금 직선의 양 끝 부분의 함숫값을 비교한다. 만약 함숫값이 어느 하나가 양쪽 모두 크다면, 전체 구간에서 다 큰 것이기 때문에, 유지하던가, 갱신한다. 하지만 그것이 아니라면 원래 있던 ..

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree Centroid Decomposition 은 트리에서 분할정복을 할 수 있도록 해주는 방법이다. 분할정복은 다음과 같이 생각해볼 수 있다. 어떤 구간 [l, r]을 잡아도 어떠한 가운데 점 k를 잡아서 [l, k], [k+1, r] 로 쪼갤 수 있다. 또한, 분할정복에서 나오는 k들에서 [a, k] 와 같은 구간의 개수는 $O(NlogN)$ 개이다. 단순히 말해, 모든 구간들을 $O(NlogN)$ 개의 구간 2개의 합으로 나타낼 수 있으니 이 $NlogN$ 개를 관리하여 해결한다는 것이다. 트리에서도 Centroid 라는 점은 그 점을 제거하면 나오는 서브트리의 집합..

https://koosaga.com/121 https://codeforces.com/gym/100551/problem/A https://www.acmicpc.net/problem/16911 cp-algorithms.com/data_structures/deleting_in_log_n.html 1. 간선 추가 2. 간선 삭제 3. 정점 u, v가 연결되어 있는지 판별 이 문제를 online 으로 처리하는 것은 매우 어려운 문제이다. 따라서 Offline 으로 분할정복을 활용하여 해결하자. 가장 먼저, 각 간선의 생존시간을 시간축에 표시하면 어떠한 구간이 된다. 이 구간을 segment tree에 $logN$ 개의 노드에 업데이트 된 것이라고 생각하고, 이후 segment tree의 노드들을 전위순회하면서 u..

https://blog.myungwoo.kr/100 https://cubelover.tistory.com/14 PST는 N개의 세그먼트 트리를 만드는데, 전체 공간 복잡도가 $O(NlogN)$ 인 자료구조이다. 앞의 세그먼트 트리에서 하나의 값만 변화하는 새로운 세그먼트 트리를 만들기 위해서는 원래 세그먼트 트리의 대부분의 노드들을 재활용하고 새롭게 값이 바뀐 부분의 노드들만 변화시켜주면 된다. 이러한 이유로, 보통 2D 점 관리를 위한 자료구조로 Merge Sort Tree 와 함께 사용된다. 또한, Persistent 하게 구현되어, 수정이 불가능하다는 단점이 있다. struct Node { int val; Node *lc, *rc; Node() : val(0), lc(NULL), rc(NULL) {..