Algorithm

Suffix Array (접미사 배열) - BeAPro

2023.04.29

이 글은 Ries 마법의 슈퍼마리오 블로그와 plzrun's algorithm 블로그 내용을 기반으로 작성하였습니다. 1. Suffix Array 1. Suffix Array란? Suffix Array는 접미사 배열로 문자열의 접미사들을 사전순으로 나타낸 것이다. Suffix Array를 활용하면 문자열 탐색을 보다 효율적으로 할 수 있다. banana는 총 6개의 접미사를 가지며 Suffix Array는 다음과 같다. Suffix Array 접미사의 시작 인덱스를 가지고 있기 때문에 [5,3,1,0,4,2]가 된다. Suffix Array를 구하는 데 걸리는 시간복잡도는 어떻게 될까? 네이브 한 방식으로 구현한다면 문자열을 비교하는데 O(n) 그리고 정렬을 하는데 O(n log n)이므로 총 O(n2 ..

Algorithm

병합정렬(Merge sort), 힙정렬(Heap sort), 퀵정렬(Quick sort) -BeApro

2023.04.25

해당 포스팅은 Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편을 보고 작성하였습니다. 1. 병합 정렬(Merge Sort) 병합 정렬은 배열을 앞 뒤 두 부분으로 나누어 정렬한 후 병합하는 정렬이다. 위는 크기 8의 병합 정렬되는 과정이다. 크기가 1이 될 때까지 쪼개지고 서로 정렬되면서 병합되는 것을 확인할 수 있다. 쪼개고 합치는데 O(log n) 정렬 할 때마다 O(n)이 걸려 총 O(n log n)이 걸린다. from typing import Sequence, MutableSequence def mergesort(a : MutableSequence)->None: def _mergesort(a:MutableSequence, left:int, right:int)->None: if lef..

Suffix Array (접미사 배열) - BeAPro

병합정렬(Merge sort), 힙정렬(Heap sort), 퀵정렬(Quick sort) -BeApro

티스토리툴바