일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- attribute
- 프로그래머스
- 315. Count of Smaller Numbers After Self
- Regular Expression
- Protocol
- Convert Sorted List to Binary Search Tree
- Substring with Concatenation of All Words
- 운영체제
- kaggle
- t1
- iterator
- Generator
- 43. Multiply Strings
- 컴퓨터의 구조
- 715. Range Module
- data science
- shiba
- 파이썬
- Class
- Python
- Decorator
- Python Code
- DWG
- 30. Substring with Concatenation of All Words
- 109. Convert Sorted List to Binary Search Tree
- Python Implementation
- 밴픽
- 시바견
- concurrency
- LeetCode
- Today
- Total
목록전체 글 (382)
Scribbling
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() N, ret = len(nums), [] for i in range(N): if i > 0 and nums[i] == nums[i-1]: continue target = -nums[i] l, r = i + 1, N - 1 while l target: r -= 1 else: l += 1 ..
Greedy하게... class Solution: def maxArea(self, height: List[int]) -> int: max_Area = 0 l = 0 r = len(height) - 1 while l height[l]: l = next_l break if next_l == len(height) - 1: break else: for next_r in range(r-1, -1, -1): if height[next_..
class Solution: def myAtoi(self, s: str) -> int: def delete_whitspace(s): idx = 0 while idx upper_limit: return upper_limit return num if len(s) == 0: return 0 s = delete_whitspace(s) if not s: return 0 first_char = s[0] if firs..
class Solution: def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s board = [[] for _ in range(numRows)] denom = 2 * numRows - 2 for i, char in enumerate(s): remainder = i % denom if remainder < numRows: board[remainder].append(char) else: board[2 * numRows - remainder - 2].append(char) ret = '' for i in range(len(board)): for j in board[i]: ret += j return ret
1. 기본 자료구조 1.1 리스트: 가장 기초적인 자료 구조 - 특징: 추가 / 탐색 / 제거 등 대부분 O(N) list.count(obj): 요수 개수 list.index(obj): 요소 위치 idx list.insert(idx, obj) list.pop(idx): 마지막 요소 제거 및 반환 / 특정 요소 제거 및 반환 list.remove(obj) list.reverse(): list.sort(reverse=True): 기본 오름차순으로 정렬 1.2. Set: 중복을 허용하지 않음 - 특징: (파이썬) Set 자료구조는 Hash Table 구조로 O(1)로 탐색 가능 선언: set = set([1, 2, 3]) set.add(obj) set.update(list): set.remove(obj): o..
위상정렬을 이용한다. class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: indegrees = [0] * numCourses graph = [[] for _ in range(numCourses)] for v, u in prerequisites: graph[u].append(v) indegrees[v] += 1 q = [] for node, indegree in enumerate(indegrees): if indegree == 0: q.append(node) while q: u = q.pop() for v in graph[u]: indegrees[v] -= 1 if indegrees[v] =..
위상 정렬: 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록' 순서대로 나열하는 알고리즘 def topology_sort(): result = [] q = deque() """ 진입 차수가 0인 node를 queue에 삽입 """ for i in range(1, v+1): if indegree_list[i] == 0: q.append(i) while q: now = q.popleft() result.append(now) """ queue에서 꺼낸 node와 연결된 모든 node 간의 간선을 제거 후 진입 차수가 0인 node를 queue에 삽입 """ for nxt in graph[now]: indegree_list[nxt] -= 1 if indegree_list[nxt] == 0: q.append..
class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: def calc_Dist(p1, p2): d1 = abs(p1[0] - p2[0]) d2 = abs(p1[1] - p2[1]) return d1 + d2 def find_parent(parent, a): if parent[a] == a: return a parent[a] = find_parent(parent, parent[a]) return parent[a] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: ..
1. 신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다. 2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리 3. Kruskal Algorithm: 최소 신장 트리를 찾는 알고리즘 - O(vlogv) - Greedy하게 최소 비용 edge부터 차례로 연결한다. - 연결하고자 하는 node가 서로소였다면, union을 진행 - 연결하고자 하는 node가 cycle을만든다면, pass def find_parent(parent, x): if parent[x] == x: return x parent[x] = find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_p..
Dynamic Programming을 이용한 방법: X + + X 는 Palindrome Substring이다는 특성을 이용한다. 위를 bottom-up으로 구현하려면, 문자열의 길이가 커지는 순(1, 2, 3, ....) 으로 DP를 연산하면 된다. class Solution: def longestPalindrome(self, s: str) -> str: ret = "" is_Palindrome = [[False] * len(s) for _ in range(len(s))] for i in range(len(s)): is_Palindrome[i][i] = True ret = s[i:i+1] for i in range(len(s)-1): if s[i] == s[i+1]: is_Palindrome[i][i+..