THIS IS ELLIE

오늘은 트라이에 대해서 공부해보겠습니다. 사실 전화번호부 검색 알고리즘이 궁금해서 찾아보다가 트라이 개념이 나와서 시작하게 된 포스팅ㅇㅇ 그래서 이번 포스팅은 트라이 개념에 대해서 포스팅하고 다음은 트라이 한국어 탐색에 대해서 포스팅 예정입니다. 트라이란? 트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 검색 트리의 일종입니다. 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조입니다. 트라이의 어원? 트라이가 왜 트라이인지 궁금해서 어원을 찾아봤습니다. 트라이의 개념은 1959년에 처음 공개되었고 검색을 뜻하는 retrieval(리트리벌)의 중간 음절에서 용어를 따왔다고 합니다. 당시에는 트리(tri:)로 불렀다고 하는데 기존에 존재하는 트리..

오늘은 208번 Implement Trie문제를 풀어보겠습니다. 난이도는 중간이고 성공률은 52.1%네요. 일주일에 몇 개씩 풀고 있는데 이 문제가 첫 번째 페이지의 마지막 문제였어요. 물론 번호 왼쪽에 체크가 아닌 물음표 표시도 꽤 보이네요. 시도는 했으나 실패했던 문제도 있어서 다시 풀어봐야 하지만 하기 싫은 언젠가는 풀겠지.. 화이팅 문제를 풀기 전에 트라이에 대한 개념을 정리해보려 합니다. 트라이는 탐색 트리의 일종이며, 트리 자료구조입니다. 문자열 검색을 빠르게 해 주기로 유명합니다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하며, 루트는 빈 문자열에 연관됩니다. 문자열에 한 문자만 넣고 다음 문자는 자식 노드에서 찾도록 합니다. 즉 문자열은 세로로 저장되게 됩니다. 문자열이..