카테고리 없음
[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day4) : 자료구조(Trie 트라이)
트라이(Trie)Prefix Tree, Digital Search Tree, Retrieval Tree문자열을 빠르게 검색할 수 있는 자료구조K진 트리 구조 (문자열 K를 담을 수 있는 트리)단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다.트라이의 root 노드는 항상 공백문자열 상태이다. 구축하기트라이 노드 설계class Node { Node child[]; boolean isWord; }단어 사전의 입력할 단어를 트라이에 삽입루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식..
