Scribbling

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..

2019 카카오 코딩 테스트 기출 문제라고 한다. 단순 구현문제다. from collections import defaultdict def solution(record): results = [] record_dict = defaultdict(list) nickname_dict = {} for rec in record: rec = rec.split(' ') if rec[0] == 'Enter': user_id, nickname = rec[1], rec[2] results.append(nickname + "님이 들어왔습니다.") record_dict[user_id].append(len(results) - 1) if user_id not in nickname_dict: nickname_dict[user_id]..

O(N) 알고리즘. class Solution: def longestConsecutive(self, nums: List[int]) -> int: longest = 0 nums = set(nums) for num in nums: if num - 1 not in nums: cnt = 1 while num + 1 in nums: num += 1 cnt += 1 longest = max(longest, cnt) return longest class Solution: def longestConsecutive(self, nums: List[int]) -> int: numSet = set(nums) longest = 0 while nums: cnt = 1 l = r = nums.pop() numSet.discard(..

난이도가 꽤 높은 그래프 문제이다. 방이 만들어지는 조건을 따져야 한다. * 방이 만들어지는 조건 - 재방문한 점이다. - 타고온 edge는 첫 방문이다. 여기까지는 생각하기 쉬운데, 문제는 아래와 같은 케이스다. 현재 알고리즘은 위의 그림에 대해 방을 1개로 파악한다. 이는 가운데 교차점을 정점으로 생각하지 않기 때문이다. 이 문제를 해결할 방법은 여러가지인데, 가장 간단한 방법은 하나의 화살표에 대해 이동을 2번 반복하는 것이다. def solution(arrows): answer = 0 dx = (0, 1, 1, 1, 0, -1, -1, -1) dy = (-1, -1, 0, 1, 1, 1, 0, -1) vertex = set() vertex.add((0, 0)) edge = set() cur = [..

아래 문제와 거의 같다. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: wordSet = set(wordList) wordSet.discard(beginWord) if endWord no..