밍쎄의 코딩공간

이번 코테는 처음부터 끝까지 Trie 였다. 보자마자 Trie 라는 것을 파악하는 건 성공, but 매끄럽게 코드를 구현하기는 힘들었다. -------- Trie 란? Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다. 위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 된다. 그러나 같은 이진트리 형태 이어도 문자열을 저장하고 있다면 문자열의 길이가 M일 때, O(M*logN)의 시간 복잡도를 가지게 된다. 이러한 문제를 해결하기 위해 Trie를 사용하는 것이다. Trie는 루트 노드는 비어있고 첫 번째 자식 노드부터 문자열의 첫 단어가 저장된다. 현재 위 그림의 Trie에 저장된 문자는 cap, code, kakao, kai..