Suhwanc

[자료구조] 트라이(Trie)

보통 우리가 많은 양의 정수, 실수형 배열에 대한 구간 합, 최대치 등을 구할 경우 구간 트리(세그먼트 트리, 펜윅 트리)를 만들어 O(log n) 만에 검색을 할 수 있게 된다. 하지만 문자열을 다룰 때에는 정수, 실수 등 크기가 정적인 변수들을 다루는 것과 좀 다른데 문자열의 경우 문자열 변수를 비교하는 데에 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문이다. (정수처럼 한 번에 비교가 되는 자료형이 아니기 때문입니다.) 따라서 정수형 배열에서 원하는 원소를 찾을 때 O(log n)이 걸렸다면, 같은 알고리즘으로 원하는 문자열을 찾으려면 문자열의 길이 |S|을 곱한 O(|S| log n) 이 걸리게 된다. 이런 문제를 해결하기 위해 문자열을 찾는 문제에서 우리는 더 나은 자료 구조를 찾을 ..