자료구조 (1) 썸네일형 리스트형 트라이 (Trie) 구조 코딩테스트 연습 - 가사 검색 programmers.co.kr 2020년 카카오 코딩테스트 기출 문제를 풀다가 트라이라는 구조가 나와서 정리하고 넘어가본다. - 트라이는 문자열의 집합을 표현하는 트리 자료구조다. 주어진 문자열의 최대길이를 M이라고 할 때, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있다. (개꿀) 문제에 나온 예시대로 ["frodo", "front", "frost", "frozen", "frame", "kakao"]를 트라이 구조에 저장하면 아래와 같이 된다. 네모로 표시한 건 종료 노드다. 해당 위치까지의 문자열이 트라이가 표현하는 집합에 포함되어 있다는 걸 나타낸다. 이처럼 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 이 노드가 종.. 이전 1 다음
