Trie (1) 썸네일형 리스트형 트라이(Trie) : JAVA / 백준 5052 트라이 알고리즘 일반 적인 정수들은 O(1) 시간내에 비교가 가능합니다 . 1==1 ,123>4 처럼 단순연산으로 접근 할 수 있습니다. 하지만 String 같은경우에는 "ABC" == "ABCD" 를 고려하기 위해서는 최대 문자열의 길이 O(M) 시간이 걸립니다. (첫 번째 인덱스부터 계속 비교해 나가야 되기 때문입니다.) 따라서 기존 이진 트리로 정수형 데이터를 찾는데 걸리는 시간이 O(logN) 이라고한다면 문자열의 경우에는 O(MlongN) 시간이 걸리게 됩니다. 하지만 트라이 알고리즘을 사용한다면 O(M) 시간내에 자료를 찾을 수 가 있습니다. 문자열 집합 S={"BE","BET","BUS","TEA","TEN"} 을 트라이 자료구조로 표현하면 다음과 같습니다. 여기서 주황색으로 표시된 Node.. 이전 1 다음
