devbelly

문제 https://www.acmicpc.net/problem/9249 알고리즘 Suffix Array 풀이 LCS문제입니다. 주어진 두 문자열$A, B$를 합친 후 LCP를 구하게 되면 답을 얻을 수 있습니다. 이때 주의해야 할 점이 있습니다. 인접한 LCP를 검사할 때, 하나의 Suffix는 $A$의 일부를 포함해야 하지만, 나머지 Suffix는 $A$를 포함해선 안된다는 점입니다. 이점을 유의하지 않으면 $A$ 또는 $B$ 내에서만 LCP를 뽑아버리므로 두 문자열의 공통부분 문자열을 얻지 못하게 됩니다. 시간 복잡도는 Suffix Array와 LCP를 구해야 하므로 $O(NlogN+N)$입니다. 코드 #include #define rep(i,n) for(int i=0;i

문제 https://www.acmicpc.net/problem/11479 알고리즘 Suffix Array 풀이 열심히 구한 Suffix Array와 LCP로 우리는 무엇을 할 수 있을까요? 그중 하나인 부분 문자열과 관련된 문제들입니다. 이 문제에선 서로다른 부분 문자열의 개수를 묻고 있습니다. 부분 문자열이란 것은 달리 말하면 Suffix의 Prefix입니다. Banana를 예로 들어보겠습니다. 모든 Suffix를 나열해보면 {Banana,anana,nana,ana,na,a} 가 될 겁니다. 여기서 부분 문자열을 얻기 위해 각각의 Suffix들에 대해 Prefix를 보면 되겠죠. 모든 Suffix 중 Suffix "anana"에서 얻을 수 있는 부분 문자열은 {a,an,ana,anana,anana} 입..

문제 https://www.acmicpc.net/problem/9248 알고리즘 Suffix Array 풀이 문자열에서 가장 어려운 알고리즘인 Suffix Array입니다. 이 글에선 제가 해당 알고리즘을 공부할 때 어려웠던 부분 및 이해하기 위한 선행지식을 간단하게 정리하려고 합니다. Counting sort & Radix sort Counting sort는 non-comparison sort으로 $O(N)$에 정렬을 해주는 알고리즘입니다. 주로 정렬할 데이터에 대한 사전 지식이 있을 때 사용합니다. 사전 지식이란 $k$이하의 정수를 배열을 정렬하라는 문제에서 $k$이하의 정수라는 조건을 의미합니다. 방법은 stable 한 방법과 unstable한 방법이 있는데, 정렬할 데이터가 단일 데이터(정수 1개..