hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 핵심 1. 문자열 처리 문제로 접두어를 이용해 자료구조를 만들어야 하므로 Trie 자료구조 사용 2. Trie에 번호들을 저장, 탐색하고 문자열이 끝나기 전 isTerminal이 true일 경우 접두어가 존재하는 것이므로 false를 반환한다. 코드 #include #include #define MAX_N10000 #define MAX_L11 int charT..

트라이(Trie)란? 트라이(Trie)의 형태 대해서 Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있습니다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다. DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있습니다. 트라이(Trie)의 예시 직접 그린 Trie이며 주황색으로 된 노드들이 입력된 문자열들입니다. 현재 be, bee, can, cat, cd가 들어가 있습니다. 사용목적 목적 사용하..