알고리즘 개념 - Trie

Trie 트라이

알고리즘 문제를 풀다가 보면 문자열의 접두사를 활용해 문제를 풀어야 하는 요소가 존재했다. 그 때마다 항상 트라이라는 것을 한번 외워봐야지 하지만 뒤로 미루는게 습관이 되서 안하다 안하다 결국 이제야 하게 되었다. 잘 정리하는 것보다는 내가 학습을 하는 것에 초점을 두어 글을 작성하도록 하겠다.

트라이 개념

• 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 이다. Radix Tree or Prefix Tree라고도 부른다.

파이썬 구현하기

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

class Trie(object):
	def __init__(self):
    	self.head = Node(None)
    
    def insert(self, string):
    	curr_node = self.head
        
        for char in string:
        	if char not in curr_node.children:
            	curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
    	
        cur_node.data = string
    
    def search(self, string):
    	curr_node = self.head
        for char in string:
        	if char in curr_node.children:
            	curr_node = curr_node.children[char]
            else:
            	return False
		
        if curr_node.data != None:
        	return True

• 이렇게 한번 따라서 적어봤는데 손으로 자주 필사해보며 외워야겠다.