들어가며: "자동 완성" 기능에 대한 이야기

구글에서 어떤 단어를 검색창에 치면 그 단어로 시작하는 다른 키워드를 보여주는데요, 이런 걸 자동 완성(Autocomplete) 라고 합니다. 자동 완성을 구현 하려면 키워드들을 리스트에 담아서, 유저 인풋이 들어올 때 마다 인풋으로 시작하는 키워드를 리스트에서 빼오면 될 겁니다. 하지만, 만약 550만 개의 글을 갖고 있는 영어 위키백과의 제목들을 가지고 자동 완성을 구현하라고 한다면  (실제 일본 모 회사의 올해 인턴 모집 스크리닝 과제였음 ㅋㅋ) 리스트 따위로는 안 되고, 훨씬 더 효율적인 자료구조가 필요합니다. 오늘 배울 Trie 가 이럴 때 필요한 자료구조입니다.

Trie: 트라이? 트리? 기본적인 개념

사실 Trie 는 트리(Tree) 자료 구조의 일종입니다. 미리 말씀드리자면 Trie 에서 어떤 문자열을 검색할 때의 시간 복잡도는 O(m) 밖에 안 됩니다. (m: 문자열의 최대 길이) 그래서 다른 자료 구조에 비해 문자열을 검색하는 데 특화된 자료 구조임을  알 수 있습니다. 

위 그림은 names = ['Joe', 'John', 'Johnny', 'Jane', 'Jack'] 을 Trie 에 삽입한 결과인데요.

각 Node 는 

(1) 글자를 갖는 key = 한 글자 (ex. J, A, C, K)

(2) 단어의 마지막 글자인지를 알려주는 flag (Terminal)

로 이루어져 있습니다. 

예를 들어 John 의 경우 J > O > H > N 으로 차례대로 Trie 에 삽입이 되었고 마지막 글자 N 의 노드에는 Terminal 이라는 flag 를 박아줍니다. 이 flag 때문에 John 이 한 단어임을 알 수 있습니다. 

Johnny 의 경우 John 까지는 이미 노드가 있으니 ( J > O > H > N )원래 있는 노드를 활용하고, John 뒤에 n 과 y를 넣은 다음 y를 마지막 글자로 flag해주면 되는 겁니다.

파이썬에서 Trie 를 구현해볼까요?

첫번째. Node 구현

1. key 필드는 단어의 글자 하나를 담는 데 이용합니다. 영어라면 알파벳만 들어갈 수 있겠죠.

2. data 필드는 사실상 마지막 글자를 나타내주는 flag 입니다. 원래 boolean 형 으로 간단하게 true/false 로 구분할 수도 있지만

저는 마지막 글자인 경우에  단어 전체를 data 필드에 저장하고, 아닌 경우에는 그냥 널로 두려고 합니다. 그 이유는 밑에 구현할 starts_with 메소드 때문인데요, 곧 설명 드리겠습니다.

(즉, Jack 의 경우 J > A > C > K 에서 마지막 글자인 K 노드의 data 필드에만 "Jack" 이 들어가고, 그 외 노드의 data 필드는 널 (None) 으로 놔둡니다.)

두번째. Trie 구현

주어진 prefix 로 시작하는 단어들을 BFS로 트라이에서 찾아 리스트 형태로 반환

마지막 글자 flag 를 boolean 으로 안하고 data 필드로 한 이유가 바로 이 메소드 때문인데요... 잘 생각해보세요. BFS 로 단어들을 찾을 때 결국 마지막에 우리에게 반환되는 것은 Terminal 노드, 즉 마지막 글자입니다. 그래서 단어 자체를 알려면 BFS 경로를 역추적해야 합니다... 이 과정이 귀찮기 때문에 ㅋㅋ Terminal 노드만 찾으면 BFS 역추적 할 필요 없이 단어가 뭔지 알 수 있도록 data 필드에 전체 단어를 넣어 놓은 것이죠.

위 세 가지만 구현하면 됩니다! 아래는 제가 간단히 파이썬으로 구현해본 Trie 입니다.

(파이썬 전체 코드는 여기를 클릭하면 보실 수 있습니다.)

끝!!

학교 자료구조 수업에서는 비중이 많이 있는 놈은 아니지만, 기술 면접이나 코딩 대회에서 많이 다루어진다고 하니 열심히 공부합시다!! 우리의 핵심 목표는 Trie다 하는 것으로 정신을 차리고 나아가면 취직할 수 있는 에너지가 분산되어 우주가 나서서 도와준다는 그런 마음을 가질 수 있을거다, 그렇게 생각합니다.