hotamul의 개발 이야기

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

url: https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 풀이 핵심 1. Trie 자료구조를 활용한다. 2. Trie root에 문자열을 insert 할 때 문자 ('a' ~ 'z') 가 나온 수를 각 문자마다 체크 한다. ex) "hello", "hell" - "hello" insert하고 난 뒤 - "hell" insert하고 난 뒤 3. search 할 때 post_cnt와 비교하면서 버튼 누를 횟 수를 증가 시킨다. (post_cnt와 다음 ..

url: https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이 핵심 (HashTable 구현 참고) 1. S 집합 문자열 hashTable에 저장 2. find 함수로 hashTable 검색 코드 #define MAXN10000 #define MAX_TABLE10007 #define MAXL26 typedef unsigned long long ull; #include ull getHashCode(const cha..

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가 들어가 있습니다. 사용목적 목적 사용하..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.