🆃 트라이(Trie) 자료구조

🗣 서론

2020 카카오 블라인드 채용 1차 코딩 테스트 문제에서가사 검색 문제를 풀었다. 테스트 케이스도 정상적으로 돌아가서 제출 했는데 답은 맞았지만 효율성 부분에서 3개가 시간 초과되었다. 리팩토링을 했지만 결과는 같았다.

시간이 지나도 도저히 생각이 안나서해설을 봤다.

트라이 자료구조 또는 이분 탐색등 보다 효율적인 방법을 이용해 코드를 작성할 수 있는지 파악

자료구조에 대한 학습이 부족한 탓인지 트라이는 처음 들어봐서 이번 기회에 정리해보려고 한다.

📌 트라이(Trie)란?

많은 문자열 중에 특정 문자가 포함되어 있는지 검색하고 싶으면, 하나씩 비교하면서 알아내는 방법이 있다. 하지만 이러한 방법은 매우 비효율적이다. 트라이 자료구조를 사용하면 매우 빠른 속도로 문자열을 검색할 수 있다. 문자열의 최대 길이가 M이라고 하면, O(M)의 시간복잡도를 가진다. 따라서 네이버의 자동 완성 기능과 같이 문자열을 저장, 탐색하는데 유용한 자료구조이다.

Retrieval 에서 유래되어 프레드킨이 "Trie" 라고 이름을 붙였다.
발음은 트라이, 트리 두 개다 쓰이는데 "Tree" 와 똑같은 발음을 가지고 있어 구분하기 위해 "트라이" 라고 불리고 있다.

📌 트라이(Trie)의 구조

사전에서 "apple" 을 찾아보려면 아래와 같은 순서로 찾을 수 있다.

1. 맨 앞글자 'a' 로 시작하는 부분을 찾는다. (a)
2. 다음 'p' 로 시작하는 부분을 찾는다. (ap)
3. 다음 'p' 로 시작하는 부분을 찾는다. (app)
4. 다음 'l' 로 시작하는 부분을 찾는다. (appl)
5. 다음 'e' 로 시작하는 부분을 찾는다. (apple)

기본적으로 K(문자열의 개수)진 트리 구조를 가지며, 위와 같이 논리적으로 컴퓨터에 적용한 것이 트라이 자료구조이다.

그림 [1] - 트라이 구조

그림 [1]을 보면 app을 검색했을 때 3개의 문자열(apple, appreciate, apply)이 나오게 되는데 문자열을 저장하는 트라이 자료구조를 보면 위와 같다.

저작자표시

'Data Structure' 카테고리의 다른 글

🆃 트라이(Trie) 자료구조  (0)	2020.03.20