Problem solving70 [BOJ] 16172. 나는 친구가 적다 (Large) (C++) 문제 숫자가 섞여있는 문자열에서 원하는 알파벳 문자열 찾기 생각할 것 문자열 검색이니 KMP를 사용해보자 알파벳 위치 필요 없이 존재여부만 알면 되므로 숫자를 다 없애고 비교하자 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string S, K; cin >> S >> K; string Str; for (int i = 0; i < S.size(); i++) { if (!('0' 0 이고 다르면 if (K[i] == K[matched]) pi[i] = ++matched; // 같으면 } matched = 0; for (int i = 0; i .. 2023. 8. 6. [BOJ] 16916. 부분 문자열 (C++) 문제 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 확인 생각할 것 문자열 검색 시 시간복잡도를 줄이기 위해 KMP를 사용하자! 실패했던 반례 : baekjoon baekjoon1 원인 검색 시 while(begin ≤ S.size() - P.size()) 으로 탐색을 했는데, 패턴이 더 긴 경우에는 음수가 되므로 끝나지 않는다. 해결 방법 패턴이 더 긴 경우에는 반드시 일치하는 결과를 얻을 수 없으므로 조건을 추가해준다 코드 1. KMP 전통적인 구현 방법 (논문에 게재된 방법) #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); str.. 2023. 8. 4. 문자열 검색 알고리즘 (KMP) 일반적으로 문자열에서 패턴을 검색한다고 할 때, 모든 경우를 검색해야 할 것이다. KMP (Knuth Morris Pratt) 알고리즘 모든 부분을 비교하지 않아도 부분 문자열을 찾을 수 있는 알고리즘 접두사와 접미사가 일치하는 최대 길이 찾기 일치하는 경우에는 점프할 수 있다 알고리즘 1. 패턴 문자열에 대해 접두사이면서 접미사인최대 문자열 개수 구하기 2. 문자열과 패턴을 비교하기 (위 : 문자열, 아래 : 패턴) 3. 다른 부분이 있다면 해당 위치에서 접두사와 접미사가 동일한 만큼 이동시킴 처음부분과 끝부분이 4개 동일하다는 것을 알고 있으므로 이동시킨만큼은 항상 같다 코드 1. 접두사 접미사가 일치하는 최대 길이 배열 구하기 // KMP 전통적인 방법 vector pi(pattern.size()).. 2023. 8. 4. [BOJ] 14929. 귀찮아 (SIB) 문제 N과 N개의 배열이 주어질 때 위의 식 결과 구하기 생각할 것 그냥 2중 for문을 이용하여 계산하면 시간초과가 발생한다. for문 하나를 줄일 수 있는 방법을 생각해보면 x1x2 + x1x3 + x1xn = x1(x2 + x3 + xn)의 공식을 이용하면 된다! 그리고 더해지는 수는 누적합과 구간합을 이용해 계산하면 된다. 코드 시간복잡도 O(N) #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; vector vec(N + 1); vector sum(N + 1); for (int i = 1; i > vec[i]; sum[i] =.. 2023. 8. 1. 이전 1 ··· 3 4 5 6 7 8 9 ··· 18 다음
