Dev_Diary

https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조를 사용해 풀 수 있는 문제였습니다. 처음에는 현재 노드의 자식이 하나면 카운트를 스킵했지만 어떤 단어의 부분집합이 함께 사전에 포함되어 있는 경우, 예를 들어 hello 와 hell 이 같은 사전에 포함되어 있는 경우, hello 의 버튼 클릭 횟수를 카운팅 할 때 o 를 자동으로 누르게 되어 카운팅이 제대로 되지 않습니다. 그러므로 자식의 수 + (value 가 존재할 때 1 / va..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 해시를 사용하면 조금 더 쉽게 풀 수 있는 문제지만 트라이 자료구조 학습을 위해 트라이로 풀어보았습니다. def solution(N, M, S, data_list): # 트라이 trie = Trie() # 데이터 입력 for string in S: # 트라이 insert 함수 trie.insert(string) # 집합에 포함되는 데이터 수 data_count = ..

https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 트라이, Trie 라는 자료구조를 사용하는 기본 문제입니다. 트리 구조를 사용해 문자열 검색에 최적화된 자료구조 입니다. dev-diary 라는 문자열을 저장한다고 하면 d, e, v, - , d, i, a, r, y 를 순서대로 하위노드로 입력시키며 특정 문자열로 시작하는 문자열을 검색하기 쉽게 만듭니다. 구현은 클래스로 구현할 수 있으며 기본 구현과 문제를 위해 변형한 코드를..