Problem solving/BOJ29 [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. [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. [BOJ] 1005. ACM Craft (C++) 문제 건설 순서 규칙이 주어졌을 때, 특정 건물을 가장 빨리 지을 때까지 걸리는 최소시간 구하기 생각할 것 순서 규칙이 있으므로 위상정렬 사용해보기 처음 시작할 때 진입차수가 0인 것이 여러개 있다면 여러번 실행해봐야하는가!? 이런식으로 하면 진입차수 0인것과 연결된 정점 모두 판단 못함 정점번호마다 누적된 건설 시간을 더하고 비교하면서 최댓값을 넣기 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T, N, K, X, Y, W; cin >> T; while (T--) { // 입력 cin >> N >> K; vector time(N .. 2023. 7. 31. 이전 1 2 3 4 5 6 7 8 다음
