본문 바로가기
반응형

전체 글571

[리드코드 leetcode] 56. Merge Intervals leetcode.com/problems/merge-intervals/ Merge Intervals - 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 풀긴 하였으나 최선은 아닌 것 같다.. class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key = lambda x: x[0]) result = [] temp = intervals[0] for i .. 2021. 4. 14.
[알고리즘 algorithm] 정렬 sort 종류와 예제 코드(버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 안정 정렬, 불안정 정렬, 계수 정렬) 1. 가장 비효율적인 정렬, 버블 정렬(Bubble Sort) 시간복잡도: O(n2) def bubble(a): n = len(a) for _ in range(n-1): for i in range(n-1): if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i] 2. 제자리 정렬, 선택 정렬(Selection Sort) 시간복잡도 : O(n2) def selection(a): n = len(a) for i in range(n-1): min_idx = i for j in range(i+1, n): if a[min_idx] > a[j]: min_idx = j a[i], a[min_idx] = a[min_idx], a[i] 3. 제자리 정렬, 삽입 정렬(Insert Sort) 시간복.. 2021. 4. 14.
[자료구조] 힙 Heap 정의와 연산 힙 : 힙의 특성을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조 힙의 예시로 최소 힙이 있다. 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 된다. 주의할 점은 힙은 정렬된 구조가 아니다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐 좌우에 대한 관계는 정의하지 않는다. - 삽입 삽입에는 업힙(up heap)연산이 필요하고 과정은 다음과 같다. 삽입의 시간복잡도는 O(logN)이다. 1. 요소를 가장 하위레벨의 최대한 왼쪽으로 삽입 2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경 3. 계속해서 부모 값과 비교해 위치를 변경(가장 작은 값일 경우 루트까지 올라감) - 추출 루트를 추출하면 되는 간단한 작업이지만 추출 이후 힙의 특성을 유지하는 작업이 .. 2021. 4. 14.
[리트코드 leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 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 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None,.. 2021. 4. 13.
[리트코드 leetcode] 783. Minimum Distance Between BST Nodes 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 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # s.. 2021. 4. 12.
[리트코드 leetcode] 938. Range Sum of BST 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 풀긴 하였지만 brute force이므로 개선의 여지가 존재한다. 가지치기 방법을 생각해봐야겠다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = .. 2021. 4. 12.
반응형

티스토리툴바