본문 바로가기

문자열

 (6)
백준 16923 - 다음 다양한 단어 https://www.acmicpc.net/problem/16923풀이이 문제는 크게 두 가지의 경우로 나눌 수 있다.알파벳이 모두 들어있지 않은 경우이 경우엔 없는 알파벳 중 가장 작은 알파벳을 맨 뒤에 붙이면 된다.알파벳이 모두 들어있는 경우먼저 zyxwvutsrqponmlkjihgfedcba는 사전순 가장 마지막이기 때문에 사전순으로 오는 다음 문자열이 없다. 이런 경우에만 -1을 출력해 주면 된다. 그렇지 않으면 문자열 $s$에서 가장 마지막으로 $s_{i} 왜 나머지 문자를 지우냐면, 문자열의 사전순 비교는 길이가 작은 게 앞으로 오기 때문이다. 정답 코드 - C++더보기#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")#pragma GCC o..
백준 1498 - 주기문 https://www.acmicpc.net/problem/4354 사전 지식 이 문제를 KMP로 풀고 와야 한다. https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 풀이 문자열 제곱을 제대로 이해하고 왔다면 KMP 실패 함수에 다음 성질이 있음을 알 것이다. 길이 x의 문자열이 주기성을 만족하려면 n - x개의 접미사와 n - x개의 접두사가 같아야 한다. 또한 x|n을 만족해야 한다.(|은 정수론에서 배수관계..
[ICPC] 백준 14959 - Slot Machines https://www.acmicpc.net/problem/14959 사전 지식 이 문제를 제대로 푸려면 다음 두 문제를 먼저 풀고 올 필요가 있다. https://www.acmicpc.net/problem/16570 16570번: 앞뒤가 맞는 수열 수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계 www.acmicpc.net https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다...
매내처 알고리즘(Manacher's algorithm) 우린 다음과 같은 문제를 해결한다고 해보자. 어떤 문자열의 부분 문자열 중 팰린드롬인 것의 개수를 구하기. 흔히들 배우는 방법으로는 $O(N^{2})$에 해결할 수 있는 동적 계획법이 있다. 하지만 N이 10000을 넘어간다면 메모리와 시간에 상당한 제약을 받게 될 것이다. 매내처 알고리즘은 선형 시간 복잡도 $O(N)$에 풀 수 있는 해법을 제시한다. 중요 아이디어는 다음과 같다. 과정은 뒤로 미뤄두고 우리는 탐색하고 있는 인덱스 i의 이전에 존재하면서 마지막 인덱스 j가 j > i인 팰린드롬을 구했다고 하자. 그리고 이 팰린드롬이 커버하고 있는 범위는 현재 인덱스 i를 포함하여 더 넓게 차지하고 있는 상황이다. 그러면 그 팰린드롬의 중심을 기준으로 양 옆에는 서로 같은 자식 팰린드롬이 있을 수 있다...
KMP(Knuth Morris Pratt) 알고리즘 복습 노트 들어가기 앞서 이 포스트는 게시자가 KMP를 공부하면 뒤돌아서면 바로 까먹는 이유로 빠르게 복습하기 위해 만들었다. 처음부터 공부하고자 하는 이는 나동빈 유튜브에서 매우 직관적이고 잘 설명하고 있으므로 유튜브를 먼저 시청할 것을 강력 권고한다. https://youtu.be/yWWbLrV4PZ8 KMP의 목적 찾고자 하는 문자열을 시간 복잡도와 공간 복잡도 각각 $O(|N| + |M|)$로 찾게 해 준다. $O(|N| + |M|)$를 실현하는 원리 KMP는 접두사와 접미사가 일치할 때 그만큼 점프하여 속도를 개선하는 데 있다. 예를 들어 문자열 abahkaba 같은 경우 접두사와 접미사가 같은 부분은 abahkaba -> aba가 된다. 예시를 통한 알고리즘 이해 abacaaba를 가지고 접두사와 접미사..

티스토리툴바