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

Trie 구조

문자열을 쉽게 탐색하기 위한 tree형태의 구조

트라이 구조

예를들어, 문자열 [Joe,John,Johnny,Jane,Jack]로 트라이 구조를 만들었을때이다.

이 트라이 구조는 최대 장점은 '검색'에 있다.

[Joe,John,Johnny,Jane,Jack] 에서 'Joe'의 유무를 찾으려면 단순하게는 문자열 전체를 search해야한다.

찾으려는 문자 길이를 m, 문자열 길이를 n이라하자.

각 문자열에 character를 J,o,e와 하나씩 비교해야하고, 이것을 n번 반복하니 총 O(nm)의 복잡도가 발생한다.

반면 trie구조를 사용하면,

문자 길이 m인 O(m) 의 복잡도면 충분하다.

---

Trie 구조는 내가 생각하기엔, 딱히 tree구조와 다른것은 없어보인다.

다만, 문자가 끝나는 것을 알려줘야하기 때문에 문자가 끝날때 terminal이라는 flag를 사용한다.

코드를 보면 더 간단해 지지 않을까..

 

Node 클래스에서 flag 는 terminal flag를 의미한다.

Trie는 크게 2개의 함수를 포함한다 (starts with은 덤,,)

insert 와 search !

구현은 간단하니 이해가 될것이라 생각 (사실 설명하고 싶으나.. 그냥 tree와 거의 똑같..)

class Node:
    def __init__(self,key,flag=None):
        self.key=key
        self.flag=flag
        self.children={}

class Trie:
    def __init__(self):
        self.head=Node(None)#root
    def insert(self,string):
        cur_node=self.head#항상 root부터 시작
        for i in string:
            if i not in cur_node.children:
                cur_node.children[i]=Node(i)
            cur_node=cur_node.children[i]
        cur_node.flag=string#terminal
    def search(self,string):
        cur_node=self.head#서치도 항상  root
        for i in string:
            if i not in cur_node.children:
                return False
            cur_node=cur_node.children[i]
        if cur_node.flag!=None:#if terminal
                return True
        return False            
    def starts_with(self,prefix):
        cur_node=self.head
        result=[]
        for i in prefix:
            if i in cur_node.children:
                cur_node=cur_node.children[i]
            else:
                return None
        candidate=list(cur_node.children.values())
        while candidate:
            cur=candidate.pop()
            if cur.flag != None:
                result.append(cur.data)
            candidate+=list(cur.children.values())
        return result

---

trie로 풀면 쾌감쩌는 문제 🦄

programmers.co.kr/learn/courses/30/lessons/60060

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

 

문제를 저엉말 간단히 설명하자면,

문자열 과 접두사&접미사 문자열을 비교해서 해당문자열의 문자들이 속하는 접두&접미사들을 카운트하는 것이다.

 

아무리 요리조리 방법을 써봐도,  for 문을 2번 쓰는건 피할 수 없었고..

효율문제에서 계속 미스가 났다.

 

문자열이고... pre/postfix 검색이라면~ trie!

 

 

참고|

blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0