환영합니다. 이 블로그 번째 방문자입니다.
[CS 스터디: JAVA] (6) 트라이
트라이(Trie) : 문자열 집합을 저장하고 탐색하기 위한 트리 형태의 자료 구조 : 자동완성 기능, 사전 검색등에 특화되어 있는 구조(단어의 앞글자부터 찾는) -- 예를 들어, "bear" 을 찾을 때 'b' 를 찾고 'e','a','r'를 순서대로 찾는다. >> bell, bear, bore, bat, ball, stop, stock, stack을 저장한 트라이 트리 구조 → Trie 구조의 특징 (1) 항상 루트 노드는 null 노드 (여러개 집합의 문자열을 저장해야 하므로) (2) 각각의 자식 노드들은 알파벳 순서대로 정렬 (3) 각각의 노드는 최대 26개의 자식을 가질 수 있음(A부터 Z까지) (4) 루트 노드를 제외한 각각의 노드는 1개의 알파벳 노드를 저장할 수 있음 (5) 삽입하는 가장 긴..
[Q3:English] Kth largest element
Given an array of integers arr and an integer k find the kth largest element. (1 ≤ k ≤ length of arr) For example, arr = [4,2,9,7,5,6,7,1,3], k = 4, output : 6. [ Method 1] # Logic Remove max element in the arr for k-1 times and return max element. # Code # Complexity T(n,k) : (k-1) * 2n + n = O(kn) S(n) : O(1) [Method 2] # Logic Use sorting # Code # Complexity T(n,k) : O(nlogn) + O(1) = O(nlogn..
[Q2:English] First and last index in sorted array
👇🏻 문제(이 정도는 해석X...귀찮,, 영어강의라 포스트도 영어로) Given a sorted array of integers arr and an integer target, find the index of the first and last position of target in arr. In targer can't be found in arr, return [-1,-1]. For example, arr = [2,4,5,5,5,5,5,7,9,9], target = 5 👉🏻 output : [2, 6] [Method 1] # Logic # Code # Complexity S(n) = O(1) T(n) = O(n) [Method 2] How about using binary search? Because i..
