반응형 [C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie) 트라이 (Trie)트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.트라이의 특징:노드 구조: 각 노드는 문자와 자식 노드를 가집니다.루트 노드: 루트 노드는 빈 문자열을 나타냅니다.경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.트라이 구현TrieNode.h#ifndef TRIENODE_H#define TRIENODE_H#include // 트라이의 노드 구조체struct TrieNode { std::unordered_map children; // 자식 노드를 .. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 1: 트라이(Trie) 자료구조와 문자열 검색 트라이(Trie) 자료구조 소개트라이(Trie)는 문자열 또는 단어의 집합을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조입니다. 주로 문자열 검색, 자동 완성, 사전 구현 등에 사용됩니다. 트라이는 각 노드가 문자 하나를 나타내며, 루트 노드에서 시작하여 각 문자를 따라가면서 단어를 구성합니다.트라이의 주요 특징빠른 검색: 문자열의 길이에 비례하는 시간 복잡도 (O(L))에서 검색이 가능합니다. 여기서 (L)은 문자열의 길이입니다.공유 구조: 공통 접두사를 가지는 문자열을 공유하여 공간을 절약합니다.삽입과 검색의 단순함: 삽입과 검색 연산이 단순하고 직관적입니다.트라이의 기본 연산삽입 (Insert): 문자열을 트라이에 삽입합니다.검색 (Search): 문자열이 트라이에 존재하는지 확인합니다... 2024. 8. 1. 이전 1 다음 반응형
