트라이 검색 결과

해당 글 4건

[BOJ 5670] (Trie) 휴대폰 자판(C++)

휴대폰 자판(Platinum 4) 문제 전체 문제 보기 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 접근법 이 문제는 정렬을 활용해서 풀 수도 있고, 트라이를 활용해서도 풀 수 있다. 트라이 문제들 중에서는 이렇게 정렬 풀 수 있는 경우가 많은 것 같다. 필자는 이번 문제를 트라이로 풀었다. 트라이는 문자열의 접두어를 활용하는 문제 해결에 특화된 자료구조이다. 이번 문제에서도 자동 입력이라고 표현된 기능은 결국 중복된 접두어를 입력해주는 기능이기 때문에 트라이를 풀이했을 때 효율이 좋다고 판단했다. 자료구조 선..
Algorithms/Trie 2021. 8. 7. 16:28

[프로그래머스] (Trie) 전화번호 목록 (C++)

전화번호 목록 (Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 접근법 이 문제는 해시 테이블만 사용하여 풀이한 적이 있다. (해시 테이블만 활용한 기존 풀이 보기) 트라이를 배우고 이 문제를 다시 보니 해시 테이블만 사용했을 때 보다 트라이를 활용했을 때 더 좋은 성능을 낼 수 있을 듯하여 다시 풀었다. 트라이는 여러 문자열들을 입력받아 동일한 접두사를 효율적으로 찾아낼 수 있다는 특징이 있다. 그래서 접두사를 찾아내야 하는 이 문제에 적합한 자료구조가 된다. 트라이..
Algorithms/Trie 2021. 8. 5. 23:47

[BOJ 14725] (Trie) 개미굴 (C++)

개미굴(골드 II) 문제 전체 문제 보기 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 접근법 트라이 자료구조를 이해하기 위해서 풀어본 문제이다. 트라이에 기본적인 설명은 이 글을 참고하자. 일반적으로 트라이라 하면 접두사를 검색하거나 단어를 검색하기 위해서 많이 사용된다. 그런데 이 문제에서는 하나의 노드에 하나의 단어가 들어가는 구조로 변형하여 사용한다는 특징이 있다. 자식 노드 개수에 제한이 없기 때문에 자식 노드의 포인터들을 배열처럼 정적인 공간에 담을 수는 없다. 그리고 여러 자식 노드..
Algorithms/Trie 2021. 8. 4. 23:40

[프로그래머스] (Trie) 자동완성 (C++ / 2018 KAKAO BLIND 3차)

자동완성 (Level 4) 문제 전체 문제 보기 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 트라이 자료구조 카카오는 해설에서 이 문제를 트라이를 사용하는 풀이와 정렬을 활용하여 풀 수 있다고 설명했다. 필자는 트라이를 이용하여 문제를 풀어보았다. 트라이는 접두사를 검색하거나 단어 자체를 검색하는데 특화된 문자열 집합 자료구조이다. 때문에 검색엔진에서도 많이 활용되는 자료구조라고 한다. 아래의 그림은 "abc", "go", "gone", "word", "world"를 저장한 트라이 자료구..
Algorithms/Trie 2021. 8. 3. 11:17