문자열 핵심 자료구조 suffix array O(NlogN) 최적화 배우기

1. 최적화 이전 문자열 자료구조 suffix array를 만드는 manber-myers 알고리즘은 $O(Nlog^{2}N)$의 시간복잡도를 가진다. https://deepdata.tistory.com/967 문자열 핵심 자료구조 suffix array와 lcp(longest common prefix)배열 구하는법 배우기(Manber-Myers, kasai) https://cp-algorithms.com/string/suffix-array.html#definition Suffix Array - Algorithms for Competitive Programming Suffix Array Definition Let $s$ be a string of length $n$. The $i$-th suffix of ..

• format_list_bulleted 알고리즘/문자열 알고리즘
• · 2023. 8. 17.
• textsms

파이썬 pair type stable sort 배우기(tuple counting sort)

https://blog.naver.com/jqkt15/222031601969 [알고리즘] Counting Sort for Stable Sort - Pair Type (ppt, 소스코드) * 소스 코드 * blog.naver.com 1. stable counting sort 원소가 (첫번째 원소, 두번째 원소)의 튜플로 이루어졌을때, 이를 stable하게 counting sort하는 방법 https://deepdata.tistory.com/367 조건을 만족할때 매우 빠른 정렬 - counting sort 1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2023. 8. 16.
• textsms

조건을 만족할때 매우 빠른 정렬 - counting sort

1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수로 표현할 수 있는 자료에 대해서만 적용가능하다 - 각 항목의 발생 횟수를 기록하고자 정수로 인덱스 되는 카운팅 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다. 전제조건이 중요함 예를 들어 "0에서 1000이하의 정수이다" 이런 제한조건을 알고 있어야함 음수있으면 안된다는데.. 있어도 될것 같기는 한디 시간복잡도는 O(n+k)의 선형시간(n은 리스트의 길이, k는 정수의 최댓값) 2. 알고리즘 과정 2-1) 주어진 리스트에 등장하는 정수들이 각각 몇개 ..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2022. 8. 11.
• textsms