본문 바로가기

TRIE

PS/Leetcode 2022. 6. 19. [Leetcode Medium] 1268. Search Suggestions System Search Suggestions System - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com You are given an array of strings products and a string searchWord. Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products sh..
PS/Leetcode 2022. 6. 18. [Leetcode Hard] 745. Prefix and Suffix Search Design a special dictionary with some words that searchs the words in it by a prefix and a suffix. Implement the WordFilter class: WordFilter(string[] words) Initializes the object with the words in the dictionary. f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the l..
아호 - 코라식 (Aho-Corasick) 알고리즘
알고리즘 공부 2022. 1. 31. 아호 - 코라식 (Aho-Corasick) 알고리즘 아호-코라식 알고리즘은 대표적인 문자열 알고리즘 중 하나로써, 매우 빠른 일대 다 패턴 매칭 알고리즘입니다. 이와 관련해 설명하기 전에, 아호 코라식이 어떻게 쓰이는지, 왜 필요한지 간단한 예제를 통해 한번 알아보겠습니다. 주어진 단어가 다음과 같을 때, 트리는 아래처럼 구현됩니다. Words = {"HE","SHE","HIS"} 우리는 KSHE라는 문자열에서, 다음의 트라이에 포함되는 문자가 무엇이 있는지를 알고 싶습니다. 먼저, 기존의 방식처럼, 그냥 트라이를 따라 이동하는 경우를 생각해봅시다. 자식을 따라 이동하다가, 더이상 이동이 불가능한 경우, 시작 위치로 이동한다고 해봅시다. 현재 노드 Root 1 ) K로는 시작 노드에서 이동할 수 없으니 패스합니다. 현재노드 : Root 2 ) 시작노드에서..
PS/BOJ (Baekjoon Online Judge) 2022. 1. 31. [BOJ_Platinum 5] 9202 - Boggle [python] 9202번: Boggle (acmicpc.net) 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 입력 첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다. 그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에..
PS/Leetcode 2022. 1. 28. [leetcode medium] 211. Design Add and Search Words Data Structure (2) Design Add and Search Words Data Structure - LeetCode Design Add and Search Words Data Structure - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Constraints: 1
PS/BOJ (Baekjoon Online Judge) 2022. 1. 28. [BOJ_Gold 2] 14725 - 개미굴 [python] 14725번: 개미굴 (acmicpc.net) 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 입력 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15) 다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다..
[BOJ_Gold 4] 5052 - 전화번호 목록 [python]
PS/BOJ (Baekjoon Online Judge) 2022. 1. 27. [BOJ_Gold 4] 5052 - 전화번호 목록 [python] 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기..
[leetcode medium] 421. 배열 내 두 요소의 최대 XOR값 구하기
PS/Leetcode 2022. 1. 27. [leetcode medium] 421. 배열 내 두 요소의 최대 XOR값 구하기 (1) Maximum XOR of Two Numbers in an Array - LeetCode Maximum XOR of Two Numbers in an Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Constraints: 1 i) & 1 if 1-bit in cur.child: #현재 자기 bit값과 반대되는 방향으로 최대한 이동 cur = cur.child[1- bit] ans += (1
728x90

티스토리툴바