PS하는 kdy

이번에는 지난 글에서 구현하는 방법을 알아본 접미사 배열과 lcp 배열을 어떻게 활용하는지 알아볼 것이다.문제를 풀어보기 전에는 suffix array와 lcp array가 도대체 어떤 의미를 가지나.. 싶기도 한데, 우리는 보통 접두사, 접미사보다도 부분 문자열에 관련된 문제를 많이 해결하게 된다. 이때, 우리가 주목해서 기억해야 하는 것은 부분 문자열은 결국 접미사의 접두사라는 것이다. 그러면 suffix array를 구했고, suffix array에서 lcp를 구한 것은 공통된 접미사의 접두사, 즉 공통된 부분 문자열에 관한 정보를 얻었음을 의미한다. https://www.acmicpc.net/problem/1605이 문제는 지난번 라빈 카프를 설명했을 때에도 다루었던 문제로, 부분 문자열 내에서 ..

이번에 다뤄볼 알고리즘은 해싱, 그 중에서도 라빈 카프 방식에 대해 살펴볼 것이다. 서론은 짧게 하고 빠르게 본론으로 넘어가보자.해싱 (Hashing)해싱은 문자열을 해시 함수에 넣어서 특정한 값으로 추출하는 것을 의미한다. 이때 가장 중요한 것은 같은 문자열을 같은 해시 함수에 여러 번 넣어 추출한 결과는 일정해야 한다는 점이다. 해싱을 하면 어떤 부분이 좋을까? 바로 비교 시간복잡도를 줄일 수 있다. "abcba"라는 문자열과 "abcbd"라는 문자열이 서로 같은지 다른지 비교하려고 한다. 일반적으로는 문자열의 가장 앞부터 비교하면서 5번째 문자까지 비교했을 때 비로소 두 문자열이 다르다는 것을 판단할 수 있다. 하지만 해싱을 이용해서 미리 두 문자열에 대해 정수 형태로 값이 나오는 해시 함수 결괏값..

지난 글에서 KMP 알고리즘의 원리와 시간복잡도를 알아보았고, 이를 바탕으로 문자열을 검색하는 기본 문제를 풀어보았다. 이번 글에서는 KMP 알고리즘을 활용하는 문제들을 몇 가지 살펴볼 것이다. https://www.acmicpc.net/problem/1305 문제는 단순하다. 광고 문구가 AABA이고 광고판이 9글자까지 표현 가능하다면 광고판에는 광고 문구를 반복해서 이어붙인 문자열이 보이고, 1칸씩 이동하는 형태이다. 즉, 아래와 같이 광고판에 문구가 뜨는 것이다.[A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A] 광고판의 어느 순간의 모습이 주어지면 광고 문구로 ..