본문 바로가기

트라이

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..
[BOJ_Platinum 2] 10256-돌연변이 [python]
PS/BOJ (Baekjoon Online Judge) 2022. 2. 3. [BOJ_Platinum 2] 10256-돌연변이 [python] 10256번: 돌연변이 (acmicpc.net) 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net 문제 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다. 하지만 때때로 DNA 구조를 그대로 확인하는 것..
아호 - 코라식 (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줄에..
[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

티스토리툴바