devbelly

문제 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개..