자료구조1 [Algorithm] Trie (Python code) Trie많은 문자열 데이터들이 있을 때 이를 효율적으로 다룰 수 있게 해줍니다.단편적 예시로는 영어사전이 있습니다.아래와 같은 데이터가 있습니다. APPLEAPPLYBANANAKIWI 이 데이터에서 특정 문자열이 이미 존재하는지 찾는다 가정할 때단순한 방식으로는 특정 문자열을 모든 문자열과 비교하는 방법이 있습니다.이 때 시간복잡도는 (국어사전의 모든 문자열의 수 x 특정 문자열의 길이) 이 됩니다. 하지만 Trie 를 사용하게 되면 특정 문자열의 길이만으로 평가할 수 있습니다.Trie 는 최상위 노드부터 시작해 공통적인 경로는 하나의 경로로 관리합니다.APPLE, APPLY 로 예를 들자면 APPLE 과 APPLY 는 APPL 이라는 공통경로를 가집니다. 동작동작은 크게 insert, find 두 .. 2024. 9. 25. 이전 1 다음
