Trie (Prefix Tree)란?

Trie(트라이), 또는 Prefix Tree(접두사 트리)는 문자열 검색 및 저장에 최적화된 트리 기반 자료구조입니다. 이 자료구조는 각 노드가 하나의 문자를 나타내며, 루트부터 리프 노드까지의 경로가 하나의 문자열을 구성합니다. 따라서 같은 접두사를 공유하는 문자열들은 공통의 경로를 사용하여 저장 공간을 효율적으로 활용할 수 있고, 검색 속도 또한 매우 빠릅니다.Trie의 기본 구조 및 동작 원리Trie는 각 노드가 여러 자식 노드를 가질 수 있는 트리 형태로 구성됩니다. 문자열을 삽입할 때는 루트 노드부터 시작하여 문자열의 각 문자를 따라가며 해당 문자가 없는 경우 새 노드를 생성합니다. 예를 들어, "apple"과 "app"을 저장할 때, "a" → "p" → "p"까지는 공통 경로를 사용하고 이..

• format_list_bulleted 컴퓨터과학/자료구조
• · 2025. 2. 25.
• textsms

해시 테이블(Hash Tables): 효율적인 데이터 검색과 저장

해시 테이블은 데이터의 키와 값을 매핑하여 빠르게 검색하거나 저장할 수 있는 데이터 구조입니다. 해시 테이블의 가장 큰 장점은 검색과 삽입 작업이 평균적으로 O(1)의 시간 복잡도를 가지며, 이는 특히 대규모 데이터 세트에서 그 효율성이 두드러집니다.해시 테이블의 동작 원리해시 함수:주어진 키를 정수 값으로 변환하여 내부 배열의 인덱스로 사용합니다.예를 들어, "name"이라는 키를 해시 함수에 넣으면 인덱스 5가 생성될 수 있습니다. 이 인덱스를 통해 "name"에 해당하는 값을 저장하거나 검색합니다.충돌 처리:서로 다른 키가 동일한 해시 값(즉, 동일한 인덱스)을 가질 수 있습니다.이를 해결하기 위해 대표적으로 사용되는 방법이 연결 리스트를 사용하는 **체이닝(Chaining)**과 빈 공간을 찾아 ..

• format_list_bulleted 컴퓨터과학/자료구조
• · 2025. 1. 21.
• textsms