CS STUDY

이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 '자료구조' 라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 '알고리즘' 자체를 지칭한다. https://leetcode.com/problems/binary-search/submissions/ Binary Search - 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.c..

https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/ Kth Largest Element 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 1. heapq 모듈 이용 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap=list() for n in nums: heapq.hea..

힙은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 이진 트리인 특수한 트리 기반의 자료구조다. 파이썬에서는 최소 힙만 구현되어 있고 heapq모듈로 사용할 수 있다. 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다. 우선순위 큐는 주로 힙으로 구현하고, 힙은 주로 배열로 구현한다. 따라서 우선순위 큐는 결국은 배열로 구현하는 셈이 된다. 힙은 정렬된 구조가 아니다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다. 계산을 편하게 하기 위해 인덱스는 1부터 사용한다. 힙 연산 먼저 이진 힙을 구현하기 위한..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/ Construct Binary Tree from Preorder and Inorder Traversal - 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 순회에는 크게 전위, 중위, 후위 순회가 있으며 이 셋 중 2가지만 있어도 이진 트리를 복원할 수 있다. 위 그림에서 전위의 첫 번..

https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이 문제는 x,y 좌표를 받고 1순위로 y좌표, 2순위로 x좌표를 이용해 정렬하는 문제이다. 파이썬을 이용한다면 sort함수 인자인 key=lambda를 이용해 쉽게 해결할 수 있다. N=int(input()) arr=[] for i in range(N): a,b=map(int,input().split()) arr.append([a,b]) ..

트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다. 그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 이진트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다. 1. 전위 순회(preorder) - NLR 2. 중위 순회(inorder) - LNR 3. 후위 순회(post-order) - LRN L = 현재 노드의 왼쪽 서브트리 R = 현재 노드의 오른쪽 서브트리 N = 현재 노드 자신 class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=left self.right=right root=Node('F'..

https://leetcode.com/problems/minimum-distance-between-bst-nodes/submissions/ Minimum Distance Between BST Nodes - 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 1. 재귀 구조로 중위 순회 BST의 왼쪽 자식은 항상 루트보다 작고, 오른쪽 자식은 항상 루트보다 크다. 그렇다면 루트 D와 가장 차이가 작을 수 있는 노드는 딱 2개 노드만 가능한데 바로 I와 G이다. 파란 글..

https://leetcode.com/problems/range-sum-of-bst/ Range Sum of BST - 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 1. 재귀 구조 DFS로 브루트 포스 탐색 DFS로 전체를 탐색한 다음, 노드의 값이 low와 high 사이일 때만 값을 부여하고, 아닐 경우에는 0을 취해 계속 더해 나가면 쉽게 구할 수 있다. # Definition for a binary tree node. # class TreeNode: # ..

정확히 중앙값을 갖도록 내림값을 리턴하는 // 연산자를 사용했다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return None mid=len(nums)//2 node=TreeNode(nums[mid]) node.left=self.sortedArrayToBST(nums[:mid]) nod..

이진 탐색 트리(Binary Search Tree, BST)란 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다. 이 트리의 가장 훌룡한 점은 탐색 시 시간 복잡도가 O(log n)라는 점이다. BST는 랜덤하게 생성해도 대부분의 경우 균형이 잘 맞는 아름다운 형태로 트리를 표현할 수 있지만, 운이 나쁘면 트리의 모양이 균형을 제대로 이루지 못할 수 있다. 균형이 많이 깨지면 탐색 시에 O(log n)이 아니라 O(n)에 근접한 시간이 소요될 수 있다. 이런 트리는 균형을 맞춰 줄 필요가 있는데 그래서 고안해낸 것이 바로 '자가 균형 이진..