4Legs_Archives

문제 링크 : www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 유형 자료 구조, 트라이 트라이 자료구조로 해결이 가능한 문제이다. 트라이의 find 함수에서, 다음과 같은 경우에 반환값을 1 증가시켜 정답을 구하면 된다. 다른 문자열의 끝을 지나는 경우 (코드의 finish) 자식의 수가 2 이상인 트라이 객체를 지날 경우 root 트라이 객체일 경우 (최초 1번의 입력) [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

단어 찾기 사전에서 "Algorithm" 이란 단어를 찾는 상황을 가정해보자. 사전에서 단어를 찾는 방법은 여러 가지가 있을 것이다. ① 단순 탐색 : 사전의 처음부터 Algorithm이 나올 때까지 모든 단어를 확인 가장 확실하고 구현하기 쉬운 방법이지만, 찾고자 하는 단어가 사전의 어느 위치에 있냐에 따라 걸리는 시간이 천차만별일 것이다. 따라서 모든 경우에 대해 그다지 좋은 효율을 갖고 있다곤 할 수 없을 것이다. ② 이분 탐색 : 사전의 절반 지점의 단어를 확인 사전의 처음부터 끝까지 모든 단어들 중 딱 절반 지점의 단어를 확인한다. 이 절반 지점을 mid라 하자. 이 때 확인된 단어가 찾고자 하는 단어보다 사전 순으로 앞서면, 다음 탐색 범위는 mid부터 사전의 끝이 될 것이다. 또한 앞서지 않..