robustflame의 블로그

문제링크 - 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를 구하면 된다는 것이다. 단순..