티스토리

레프네 약방
검색하기

블로그 홈

레프네 약방

tamref.com/m

졸업하고 싶다

구독자
11
방명록 방문하기

주요 글 목록

  • 접미사 배열의 조합적 성질 이 글은 GPT-4.5가 최종 편집하였다. 썸네일의 suffix array도 GPT가 그렸지만, 아쉽게도 틀렸다.길이가 $n$인 문자열 $S$의 접미사 배열(Suffix Array, SA)이란, $S$의 모든 접미사(suffix) $S[i\dots]$들을 사전 순으로 정렬했을 때의 시작 인덱스 순열을 말한다. 예를 들어, $S = aba$라면 접미사들을 사전 순으로 정렬했을 때 $a koosaga님의 글을 참고하면 좋다.Inverse Problem어떤 순열 $\sigma$가 주어졌을 때, 이를 접미사 배열로 하는 문자열은 몇 개나 존재할까? SA는 $S[\sigma(0)] \le \dots \le S[\sigma(n-1)]$라는 관계를 나타내므로, 우리는 이 등호가 언제 성립하지 않는지만 판별하면 된다... 공감수 0 댓글수 0 2025. 5. 8.
  • Persistent Data Structure PS를 하면서 Persistent라는 단어가 붙는 자료구조는 Persistent Segment Tree 외에는 보기 힘들지만, 사실 Persistent라는 prefix는 꽤나 일반적인 의미를 지닌다. 어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 그 자료구조를 'Persistent하다'고 한다. 조금 더 세부적으로 분류하면, 이전의 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하지만 최종 상태를 제외하면 모두 read - only라면 Partially persistent 혹은 Confluently persistent라고 한다. 분류는 거창하지만 구현이 그렇게 난해한 건 아니다. 일반적인 방법론은 Fat node, Path co.. 공감수 0 댓글수 0 2018. 10. 11.
  • ???한 자료구조, 알고리즘 모음 아직 공부중인 자료구조 / 알고리즘들이다.세상에 똑똑한 사람이 너무 많아.. 1. DP tricks 1.1. Alien Trick (Wang Qing-Shi Binary Search) 구사과 블로그imeimi 블로그원문을 구할 수 있는 곳 (중국어) IOI 2016 AliensNAIPC 2017 Blazing new trails 1.2. dynamic CHT (without pointer) 일명 성적CHT. 본지가 언제인데 아직도 못 짜냐 ㅡㅡ 1.3 Li-Chao tree Doc2 csacademy 연습문제 1.4. Knuth Optimization with rigorous proof 2. Offline Dynamic Tricks 2.1. Offline Dynamic Connectivity 2.2. D.. 공감수 1 댓글수 4 2018. 9. 9.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.