Patrick's Devlog

1. 트라이탐색 트리의 일종이며, 동적 집합이나 연관 배열을 저장하는데 사용되는 트리 자료구조이다. 문자열을 저장하고 효율적으로 탐색하기 위한 자료구조로 생각하면 된다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산됨을 의미한다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 메모리에 최적화된 경우에는 기수 트리가 된다.   2. 장단점문자열 검색 시 빠른 검색 가능문자열 탐색 시 하나씩 전부 비교하는 것 보다 시간 복잡도 측면에서 효율적각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있으므로 공간적인 측면(메모리)에서는 비효율적3..

1. 개요 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 1-1. 설명 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개 문자열 중 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫째 줄에 문자열 개수 N과 M이 주어지며, 각각 1 이상 10,000이하 자연수 - 다음 줄 N개에는 집합 S에 포함되어 있는 문자열 - 다음 M개 줄에는 검사..