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

# 문자열을 찾을때 사용하는 알고리즘이 여러가지 있는데,

   대표적으로 KMP, 라빈카프, 보이어-무어, BruteForce, Trie등이 있다.

    전체 문자열 길이를 N, 찾고자하는 패턴길이를 M이라 하면

    BruteForce는 O(NM) / KMP는 O(N) + 전처리 / 보이어-무어는 O(N/M), 최악 O(N) / 라빈카프는 O(N)이다.

 

# 이번에 소개할 자료구조는 Trie(트라이)라고 하는 자료구조인데, 우선 Trie라는 말은

   retrieval(탐색)에서 따온 말이라고 한다.

   트라이는 트리구조를 사용해서 문자열을 저장하는데, 시간복잡도가 가장 긴 문자열의 길이를 L이라

   했을때 O(L)밖에 걸리지 않는다.

 

# 우선 'fire', 'firefox', 'frodo', 'frost', 'fry'를 저장했을 때 다음과 같은 형태로 문자열이 저장이 된다.

   문자열을 찾을때 최악의 경우에도 가장 긴 문자열의 길이 L만큼만 탐색을 들어가면 되기때문에

   O(L)이 소요된다.

 

 

# 코드를 보면 다음과 같다.

* 문자들을 저장할 Node클래스를 생성해준다.

class Node(object):
    def __init__(self, key):
        self.key = key          # 해당 문자를 key값으로 가짐
        self.children = {}      # 자식노드를 딕셔너리형태로 저장

 

* Trie클래스를 만들어주고 처음에 빈 Node를 생성하고 self.head로 가리킨다.

 

* insert메소드: insert하고자하는 string을 넘겨받아 string문자열에서 한글자마다 반복문을 돈다.

                    string의 각 글자마다 해당 글자가 자식노드에 없으면 새로운 노드를 추가해주고

                    이미 존재한다면 cur_node가 cur_node.children[해당글자]를 가리키도록 한다.

 

                    현재 string의 마지막에는 자식에 '*'을 저장해 문자열의 끝임을 알려주도록 한다.

 

class Trie:
    def __init__(self):
        self.head = Node(None)
    
    def insert(self, string):
        cur_node = self.head

        for char in string:
            if char not in cur_node.children:
                # 해당문자가 자식노드에 없을 경우 노드 추가
                cur_node.children[char] = Node(char)
            cur_node = cur_node.children[char]

        cur_node.children['*'] = True       # 문자열의 마지막에 '*' 삽입

 

* search메소드: 찾고자하는 string을 넘겨받아 insert메소드와 마찬가지로 한글자마다 반복문을 돈다.

                     이번에는 해당문자(char)가 현재노드의 자식에 존재한다면 cur_node가

                     cur_node.children[char]를 가리키도록 하고, 없다면 바로 False를 return해준다.

 

                      마지막 자식까지 탐색후에 '*'가 있다면 문자열을 찾은 것이므로 True를 return해준다.

 

def search(self, string):
        cur_node = self.head

        for char in string:
            if char in cur_node.children:
                cur_node = cur_node.children[char]
            else:
                return False

        # 트리의 끝까지 갔을때 마지막노드의 자식이 '*'이면 True 리턴
        if '*' in cur_node.children:
            return True

 

# 이 이외의 메소드들은 이제 우리가 구현하기 나름이다. 문제에 따라 접두사를 찾는 starts_with메소드를 

   구현할 수 있고, 현재 트라이에 있는 문자열들을 출력하는 print메소드를 구현할 수도 있다.

 

* 풀어볼 문제는 다음과 같다.

https://www.acmicpc.net/problem/14725

14725번: 개미굴

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/60060?language=python3 

코딩테스트 연습 - 가사 검색

 

(대부분의 문제가 플레티넘 이상이고 코테에 거의 나오지 않지만, 카카오 기출에 한번 나와서 정리해본다.)

 

# 출처: 다음 블로그를 참고했다.

https://hooongs.tistory.com/28