Larshew's Diary Larshew's Diary

https://www.acmicpc.net/problem/26151 26151번: NATO 음성 기호와 쿼리 첫째 줄에 알파벳 대문자로만 이루어진 문자열 $ S $와 쿼리의 횟수 $ Q $가 주어진다. $( 1 \le |S| \le 200\,000; $ $ 1 \le Q \le 200\,000 )$ 이어 $ Q $개의 줄에 걸쳐 쿼리가 주어진다. www.acmicpc.net 진짜 오랜만에 푸는 백준 문제. 입사하고 난 다음 알고리즘 쪽 머리가 너무 굳은 것 같아 부담없이 하나 풀어보기로 하였다. 알고리즘 자체는 그렇게 어려운 편이 아니지만 자질구리하게 처리해야 하는게 귀찮았다. 더불어서 거의 처음으로 Visual Studio를 쓰다가 vim에서 하다보니 디버그가 익숙하지 않아 더 귀찮아졌다. 이정도면 그..

Counting Sort는 특정 문제에서 굉장히 강력한 성능을 내는데, 앞서 얘기한 suffix array에서의 정렬 또한 counting sort를 이용하여 logN이라는 귀중한 시간복잡도를 나눌 수 있다! 일반적인 counting sort는 굉장히 쉬운 반면에, pair로 되어있으면 순간 뇌정지가 온다(필자는 Radix Sort를 놀랍게도 한번도 써보지 않았다!) 하지만, 조금의 요령만 있다면 counting sort를 두 번 하는 것으로 해결된다. Remind – Stable Counting Sort 필자는 Counting Sort만 알고 Stable Counting Sort의 원리를 알지 못했어서 Pair의 Counting Sort를 이해하는데 어려움을 겪었었다. “Stable” Counting ..

어느 정도 수준있는 문제에서 많이 쓰이는 문제이다. 이 알고리즘이 메인이 된다기보다는, 다른 알고리즘(Tree DP 등등)과 짬뽕해서 조미료로 쓰이는 경우가 굉장히 많다. 최소 공통 조상이란? 다음과 같이 루트(위 그림에서 1번)가 있는 트리가 있을 때, LCP(a,b)는 a와 b를 모두 자식으로 가지는 노드들 중에서 a와 b에 가장 거리가 짧은 조상을 말한다. 예를 들어 LCP(7,9)=2, LCP(10,12)=6, LCP(7,10)=1이 된다. a가 b의 조상인 경우, 혹은 그 역인 경우 LCP의 값이 a 혹은 b가 될 수 있다(ex. LCP(7,1)=1) 일반적으로 LCP(a,b)의 쿼리가 Q개 있는 경우 DFS, BFS 등 일반적인 Search Algorithm을 사용하면 O(NQ)가 걸릴 것이다..

Suffix Array란 무엇인고? 항상 String 관련 알고리즘에 자주 등장하는 바나나의 예시를 들어보자. S = "banana" Suffix라고 함은 접미사라는 뜻인데, 끝에서부터 한 글자, 끝에서부터 두 글자 이렇게 해서 전체 글자까지 나타낼 수 있다. a - 5 na - 4 ana - 3 nana - 2 anana - 1 banana - 0 이 친구들을 사전순으로 정렬하면 a - 5 ana - 3 anana - 1 banana - 0 na - 4 nana - 2 가 된다. 이 때, [5,3,1,0,4,2]를 저장한 Array를 Suffix Array라고 한다. 어떻게 구현해? 당연히, 조금만 생각하면 O(N^2 logN) (Naive Sort), O(N^2) (Trie) 정도는 바로 생각해낼 수..

문자열 알고리즘의 대표적인 알고리즘 되시겠다. Knuth–Morris–Pratt 세 명의 첫 글자를 따서 KMP라고 불린다. 어디에 쓰는 알고리즘인고? 우리가 네이버나 구글에 검색어를 치면 검색어가 포함된 게시글을 바로바로 보여준다. 세세한 것은 다르겠다만, “banana”라는 글자를 치면 바로 “banana” 키워드가 있는 게시물을 보여준다. 게시물 하나하나에 banana가 들어가있는지 검색해줄 뿐만 아니라 banana 단어에 bold로 표시하면서 게시물에 banana가 있음을 우리에게 확인시켜주고 있다. 이를 빨리 해결하는 데 쓰는 알고리즘이 바로 KMP algorithm 되시겠다. Brute Force 알고리즘 – O(NM) S1 = “I love apple and banana” S2 = “bana..