CP Algorithm & Knowledge (30) 썸네일형 리스트형 KMP 알고리즘으로 부분 문자열 효과적으로 제거하기 이 포스트에서는 USACO 문제인 Censoring에서 문제 풀이를 통해 KMP와 동적 계획법으로 특정한 부분 문자열을 전체 시간 복잡도 $O(N + M)$로 처리하는 방법을 알아본다. https://www.acmicpc.net/problem/10747 10747번: Censoring Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inap.. 매내처 알고리즘(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를 가지고 접두사와 접미사.. C++ fast io 코드 PS 혹은 CP를 하다 보면 이론상 통과가 힘든 시간 복잡도이지만 그럼에도 불구하고 시도를 하고 싶을 때 대표적으로 IO 오버헤드를 최대한으로 줄이는 방법을 채택한다. 이 포스트에서는 버퍼같은 이론적 배경은 접어두고 즉시 사용할 수 있는 코드를 제공하고자 한다. 첨부한 코드는 USACO GUIDE에 수록된 코드를 일부 개조했으며 리눅스 환경이 아닌 곳에서도 바로 사용할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6.. 수열의 홀짝성 feat. [ICPC] 백준 5000 - 빵 정렬 수열의 홀짝성 일단 순열 {1, 2, 3}이 있고 6! 만큼 순열을 나열하는 경우를 살펴보자. 각 순열에 대해 다음과 같은 연산을 시행한다고 해보자. 순열에서 임의의 두 인접한 원소를 교환한다.(이하 transposition) 여러 번 하다 보면 흥미로운 현상을 관찰할 수 있다. transposition을 반복하다 보면 어떤 순열 a에서 순열 b로 만들 수 없는 경우가 존재한다는 것이다. 여기서 두 집합을 살펴보자. 집합 A에 속한 순열과 집합 B에 속한 순열들은 transposition으로 서로 다른 집합에 속한 순열로 만드는 것이 불가능하다. 그리고 각 집합에 속한 순열들에 대해 inversion number를 세면 공통점을 발견할 수 있다. *inversion number: 수열의 i번째 원소 $a.. 이전 1 2 3 4 5 6 다음
