python 리스트를 이용해 trie 구현하면서 개념 익히기

python에서는 trie가 class로 구현된 경우가 많아 꺼렸는데... 배열로 구현하는 법을 익혀서 기록해보기 https://deepdata.tistory.com/659 문자열 자료구조 Trie 알고리즘 기본기 배우기1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자deepdata.tistory.com https://blog.encrypted.gg/1059 [실전 알고리즘] 0x1F강 - 트라이안녕하세요, 드디어 마지막 강이라니 가슴이 웅장해집니다. 마지막인만큼 난이도도 끝판왕일 수 있지만 개..

• format_list_bulleted 고급 자료구조
• · 2024. 5. 14.
• textsms

희소 배열(sparse table) 자료 구조 배우기

https://cp-algorithms.com/data_structures/sparse-table.html Sparse Table - Algorithms for Competitive Programming Sparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compu cp-algorithms.com infossm.g..

• format_list_bulleted 고급 자료구조
• · 2023. 8. 21.
• textsms

문자열 자료구조 Trie 알고리즘 기본개념 이해하고 삽입, 추가 직접 구현해보기

1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자 할때, d['hello']같이 key로 접근해서 1인지 확인해보면 되니까 O(1)로 바로 찾을 수 있는 장점이 있다 하지만 공간복잡도 측면에서 단어가 100만개가 있다면 100만개의 공간이나 필요할 것이다  2. Trie 자료구조 Trie 자료구조는 효율적인 공간복잡도를 가지면서도, 시간복잡도도 충분히 효율적으로 만드는 문자열 저장 자료구조라고 할 수 있다. dictionary보다 조금 느리지만, 단어를 찾는데 단어를 구성하는 알파벳(문자)개수만..

• format_list_bulleted 고급 자료구조
• · 2023. 1. 23.
• textsms