안녕하세요. 코딩도치입니다~ 오늘은 프로그래머스에 있는 2020 카카오 블라인드 채용 : 가사 검색 문제를 풀어보려고 합니다! 위 문제는 트라이(Trie) 자료구조를 사용하여 풀어야 효율성 테스트를 통과할 수 있습니다. 먼저, 트라이(Trie) 자료구조에 대해서 알아보겠습니다. 트라이(Trie) 자료구조 트라이는 문자열을 트리 형태로 저장하는 문자열 검색에 특화된 자료구조입니다. 트라이 자료구조를 사용하게 되면 가장 긴 문자열의 길이가 N이라고 했을 때, O(N)의 시간복잡도로 문자열을 찾을 수가 있습니다. ["app", "apart", "away", "bear"] 의 문자열이 주어졌을 때, 트라이 자료구조가 만들어지는 과정은 다음과 같습니다. 트라이 자료구조는 아무 데이터도 들어 있지 않은 루트 노드부..
