일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- data science
- 315. Count of Smaller Numbers After Self
- Decorator
- 43. Multiply Strings
- attribute
- DWG
- 운영체제
- Python
- Substring with Concatenation of All Words
- LeetCode
- Protocol
- 프로그래머스
- 30. Substring with Concatenation of All Words
- Python Implementation
- 파이썬
- 715. Range Module
- 컴퓨터의 구조
- Generator
- Class
- shiba
- Regular Expression
- Python Code
- 밴픽
- iterator
- concurrency
- 시바견
- t1
- Convert Sorted List to Binary Search Tree
- kaggle
- 109. Convert Sorted List to Binary Search Tree
- Today
- Total
목록Computer Science (392)
Scribbling
면접 형식의 문제여서 문제를 맞추는 것은 어렵지 않다. 다만 어느정도로 효율적인 알고리즘(시간 및 메모리 측면)을 구현하는지가 관건이다. 가장 간단한 방법은 모든 숫자를 저장하고, 중앙값 search시마다 정렬하는 방법이다. add: O(1) find: O(nlogn) 위의 이유로 비효율적이다. class MedianFinder: def __init__(self): self.arr = [] self.count = 0 def addNum(self, num: int) -> None: self.arr.append(num) self.count += 1 def findMedian(self) -> float: self.arr.sort() if self.count % 2 == 0: return (self.arr[se..
빈도를 기억하기 위한 hashmap을 사용하자. from collections import defaultdict class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: dic = defaultdict(int) for num in nums: dic[num] += 1 temp = [] for key, val in dic.items(): temp.append([val, key]) temp.sort(key=lambda x: -x[0]) temp = temp[:k] return [t[1] for t in temp]
매우 어려운 문제였다. 다만 아래 문제를 먼저 풀면, 이 문제도 쉽게 풀 수 있다. https://focalpoint.tistory.com/179 LeetCode: 300. Longest Increasing Subsequence - 시바견의 끄적임 1. 가장 간단한 DP 형태 O(N**2)이다. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = 1 for i in range(1, len(nums)): temp = -1 j = i - 1 while j >= 0: if n.. focalpoint.tistory.com from bisect import bisect_left class Solutio..
1. 가장 간단한 DP 형태 O(N**2)이다. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = 1 for i in range(1, len(nums)): temp = -1 j = i - 1 while j >= 0: if nums[j] < nums[i]: temp = max(temp, dp[j]) j -= 1 if temp != -1: dp[i] = temp + 1 else: dp[i] = 1 return max(dp) O(N**2)답게 빠르지 않다. 개선을 해보자. 2. LIS 알고리즘 (1)의 알고리즘은 하나의 숫자에 대해 계산함에 있어 이전에 나온 모든 숫자를 다 조사한다. 그러다보니 ..
1. Bottom-up Solution + predefining palindromic matrix class Solution: def minCut(self, s: str) -> int: dp = self.build_palindrome(s) n = len(s) self.cut = [2002] * n for end in range(n): if dp[0][end]: self.cut[end] = 0 continue for start in range(1, end+1): if dp[start][end]: self.cut[end] = min(self.cut[end], self.cut[start-1] + 1) return self.cut[-1] def build_palindrome(self, word): n = len..
class Solution: def partition(self, s: str) -> List[List[str]]: self.ret = [] self.dfs(s, []) return self.ret def dfs(self, s, path): if not s: self.ret.append(path) return for i in range(1, len(s)+1): first, second = s[:i], s[i:] if self.is_Palindromic(first): self.dfs(second, path+[first]) def is_Palindromic(self, s): return s == s[::-1]
LRU(Least Recently Used) 알고리즘은 캐시나 메인 메모리에서 '메모리 관리 알고리즘'으로 많이 사용된다. LRU 알고리즘에 대한 자세한 설명은 아래 링크를 참고하라. https://focalpoint.tistory.com/137 쉽게 배우는 운영체제 내용 정리 - Chapter 09 가상 메모리 관리 1. 요구 페이징 1.1 요구 페이징 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것이 가져오기 정책이다. 일반적으로 프로세스가 요청할 때 메모리로 가져오는데, 일르 요구 focalpoint.tistory.com 간단히 말하자면, 메모리가 가득차면 가장 사용한지 오래 지난 부분을 버리는 것이다. 여기서 '사용'은 해당 부분에 접근하거나, 수정한 경우를 의미한다. 파이썬은..
고립된 O를 X로 만드는 문제이다. "고립된"은 board의 경계와 이어지지 않는 O들이다. 고로 경계의 O와 이어진 O들을 제외하고, 모두 X 처리해준다. from collections import deque class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] island = set() m, n = len(board), len(board[0]) for i in range(m): for j in range(n): if board[i][j] == "O": islan..
DFS로 푼다. # 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 sumNumbers(self, root: Optional[TreeNode]) -> int: self.sum = 0 self.dfs(root, '0') return self.sum def dfs(self, node, num: str): if node.left == None and node.right == None: self.sum += int(num + str(nod..

정규 표현식 혹은 정규식은 문자열 매칭에 매우 유용하다. 정규 표현식에 대해 자세히 알고 싶다면 아래 링크를 참고하라. https://wikidocs.net/1642 07-1 정규 표현식 살펴보기 정규 표현식(Regular Expressions)은 복잡한 문자열을 처리할 때 사용하는 기법으로, 파이썬만의 고유 문법이 아니라 문자열을 처리하는 모든 곳에서 사용한다. 정 ... wikidocs.net https://dojang.io/mod/page/view.php?id=2435 파이썬 코딩 도장: 43.1 문자열 판단하기 Unit 43. 정규표현식 사용하기 정규표현식(regular expression)은 일정한 규칙(패턴)을 가진 문자열을 표현하는 방법입니다. 복잡한 문자열 속에서 특정한 규칙으로 된 문자열..