트라이(Trie) 란?

  • 문자열의 집합을 표현하는 트리(Tree)

    • 정보 검색(Retrieval)에서 이름을 따옴
    • E.Fredkin이 1960년에 소개함
    • 일반적인 Tree와 구분하기 위해 [trai]라고 발음
  • 접미사, 접두사 문자를 찾는데 효율적인 자료구조이다.
  • 알고리즘풀이에서 가끔 나오는 유형

왜쓰는지

  • 만약 ‘abcdefg’라는 문자가 존재할때, abc로 시작하는 문자열인지 확인하고싶다면?
    • 간단하게 앞에서부터 잘라가면서 hashmap으로 저장하는 방식을 생각 할수있다.
  • 이럴때 효율적인 방식이 트라이라는 자료구조를 사용한다.
  • 문자열을 전부 쪼개서 문자들을 일종의 트리의 경로처럼 활용한다.
  • 이를 통해 그저 hashmap으로 전부 저장할때보다, 더욱 공간과 시간 효율이 좋아진다.

어떤식으로 만들어지는지.

  • 먼저 트라이는 자식이 26개 존재하는 트리형태로 존재한다.
    • 무조건 26개로 만들거나, hashmap으로 공간효율을 높이는것도 가능
  • 검색하려는 문자들을 전부 트라이자료구조에 저장하는데, 시간은 전체 문자길이만큼 든다.
  • 특정 문자를 넣고 해당 문자가 종료된다면 flag로 표시해준다.
  • 만약 ‘test’라는 문자를 넣는다면?
    • t->e->s->t(문자가 종료됐다는 flag를 넣는다.)
    • 그러면 만약 te라는 접미사를 검색할때, t->e까지 이동하고나서 나오는 모든 자식들을 dfs로 출력하면된다.
      • 좀더 효율적으로 하고싶다면 트라이 입력시 각 노드마다 지나간 문장들을 저장하면 된다.
  • 아래에 알고리즘으로 간단하게 구현된 트라이를 확인하자.

트라이 선언하는 java 코드

  • 트라이 선언 클래스
import java.util.*;

class Trie{

    //다음 자식들
    Trie[] childs = new Trie[26];
    boolean isWord;//문장 하나가 완성되면 true

    //만약 지나간 문장들을 저장하고 싶다면?
    //Set<String> save = new HashSet<>();

    Trie(){}

    //트라이에서 입력시 다음노드를 생성하면서 입력
    public Trie next(char ch){
        //다음 노드가 없을때, 생성하고 진행
        if(this.childs[ch-'a']==null){
            this.childs[ch-'a'] = new Trie();
        }

        return this.childs[ch-'a'];
    }

    //트라이에서 입력시 지나가는 문장들을 저장하고 싶을때
    public Trie next(char ch,String word){
        //다음 노드가 없을때, 생성하고 진행
        if(this.childs[ch-'a']==null){
            this.childs[ch-'a'] = new Trie();
        }

        this.save.add(word);

        return this.childs[ch-'a'];
    }

    //트라이에서 순회할때 사용
    public Trie go(char ch){
        return this.childs[ch-'a'];
    }
}
  • 사용시

Trie tries = new Trie();


//입력
//String[] inputs 형태로 단어들이 주어졌을경우

for(String str : inputs){
    Trie trie = tries;

    //단어를 쪼개고, 순회하면서 trie에 입력한다.
    for(int i=0;i<str.length;i++){
        char ch = str.charAt(i);
        trie = trie.next(ch);
    }
    //한 단어를 전부 넣고, 종료 flag로 표시.
    trie.isWord = true;
}

어떻게 활용할까?

트라이 문제들

  • 트라이가 대부분의 채용 기업에서 많이 출제되는 유형은 아니라고 생각한다.
  • 카카오나, 알고리즘 대회에서 난도가 조금 높은 문제에서 출제되는 식으로 나온다.
    • 알고리즘 대회나갈정도면 이정돈 풀어야지 하는 느낌으로 내는거 같다.
  • 면접에서 물어보기도 한다고 하니, 어느정도 만드는 법은 알고 언제 써야지 정도는 알아둬도 좋을듯 하다.