일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 운영체제
- Python
- Class
- data science
- Convert Sorted List to Binary Search Tree
- concurrency
- DWG
- 43. Multiply Strings
- Decorator
- Python Code
- attribute
- t1
- Protocol
- Generator
- 밴픽
- Substring with Concatenation of All Words
- 715. Range Module
- 109. Convert Sorted List to Binary Search Tree
- shiba
- 315. Count of Smaller Numbers After Self
- LeetCode
- iterator
- Python Implementation
- kaggle
- 프로그래머스
- 시바견
- 30. Substring with Concatenation of All Words
- 파이썬
- Regular Expression
- 컴퓨터의 구조
- Today
- Total
목록Computer Science/Algorithms & Data Structures (26)
Scribbling
Python does not provide standard library for ordered set or ordered dictionary. However, there's an Apache2 licensed sorted collections library "SortedContainer". You can install the library with the following cmd. pip install sortedcontainers https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/#:~:text=Sorted%20set%20is%20a%20sorted,must%20be%20hashable%20and%20comparable. Py..
I found this problem is pretty similar to 'Russian Doll' prob (https://leetcode.com/problems/russian-doll-envelopes/). Thought process for this problem is: 0> Sort the properties. 1> Let's just assume that attack strictly increases (e.g. 3, 4, 5, ...): then what we should do is to count how many defense values have larger values on their right side. And that's exactly what monotonicly desc stack..
Question: There is a stream of two different operations. One is placing a point on a single axis. The other is to check if there's a point in a given range. (see the image below) 1> Brute Force 1-1> For every range check, we can just go over all the points it includes. Time complexity for that would be O(R * N), where R is range and N is the number of range checks. 1-2> Or, we can just go over a..
Monotonic stack or monotonicly increasing/decreasing stack is a stack which keeps its elements in increasing/decreasing order. Monotonic stacks are useful when, - Finding the very previous less element of each element in a vector in O(N) time complexity - Finding the very next less element of each element in a vector in O(N) time complexity (1) Code Example To get the very previous less (or equa..
크게 두 단계로 풀 수 있다. 1) 알파벳 조합이 동일한 집합끼리 나눈다. 2) 각 집합 내에서 단어를 연결하고, 소 집합의 갯수를 구한다. This prob can be solved within two steps. 1) Group words by alphabet combinations 2) Connect words in each group and then get the number of small groups Code is quite straightforward, so I guess there's no need to explain more. Time complexity would be (O(N**2*k)), where N is the number of words and k is length of a w..
This post is about Knuth Shuffle, a shuffle algorithm. - This algorithm allows random shuffle, giving all permuations of array equal likelihood. - No need for additional arrays, so memory complexity is O(1). - Time complexity is O(N) Code is pretty simple as below. To give all permuations of a particular array equal likelihood, all the number should have the same probability to be placed in a ce..
Below is my own python implementation of AVL Tree. Feel free to use it and refer to the bottom most part of the code to see how it works. As there are already so many materials dealing with the algorithms of AVL data structure, I won't explain about them at this article. Instead, I upload a concise implementation of AVL tree. class TreeNode: def __init__(self, val): self.val = val self.left = No..
Below is the python implementation of segment tree data structure. Segment tree is often used to query range sum within O(logN) time complexity. As it is storing range information of the data, this data structure can be useful when you are looking for information on the basis of various ranges. * Below implementation is for range sums. class SegmentTreeNode: def __init__(self, start, end, val, l..
Heapq만을 사용한 Priority Queue의 Time Complexity는 아래와 같다. Find max/min - O(1) Insert - O(logN) Remove - O(N) Remove Operation에 Linear Time이 필요하다는 것이 아쉽다. 이를 해결하기 위한 Custom Priority Queue를 만들었다. 이는 두 개의 Priority Queue를 사용하는 방식이다. 하나의 Queue는 원래 목적인 max/min heap로 사용하고, 나머지 하나의 queue를 쓰레기통으로 사용한다. Time Complexity는 아래와 같다. Find max/min - O(1) Insert - O(logN) Remove - O(logN) 다른 연산은 그다지 어렵지 않으니 Remove 연산만..
파이썬 코드로 작성한 KMP 알고리즘이다. 이해하기 어렵다면 아래 사이트를 참고하자. https://bowbowbow.tistory.com/6 def getPi(pattern): m, j = len(pattern), 0 pi = [0] * m for i in range(1, m): while j > 0 and pattern[i] != pattern[j]: j = pi[j-1] if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi def kmp(string, pattern): ret = [] pi = getPi(pattern) n, m, j = len(string), len(pattern), 0 for i in range(n): while j > 0 and s..