Scribbling

class Solution: def numDecodings(self, s: str) -> int: candidates = set([str(i) for i in range(1, 27)]) # dp[i] denotes # of ways until s[i-1] dp = [0] * (len(s) + 1) dp[0] = 1 if s[0] in candidates: dp[1] = 1 for i in range(2, len(s)+1): # dp[n] = dp[n-2] * k2 + dp[n-1] * k1 k2 = 0 if s[i-2:i] in candidates: k2 += 1 k1 = 0 if s[i-1] in candidates: k1 += 1 dp[i] = dp[i-2] * k2 + dp[i-1] * k1 ret..

1. 교착 상태 1.1 교착 상태 임계구역이 존재하면 프로세스 간 상호 배제가 보장되지만, 작업이 더 이상 진행되지 않는 교착 상태에 빠지는 경우가 있다. 이처럼 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(Dead Lock)라고 한다. 교착 상태는 아사 현상과는 전혀 다르다. 아사 현상은 운영체제가 잘못된 정책을 사용하여 프로세스의 작업이 크게 지연되는 것을 의미한다. 반면 교착 상태는 여러 프로세스가 진행되는 과정에서 자연적으로 일어난다. 컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(혹은 파일), 응용 프로그램 등을 함께 사용할 때 발생할 수 있다. 1.2 자원 할당 그래프 자원 할당 그래프(Resource Allocat..

BFS로 순회해보자 # 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 from collections import deque class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if p == None and q == None: return True if p == None and q != None: return False if p != None and q =..

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() self.ret = [] self.dfs(nums, []) return self.ret def dfs(self, nums, path): self.ret.append(path) prev = None for i, num in enumerate(nums): if num != prev: prev = num self.dfs(nums[i+1:], path+[num]) Lazy version: class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() sel..

The key here is that we need to push elements from nums2 to nums1 while not disturbing the existing elements in nums1. So, put the elems from nums2 to nums1 from the end. class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ p1, p2 = m - 1, n - 1 for i in range(m+n-1, -1, -1): p1_val = nums1[p1]..

Binary Search Tree의 Validation 문제이다. BST 특성상 아래와 같이 순회하면 정렬된다는 특성을 이용한다. 즉, 순회하면서 점점 value가 커지는지만 체크하면 끝. # 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 isValidBST(self, root: Optional[TreeNode]) -> bool: self.reg = -pow(2, 31) - 1 return self.dfs(root) def dfs..

1. 초안 코드가 뭔가 복잡하다. 코드도 줄일겸 메모리를 O(1)으로 풀어보자. # 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 recoverTree(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.arr = [] self.helper(root) left, right = None, No..

n = 0 n = 1 n=2 n = 3 000 001 101 1100 100 1101 1001 1000 e.g. n=3 -> 100 + 1000, 101 + 1000, 001 + 1000, 000 + 1000 -> 역순 + 2의 n-1승 class Solution: def grayCode(self, n: int) -> List[int]: ret = [0] for i in range(n): ret += [x + pow(2, i) for x in reversed(ret)] return ret

1. 프로세스 간 통신 1.1 프로세스 간 통신의 개념 독립적인 프로세스끼리 서로 데이터를 주고 받는 경우 통신을 사용한다. 프로세스끼리 통신을 하는 경우 누가 먼저 작업할지, 작업이 언제 끝날지 등을 서로 알려주어야 하는데 이를 동기화라고 한다. - 프로세스 내부 데이터 통신: 하나의 프로세스 내의 2개 이상의 스레드가 통신하는 방식. - 프로세스 간 데이터 통신: 여러 프로세스끼리 통신하는 경우. - 네트워크를 이용한 데이터 통신: 여러 컴퓨터가 네트워크로 연결되어 있을 때 프로세스의 소켓을 이용한 통신 방식. 1.2 바쁜 대기와 동기화 전역 변수를 사용하여 통신하는 경우의 가장 큰 문제는 언제 데이터를 보낼지 데이터를 받는 쪽에서 모른다는 것이다. 데이터를 받는 측에서는 반복적으로 전역 변수의 값을..

개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경로를 찾는다. 나름 머리 써서 푼건데, 속도도 느리고 메모리 효율도 떨어져서 실망스럽다. import heapq class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: if endWord not in wordList: return [] if beginWord not in wordList: wordList.append(beginWord) s_idx = w..