Scribbling

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

간단하면서도 재밌는 문제 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: smaller_train = ListNode() s_ptr = smaller_train bigger_train = ListNode() b_ptr = bigger_train cur = head while cur != None: if cur.val < x: s_ptr.next = cur s..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None new_head = ListNode() ptr = new_head reg, freq = head.val, 0 cur = head while cur != None: if reg != cur.val: if freq == 1: temp = ListNode(reg) ptr.n..