본문 바로가기

Algorithm/F. Strings

 (8)
91. Z Algorithm Z 알고리즘(Z Algorithm)은 문자열의 각각의 접미사와 전체 문자열의 가장 긴 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 이것도 설명이 간단하지는 않은데, 다음과 같은 예시를 보면 이해하기 쉽다. 문자열 $s = \ ^\shortparallel \mathsf{ababcacababa}^\shortparallel$이고 $|s| = n$이라고 하자. $k$ $s_k$로 시작하는 접미사 접미사와 전체 문자열의 가장 긴 공통 접두사 $z(k)$ $0$ $\mathsf{ababcacababa}$ $\mathsf{ababcacababa}$ $12$ $1$ $\mathsf{babcacababa}$ (없음) $0$ $2$ $\mathsf{abcacababa}$ $\mathsf{ab}$ $2$ $3$ $\m..
89. Manacher Manacher's Algorithm은 문자열에 존재하는 팰린드롬 부분 문자열을 빠르게 찾을 수 있는 알고리즘이다. 팰린드롬(회문, Palindrome)은 전체를 뒤집었을 때 원래 상태와 같은 수열, 문자열 등을 의미하며, 팰린드롬 부분 문자열은 부분 문자열 중 팰린드롬인 것을 의미한다. 단어 Manacher는 이 블로그에서 소개하는 모든 용어들 중에 거의 유일하게 한국어 발음이 불분명하며, 'Ma-' 부분은 '마' 또는 '매', '-na-' 부분은 '나', '내', 또는 '니', '-cher' 부분은 '처', '쳐', 또는 '커' 등으로 발음이 달라지는 등 사람마다 읽는 방식이 매우 다양하다. 백준의 '단계별로 풀어보기' 탭에서는 '마나허'라고 표기한 적도 있었으나 토론 끝에 '매니커'로 바뀌었다. 문..
88. Rabin-Karp 라빈-카프 알고리즘(Rabin-Karp Algorithm)은 해싱을 이용하여 문자열을 검색하는 알고리즘이다. 이 알고리즘은 주로 부분 문자열들이 동일한지의 여부를 빠르게 판별해야 하는 경우에 쓰이는데, 각각의 부분 문자열을 일일히 해싱하는 것은 시간이 너무 오래 걸리므로 더 빠른 방법이 요구된다. Rabin Fingerprint는 이러한 문제를 해결할 수 있는 해싱 방법으로, 다음과 같은 형태로 나타낼 수 있다. $$f(x, n) = \sum_{k=0}^n(s_k \cdot x^k) = s_0 + s_1x + s_2x^2 + \ldots + s_{n-1}x^{n-1} + s_nx^n$$ 일반적인 라빈-카프 알고리즘은 이 식을 약간 변형해서 다음과 같이 만든 다음 해시값을 계산한다. $$f(x, n) = ..
87. Failure Function & Knuth-Morris-Pratt 앞선 글에서 문자열의 표현에 관한 내용들을 다루었고, 이제부터는 문자열의 검색에 대한 내용을 다룬다. 본격적인 내용을 설명하기에 앞서 용어를 정리한다. 어떤 문자열의 부분 문자열(Substring)은 문자열의 앞과 뒤에서 각각 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 이 글에서는 문자열 $s$의 부분 문자열을 $s[i, j]$로 표기하며, 이는 $s$의 $i$번째 ~ $j$번째 문자로 이루어진 부분 문자열이라는 뜻이다. 문자열의 인덱스는 0-based이다. 문자열의 접두사(Prefix)는 문자열의 뒤에서 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 문자열의 접미사(Suffix)는 문자열의 앞에서 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 문자열 $s$..
86. Regular Expression 정규 표현식(정규식, Regular Expression, Regex/Regexp, Rational Expression)은 규칙을 가진 문자열의 집합을 표현하기 위해 사용되는 형식 언어이다. 일부 프로그래밍 언어와 텍스트 편집기는 문자열의 검색 및 치환 등을 위해 정규 표현식을 지원하고 있으며, 표준 라이브러리에 정규 표현식이 제공되지 않는 대부분의 프로그래밍 언어는 별도의 라이브러리를 통해서 정규 표현식을 사용할 수 있다. python과 JAVA는 표준 라이브러리에 정규 표현식이 제공되며, C++의 경우 C++11 표준에 정규 표현식이 추가되어 C++11 표준부터는 정규 표현식을 사용할 수 있다. C에도 정규 표현식이 존재하지만 POSIX 환경에서만 사용이 가능하다. 정규 표현식의 기본적인 문법은 다음과..
85. Hashing 해싱(Hashing)은 길이가 정해지지 않은 임의의 데이터를 길이가 정해진 데이터로 변환하여 표현하는 것을 말한다. 일반적으로 해싱의 대상이 되는 '길이가 정해지지 않은 임의의 데이터'는 문자열인 경우가 많으며, 해싱의 결과인 '길이가 정해진 데이터'는 정수값으로 나오는 경우가 많다. 이런 이유로 이 블로그에서는 문자열을 정수로 해싱하는 경우만 다루지만, 해싱의 대상과 결과가 항상 이렇게 될 필요는 없다. 해싱에 대해 알아보기 전에 왜 해싱이 필요한지를 알아야 한다. 문자열을 해싱하는 것이 그다지 특이한 일이 아니라는 것은 문자열을 그대로 사용할 경우 큰 단점이 생기는 상황이 있다는 것을 의미한다. 이 상황은 문자열을 검색하는 상황이다. 정수나 실수 데이터를 비교할 경우 단순히 한 번(경우에 따라 두 번..
84. Parsing 파싱(구문 분석, Parsing)은 문장을 적절한 구성 성분으로 분해한 다음 그것을 분석하여 문장의 구조를 정하는 것이다. PS에서의 파싱은 이보다 조금 더 제한적인 의미로 사용되는 경우가 많으며 이때의 의미는 주로 '문자열을 기준에 따라 여러 데이터로 구분하여 원하는 형태로 만든 뒤 적절하게 처리하는 것'으로 해석할 수 있다. PS에서 파싱은 수와 수가 아닌 문자들이 섞여 있을 때 이것들을 분리할 경우, 특정한 기호가 정해져 있고 그것이 문자열에 등장하는지의 여부를 사전에 알 수 없거나 등장하는 위치가 변할 수 있는 경우, 길이가 정해지지 않은 문자열이 화이트 스페이스 이외의 다른 문자로 구분되어 입력되는 경우 등에 사용된다. 그밖에 다른 유형도 존재하며 각각의 유형을 적절하게 처리해야 데이터를 편리하..
83. Strings Intro 카테고리 F에서는 문자열 및 이와 관련된 몇 가지 알고리즘에 대해서 다룬다. 다루는 내용은 다음과 같다. 파싱(Parsing) 해싱(Hashing) 정규 표현식(Regular Expression) 실패 함수, KMP(Failure Function & Knuth-Morris-Pratt) 라빈-카프(Rabin-Karp) 매내처(Manacher) 트립, 트라이(Treap & Trie) Z 알고리즘(Z Algorithm) 접미사 배열, LCP 배열(Suffix Array & LCP Array) 아호-코라식(Aho-Corasick) 대부분의 문자열 알고리즘은 문자열의 표현, 문자열 검색의 두 가지 측면에서 이해할 수 있으며, 정교한 부분이 많아서 다소 어렵거나 복잡하게 느껴질 수도 있지만 그만큼 성능이 뛰어나다...

티스토리툴바