본문 바로가기

트리

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..
독학사/자료구조 2022. 5. 13. [자료구조] 힙 | Heap 공유된 코드 - Color Scripter colorscripter.com 힙, 힙트리는 부모 노드가 자식 노드보다 우선순위가 높은 값을 가지고있음이 보장되는 힙구조로 이루어진 트리형태의 자료구조입니다. 이 정의를 가지고 귀납적으로 생각해보면, 루트노드에 담겨있는 값이 항상 우선순위가 가장 높은 값임을 알 수 있습니다. 또, 균형 이진트리 형태를 항상 유지하므로, 값의 삭제 및 삽입을 항상 O(logN)시간복잡도 내에 할 수 있음이 보장됩니다. 이러한 힙트리의 특성을 활용해, 다익스트라(Dijkstra), 힙 정렬(Heap Sort)등을 수행할 수 있습니다. 위 링크는 힙트리를 개인적으로 구현한 소스코드입니다.
[자료구조] 세그먼트 트리 | Segment Tree
독학사/자료구조 2022. 4. 24. [자료구조] 세그먼트 트리 | Segment Tree 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 어떤 구간에 대한 정보(특정 구간에서의 최대/최솟값, 평균, 합 등)를 각각의 노드가 저장하고 있다는 특성을 이용해, O(logN)의 시간복잡도로 구할 수 있게 해주는 자료 구조입니다. 구현의 편의를 위해, 완전 이진트리 형태로 구현하였습니다. 먼저, 전체적인 구조는 아래와 같습니다. 주어진 노드(BaseNodes)의 개수 $N$에 대해 $N < X$를 만족하는 가장 가까운$2^N$값 X에 대해, 세그먼트 트리의 루트노드는 구간 [0,X]까지의 BaseNodes의 세그먼트 값(합)을 의미합니다. 또한, 이 BaseNode의 자식들은 각각 구간[0,X//2),[X//2,X)의 합을 저장하고 있습니다. 이러한 세그먼트 트리의 특성을 잘 이용하면, 우..
PS/BOJ (Baekjoon Online Judge) 2022. 4. 15. [BOJ_Silver2] - 11725 트리의 부모 찾기[python] 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 간단한 트리 탐색 문제입니다. 주어진 트리에 대해, 루트 노드인 1번 노드부터 그래프 탐색을 진행하며, 현재 노드와 연결된 자식 노드의 부모를 현재 노드로 저장해주..
PS/BOJ (Baekjoon Online Judge) 2022. 3. 20. [BOJ_Platinum 2] 12995 - 트리나라 [python] 12995번: 트리나라 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연 www.acmicpc.net 문제 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연결되어 있기 때문에, 임의의 두 도시 사이를 항상 오갈 수 있다. 스타트링크의 직원 K명은 트리나라로 이사를 가려고 한다. 모든 직원은 서로 다른 도시로 이사를 가야한다. 즉, 이사할 도시 K개를 선택해야 한다. 이사할 도시에는 중요한 조건이 하나 있는데, 모든 ..
PS/BOJ (Baekjoon Online Judge) 2022. 2. 27. [BOJ_Platinum 4] 24520 - Meet in the middle [python] 24520번: Meet In The Middle 첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$ 이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 www.acmicpc.net 문제 신촌 왕국에는 $1$번부터 $N$번까지 $N$개의 마을이 있고 $N-1$개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다. 현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 ..
[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줄에..
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) 이다..
728x90

티스토리툴바