반응형 자료구조1 [Algorithm] 트라이(Trie) 트라이(Trie)" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스Trie는 탐색트리의 일종으로 특정 문자열이 포함되어있는지 등을 찾는데 효과적인 자료구조다. 예를 들어 영어로 된 여러 단어가 N개 주어지고, 여러개의 접두어가 M개 주어진다.이때, M개의 접두어로 시작하는 단어가 몇 개 있는지 구하는 경우를 생각해보자. 단순하게 반복문으로 구하게 되면 (M개의 접두어)*(N개의 단어)*(접두어와 단어를 비교) 의 반복을 하게 된다.M, N, 접두어 단어의 길이가 작으면 상관없지만 조금이라도 커지면 시간복잡도가 크게 늘어나게 된다. 이러한 반복을 줄이는데 효과적인 자료구조가 Trie다. 이제 [HILL, HIGH, HELL, HELLO, HELLT] 라는 단어를 Trie 구조로 .. 2024. 5. 24. 이전 1 다음 반응형
