Computer Science/[22-상] Data Structure & Algorithm4 [Algorithm] Sliding Window + 1695. Maximum Erasure Value array에서 특정 구간의 최대 합을 찾을 때, 인덱스 0부터 모든 subarray의 합을 구해볼 수 있을 것이다. 이 때 시간복잡도는 O(n^2)으로, Sliding Window기법을 통해 시간복잡도를 O(n)으로 낮출 수 있다. 리트코드 1695. Maximum Erasure Value = unique한 값만 존재하는 subarray의 합 중 가장 큰 합 찾기 [4, 2, 1, 2, 6] 1. 인덱스 0부터 윈도우 크기를 키우다가, 중복되는 값이 나오면 (=2) 앞에서부터 윈도우 크기를 줄임 [4] = 4 [4, 2] = 6 [4, 2, 1] = 7 [2, 1, 2] [1, 2] 2. 윈도우에 unique한 값만 존재하면, 합이 얼마인지 찾기 [1, 2] = 3 [1, 2, 6] = 9 class S.. 2022. 6. 12. [Algorithm] Binary Tree + 530. Minimum Absolute Difference in BST 리트코드 530. Minimum Absolute Difference in BST Binary Search Tree에 있는 전체 노드의 차이 중 가장 적은 숫자를 리턴한다. (서로 부모-자식 관계인 노드가 아니여도 됨) 115ms가 걸린 내 코드랑 디스커션에 있는 55ms 걸린 코드를 비교해보려고 한다. 나는 단순하게 전체 노드를 저장해서 가장 작은 차이를 골랐는데, BST의 성질을 이용하지 못했다. 디스커션의 코드는 왼쪽 자식 노드가 항상 부모 노드보다 작고, 오른쪽 자식 노드가 항상 부모 노드보다 크다는 것을 이용했다. 55ms class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: d.. 2022. 6. 1. [Algorithm] Bucket Sort + 347. Top K Frequent Elements Bucket Sort INPUT: 길이가 n인 리스트 (array), 키값이 균등하게 분포한다고 가정 1. 구간을 n등분한 버킷을 만든다. 2. array[i]를 인덱스가 n * array[i]인 버킷의 위치에 추가한다. 3. 각각의 버킷에 여러개의 요소가 있으면 insertion sort로 정렬한다. 리트코드 347. Top K Frequent Elements - Bucket Sort를 이용한 풀이 - n이 인풋 리스트의 길이일 때, 빈도는 1에서 n까지 분포. (가장 작은 빈도수 = 1, 가장 큰 빈도수 = n) - 빈도수는 collections.Counter()로 센다. Counter()은 소를 key로, 빈도수를 value로 가진 딕셔너리를 리턴. INPUT: 숫자를 요소로 가진 리스트 1. 길이.. 2022. 4. 14. [Algorithm] Top 75 LeetCode https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode questions that teach you core concepts and techniques for each category/type of proble.. 2022. 2. 21. 이전 1 다음
