[SW 정글 23일차] 트라이 (Trie) 알아보기

오늘은 아래의 문제를 풀면서 새롭게 안 트라이(Trie)에 대해 정리해보려고 한다.

문제를 통해 알게 되어 내가 공부한 것을 정리하는 것도 있지만 내가 평소에 검색기능을 이용하면서 자동완성을 많이 경험하곤 했는데 이 자동완성에 쓰인 알고리즘을 알았다는 것이 신기해서 정리하는 것도 있다.

 

 

 

1. 트라이(Trie)란?

트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.

여기서, 트리 형태에 대해서는 아래의 글에 정리했으니 혹시 모르겠다면 참고하면 좋을 것같다.

https://straw961030.tistory.com/192

[SW 정글 13일차] 트리 구조와 이진 트리

조금 더 개념을 자세히 설명하면 Trie라는 단어가 붙게된 이유는 retrieval tree에서 retrieval의 trie만 따온 것이다.

트라이는 문자열을 Key로 사용하는 동적인 set 또는 연관 배열을 저장하는 트리의 확장된 자료구조로

우리가 jungle이라는 단어를 찾고자 한다면 j를 먼저 찾고 u 찾고 n 찾고... 이렇게 순서대로 찾을 것이고 이러한 개념을 적용한 것이 트라이(trie)구조이고 문자열을 빠르게 찾을 수 있게 해준다.

 

그러면 직접 단어를 생각해서 트라이에 어떻게 들어가는지 시각적으로 보자.

spring, spot 2가지 단어를 트라이 구조에 저장하면 아래와 같다.

트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다.

저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다.

 

 

트라이(Trie)를 사용하는 이유는 문자열을 탐색할 때 하나씩 비교하면서 탐색하는 것보다 시간복잡도 면에서 효율적이기 때문이다.

트라이를 생성할 때에는 O(M*L) (M: 총 문자열 수, L: 가장 긴 문자열 길이)시간복잡도를 가진다.

트라이를 생성 후에 문자열을 검색할 때에는 O(L)만큼의 시간복잡도를 가진다.

시간복잡도 면에서 효율적인 것은 트라이의 큰 장점이지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있어야 하기 때문에 저장 공간의 크기가 크다는 단점이 있다.

 

 

 

 

2. 트라이(Trie) 구현하기

트라이를 만들고 트라이에 문자열을 삽입하고 원하는 문자열을 검색하는 코드를 구현해보자.

파이썬에서는 딕셔너리를 활용하여 트라이를 만들 수 있지만 이렇게 직접 구현해보는 것도 좋은 것같다.

class TrieNode:
     
    # Trie node class
    def __init__(self):
        self.children = [None]*26
 
        # isEndOfWord is True if node represent the end of the word
        self.isEndOfWord = False
 
class Trie:
     
    # Trie data structure class
    def __init__(self):
        self.root = self.getNode()
 
    def getNode(self):
     
        # Returns new trie node (initialized to NULLs)
        return TrieNode()
 
    def _charToIndex(self,ch):
         
        # private helper function
        # Converts key current character into index
        # use only 'a' through 'z' and lower case
         
        return ord(ch)-ord('a')
 
 
    def insert(self,key):
         
        # If not present, inserts key into trie
        # If the key is prefix of trie node,
        # just marks leaf node
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
 
            # if current character is not present
            if not pCrawl.children[index]:
                pCrawl.children[index] = self.getNode()
            pCrawl = pCrawl.children[index]
 
        # mark last node as leaf
        pCrawl.isEndOfWord = True
 
    def search(self, key):
         
        # Search key in the trie
        # Returns true if key presents
        # in trie, else false
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
 
        return pCrawl.isEndOfWord

---

[오늘의 나는 어땠을까?]

오늘은 아침 시간을 조금 효율적으로 보냈다고 생각한다.

평소에는 못 푼 알고리즘 문제들을 이어 풀었지만 오늘은 스프링 강의를 들으며 하루를 시작했다.

다른 것을 하지말고 지금 현재 주어진 것들에만 집중하라고 했지만 남들보다 평균적으로 2시간 정도 책상 앞에 있는 나에게는 새로운 것을 배우는 시간으로 투자할 수 있다고 판단했다.

 

그리고 이렇게 하루에 알고리즘만 하는 것이 아닌 다른 주제의 공부를 하니 하루에 배운 것이 많다고도 느껴지고 아침의 시간 활용도가 높다고 느낀다.

물론 1일차이고 앞으로 쭉 하기에는 아마 힘들 수 있다.

이번 주차가 여유로워서 이렇게 다른 것에 잠깐의 시간을 투자 할 수 있는 것이지 고정적으로 시간을 투자하지는 않을 것이다.

아마 알고리즘 주차가 끝나고 B트리, 말록, 웹 서버를 만드는 프로젝트가 시작되면 그 주차에 집중하느라 시간을 다 쓸 수도 있다고 생각한다.

그래도 알고리즘 주차가 끝나도 매일 1 ~ 2문제는 풀 생각이다.

그래야 지금의 감이 죽지 않고 협력사 코딩테스트 날까지 이어갈 수 있다고 생각한다.

 

여유롭다고해서 너무 나태해지지 말고 해이해지지 말고

내가 이루고 싶은 목표, 얻고자 하는 것을 생각하며 처음 리듬을 유지하자.

 

---

<참고 자료>

https://twpower.github.io/187-trie-concept-and-basic-problem#%EC%B0%B8%EA%B3%A0%EC%9E%90%EB%A3%8C

https://www.geeksforgeeks.org/trie-insert-and-search/

https://brunch.co.kr/@springboot/75