Scribbling

빈도를 기억하기 위한 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)은 일정한 규칙(패턴)을 가진 문자열을 표현하는 방법입니다. 복잡한 문자열 속에서 특정한 규칙으로 된 문자열..

Decorator는 이미 만든 함수를 수정하지 않고, 함수 주변을 감싸는 방식으로 함수에 추가 기능을 구현한다. def trace(func): # wrapper는 아래처럼 가변 인수로 만들 수 있다. # 가변 인수가 아닌 경우, 원래 함수의 parameter 형태와 일치해야 한다. def wrapper(*args, **kwargs): ret = func(*args, **kwargs) print('{0}(args={1}, kwargs={2}) -> {3}'.format(func.__name__, args, kwargs, ret)) # 원래 함수가 return이 필요한 경우에는 wrapper도 return이 필요하다. return ret return wrapper @trace def get_max(*args..