본문 바로가기
반응형
SMALL

trie

5446 - 용량 부족 (Trie, 정적 풀이) https://www.acmicpc.net/problem/5446 더보기
13505 - 두 수 XOR (Trie) https://www.acmicpc.net/problem/13505 13505번: 두 수 XOR N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성하시오. 즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다. www.acmicpc.net Trie를 계속해서 조져봅시다. 두 수 XOR, 이 문제는 Trie 문제인 것을 모르면, Trie까지 생각하기 힘든 문제입니다. 저는 심지어, Trie 문제인 것을 알고 봤는데도 어떻게 응용을 해야하는지 하루 내내 생각을 할 정도였어요 ㅠㅠ... 아직 한 참 모자랍니다. 어찌됐건, 이 문제에 어떻게 Trie를 끼얹을 수 있을까요? 결국 XOR이 최대한 크려면, 비교하려는 두 수의 같은 자릿.. 더보기
5670 - 휴대폰 자판 (Trie, 정적 풀이) https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 문제 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드 www.acmicpc.net 대놓고 트라이 써라는 문제입니다. 원래는 동적으로 필요할 때마다 만들어서 문제를 풀려고 했다가, 어차피 프로 시험에서 정적으로 문제 .. 더보기
14425 - 문자열 집합 (Trie 풀이) https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. www.acmicpc.net Trie를 더 연습해봅시다 !! 문제는 뭐 이해가 안가실건 없다고 생각합니다. 라이브러리를 쓰면 간단하게 풀 수 있는 문제인데.. 저희는 프로를 위한 준비로 구현 능력을 직접!! 기르는 시간을 가져보도록 합시다... 더보기
5052 - 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net 문자열 알고리즘, 자료구조엔 투 톱이 있습니다. (주관적인 생각입니다) 해시(hash)와 트라이(Trie)가 바로 그 것인데요. 해시.. 더보기
반응형
LIST

티스토리툴바