본문 바로가기

분류 전체보기

BOJ)10266 시계 사진들 문제: icpc.me/10266 각 시계의 바늘들을 1 빈 공간을 0으로 표시해준 뒤 환형 문자열 A에서 B를 탐색하여 존재하는 경우 possible을 출력하면 된다. 환형 문자열 A를 탐색하는 방법은 A 2개를 이어붙인 문자열에서 B를 탐색하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include #define N 360000using namespace std;int n, f, t;bool arr[720100];bool brr[360100];int pi[360100];void getpi(){ int j = 0; for (int i.. 더보기
BOJ)1305 광고 문제:icpc.me/1305 광고의 길이중 가장 짧은 광고는 조금만 생각해보면 n-pi[n-1]이라는 걸 알 수 있다. 123456789101112131415161718192021222324252627#include #include #include #include #include using namespace std;vector pi;int n;string x;void getpi(){ int j = 0; for (int i = 1; i 0 && x[i] != x[j]) j = pi[j - 1]; if (x[i] == x[j]) pi[i] = ++j; }}int main(){ scanf("%d", &n); pi.resize(n + 1); cin >> x; getpi(); printf("%d\n", n - p.. 더보기
BOJ)11479 서로 다른 부분 문자열의 개수2 문제:icpc.me/11479 서로 다른 부분 문자열의 개수를 세는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 0~n 에 대하여 n-SA[i]-LCP[i](해당 Suffix의 길이-LCP) 의 합을 구해주면 된다. 해당 Suffix의 부분 문자열의 경우의 수는 해당 Suffix의 길이지만 이때 LCP만큼 중복되기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include typedef long long ll;#define MAX_N 1000010using namespace std;char.. 더보기
BOJ)9249 최장 공통 부분 문자열 문제: icpc.me/9249 http://jason9319.tistory.com/143와 유사한 문제이다. 두 문자열 사이에 더미를 끼운 뒤 하나로 연결한 후 LCP Array의 최댓값을 구하는데 이때 해당 LCP[i]를 구성하는 SA[i]와 SA[i-1]이 서로 다른 문자열에서 파생된 문자여야 한다. 거기에 해당 부분 문자열을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #define MAX_N 200020using namespace std;char str[2.. 더보기
BOJ)5582 공통 부분 문자열 문제: icpc.me/5582 두 문자열이 주어질 때 공통 부분 문자열의 최대 길이를 출력하는 문제이다. 두 문자열 사이에 나올 수 없는 한 문자열을 더미로 끼운 뒤 두 문자열을 연결하여 (ex ABC!BCD) Suffix Array를 이용하여 LCP Array를 구할 때 비교 되는 접미사 SA[i]와 SA[i-1]가 서로 다른 문자열로부터 파생된 것들 중 LCP의 최대길이를 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #define MAX_N 10000using namespace st.. 더보기
BOJ)1605 반복 부분문자열 문제: icpc.me/1605 한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에 가장 긴 문자열의 길이를 출력하는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 LCP Array중 최댓값이 두번 이상 나타나는 문자열 중 가장 긴 문자열이다. 한 부분 문자열이 두번 이상 출현한다면 이를 접두사를 갖는 접미사들은 접미사 배열상에서 항상 인접해 있기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #define MAX_N 200020using namespace std;char .. 더보기
Suffix Array & LCP Array(Longest Common Prefix Array) Suffix Array는 번역하면 접미사 배열으로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조 입니다. Suffix Array는 문자열의 Suffix를 사전순으로 정렬한 배열입니다. 예를 들어 banana라는 문자가 있다면 Suffix Array는 다음과 같이 됩니다. 하지만 Suffix Array를 이렇게 문자열로 가지고 있을 경우 O(N^2)의 공간 복잡도를 가지게 될 것입니다. 그렇기 때문에 Suffix Array는 몇번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조형태를 가집니다. 다음과 같이 말이죠. 자 이제 Suffix Array의 정의에 대해 알았으니 구현을 해 볼 차례입니다. 단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요 하지만 이.. 더보기
BOJ)1021 회전하는 큐 문제: icpc.me/1021 주어진 순서대로 첫번째 원소를 뽑아 원하는 수를 뽑아낼 때 쉬프트 연산의 최소 횟수를 출력하는 문제이다. 쉬프트 연산은 앞 뒤에서 pop push가 가능한 deque을 이용하면 쉽게 해결가능하다 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include using namespace std;deque dq;int n, m, x, r;int main() { scanf("%d%d", &n, &m); for (int i = 1; i 더보기
BOJ)1893 시저 암호 문제: icpc.me/1893 문자열 W가 주어질 때 W를 A의 조건에 맞게 쉬프트하여 문자열 S에서 n번 만큼 쉬프트한 W가 1개일 경우 답에 추가하는 문제이다. A의 조건의 순서를 dictionary를 이용하여 인덱스로 관리해주고 W를 한번씩 쉬프트 해주면서 S에서 W를 KMP를 이용하여 검색하였을 때 1번만 검색되는 경우만 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #include #include #include using na.. 더보기
BOJ)9934 완전 이진 트리 문제: icpc.me/9934 완전 이진 트리가 주어질 때 이진 트리의 깊이 순서대로 출력해주면 되는 문제이다. 12345678910111213141516#include #include #include using namespace std;int k, r[1 더보기

티스토리툴바