robustflame의 블로그

Suffix Array 접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다. 접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미..

트리의 지름 (Diameter of Tree) 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 트리의 지름이라고 한다. 이 트리의 지름을 가장 간단하게 구하는 방법은 다음과 같다. 트리의 임의의 한 노드 \(u\)에서 가장 멀리 있는 노드 \(v\)를 찾는다.\(v\)에서 가장 멀리 있는 노드 \(w\)를 찾는다.\(v\) ~ \(w\)가 트리의 지름이 된다. 위의 방법에서 특정 노드에서 가장 멀리 있는 노드는 DFS나 BFS를 사용하면 쉽게 찾을 수 있다. 증명은 귀류법을 이용하여 \(v\) ~ \(w\)가 아닌 다른 두 노드 \(a\) ~ \(b\)를 트리의 지름이라고 가정한 후, 이것이 모순이 됨을 보이면 된다. (자세한 내용은 여기를 참고하자) 예제BOJ 1967 트리의 지름 BOJ 2132 나..

문제링크 - https://www.acmicpc.net/problem/5419문제 분류난이도 - 중태그 - 구간 트리문제 풀이각 점에 대해서 자신의 위치보다 \(x\) 값이 크거나 같으면서, \(y\)값은 작거나 같은 지점들을 모두 세면 되는 문제다. 그런데 \(n\)의 값을 보면 알겠지만, 단순하게 모두 다 해보는 \(O(N^2)\) 방식으로는 안된다. 구간 트리를 사용하면 이 정보를 빠르게 셀 수 있다. 먼저 좌표들을 (1) \(x\)값이 감소하는 방향으로, (2) \(y\) 값이 증가하는 방향으로 정렬한다. 그런 다음에 유일한 \(y\) 좌표들을 가지고 구간 트리를 구성한다. 이제 앞서 점들을 정렬한 순서대로 하나씩 자신보다 \(x\) 값이 크거나 같은 점들 중에서 \(y\) 값이 작거나 같은 좌표..

Knuth-Morris-Pratt Pattern Searching 긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다. 구현#include using namespace std; // 문자열 A에서 문자열 B와 일치하는 위치를 모두 찾는다. vector KMPSearch(const string& A, const string& B) { int AN = A.length(), BN = B.length(); // 부분 일치 테이블 생성 vector pi(BN, 0); int matched = 0; for (int i = 1; i 0 && B[i] !..

문제링크 - https://www.acmicpc.net/problem/3117문제 분류난이도 - 중태그 - 동적계획법문제 풀이경험이 없으면 풀기 까다로운 문제다. 단순하게 동영상을 순회하면서 풀고자 하면 당연히 시간초과가 발생한다. 동적계획법을 생각해봐도 \(M\)이 10억이라 딱히 감이 오지 않는다. 그런데 다음과 같은 점화식을 세울 수 있으면 문제가 해결된다. dp[i][j] = i 번 동영상에서 \(2^j\) 분 후, 시청할 동영상dp[i][j] = dp[ dp[i][j-1] ][j-1] 위의 점화식을 간단하게 설명하면 a번 동영상에서 2x분 후에 시청할 동영상은 a번 동영상에서 x분 후에 시청할 동영상 b를 구한 뒤, 다시 b번 동영상에서 x분 후에 시청할 동영상 c를 구하면 된다는 것이다. 단순..