반응형 Trie #트라이 #알고리즘 #자료구조1 트라이(Trie)알고리즘 트라이(Trie) 트라이란 문자열 검색을 빠르게 할 수 있는 알고리즘이다. 예를 들어 영어사전이 있을 때 특정 단어가 있는 지 빠르게 찾을 수 있다. 문자열을 특정 키값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있다. 불완전한 해시 테이블의 최악의 검색속도는 모든 데이터를 다 확인하는 것으로 O(N)이지만 트라이를 사용하게 되면 문자열 길이 만큼의 O(M)의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있다. 보통 트라이 알고리즘을 사용할 때 고려해야할 점이 단어의 길이, 그리고 파생되는 노드 child개수다. 위에 영어사전으로 예를 들었는데 영어는 알파벳이 26가지로 child 노드는 26개를 갖고 있을 수 있다. 전화번호 목록같은 경우도 0부터 9가지.. 2020. 4. 7. 이전 1 다음 반응형
