Scribbling

간단하면서도 재밌는 문제 # 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..

이 문제는 아래 문제와 상당히 유사하다. 33. Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/description/) 실제 구현도 유사하지만, Time Complexity는 다른데 그 이유를 생각해보면 흥미롭다. class Solution: def search(self, nums: List[int], target: int) -> bool: left, right = 0, len(nums) - 1 while left

class Solution: def removeDuplicates(self, nums: List[int]) -> int: reg, freq = None, None k = 0 for i, num in enumerate(nums): # update reg & freq if reg != num: reg = num freq = 1 else: freq += 1 if freq

1. 스케줄링 CPU 스케줄링은 CPU에 어떤 작업을 배정할지 결정하는 것이다. 컴퓨터 시스템의 효율은 이에 따라 달라진다. 앞서 배운 것 처럼, 프로세스는 생성 상태, 준비 상태, 실행 상태, 대기 상태 등의 여러 상태를 거치며 작업이 이루어진다. CPU 스케줄러는 프로세스가 생성된 후부터 종료될 때까지 모든 상태 변화를 조정한다. - 고수준 스케줄링: 고수준 스케줄링(high level scheduling)은 작업 스케줄링(job scheduling)이라고도 불리우며, 시스템 내의 전체 작업 수를 조절하는 것을 의미한다. - 저수준 스케줄링: 저수준 스케줄링(low level scheduling) 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다. - 중간 ..

문제 링크: https://leetcode.com/problems/largest-rectangle-in-histogram/ O(N)만에 푸는 방법을 떠올리는 것은 매우 어렵다. 이 문제를 O(N)에 풀 수 있는 방법은 monotonic stack을 이용하는 것이다. Monotonic Stack이란 stack을 쌓되 stack 내부가 오름차순 혹은 내림차순으로 정렬되도록 쌓는 것이다. 이 문제에서 Monotonic Stack이 사용되는 이유는 다음과 같다. 왼쪽에서부터 오른쪽으로 가면서 블록이 하나씩 추가된다고 고려했을 때, 이전에 추가된 블록에 비해 현재 블록의 높이가 작다면, 이전 블록의 높이가 직사각형의 최대 높이가 된다. 아래 그림에서 높이 2의 블록 차례가 오면, 높이 5와 높이 6의 블록은 더 ..

어케풀었누... 1. 내 방법 A. 각 점으로부터 오른쪽으로 연결된 네모의 개수를 저장한다. 1 0 1 0 0 1 0 3 2 1 5 4 3 2 1 1 0 0 1 0 B. 모든 열에 대해서 최대 직사각형 넓이를 계산한다. class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix: return 0 n, m = len(matrix), len(matrix[0]) dp = [[0] * m for _ in range(n+1)] # table for i in range(n): j = m - 1 count = 1 while j >= 0: if matrix[i][j] == '0': dp[i][j] = 0 count =..

1. 프로세스의 개요 1.1 프로세스 프로세스는 하나의 작업 단위이다. 프로그램은 하드디스크 같은 저장장치에 보관되어 있다가 마우스로 더블클릭하면 실행된다. 이 때, 실행된다는 것은 정적인 상태의 프로그램이 메모리에 올라와서 동적인 상태의 프로세스가 되는 것을 의미한다. 1.2 시분할 CPU가 1개인 컴퓨터에서 여러 개의 프로세스가 동시에 실행되는 것은, CPU가 시간을 쪼개어 여러 프로세스에 적당히 배분하기 때문이다. 1.3 프로그램에서 프로세스로의 전환 프로세스는 컴퓨터 시스템의 작업 단위로 태스크(task)로도 불린다. 운영체제는 프로그램을 메인 메모리로 올린다. 그리고 프로세스에 '프로세스 제어 블록(Process Control Block)'을 준다. 즉, 프로그램이 프로세스가 되었다는 것은 운영..

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: n, m = len(board), len(board[0]) for i in range(n): for j in range(m): if self.dfs(board, i, j, word, 0): return True return False def dfs(self, board, y, x, word, k): if k == len(word): return True if y = len(board) or x = len(board[0]) or board[y][x] == '@': return False char = word[k] if board[y][x..

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: self.ret = [] self.helper(nums, []) return self.ret def helper(self, nums, path): self.ret.append(path) if not nums: return for i, num in enumerate(nums): self.helper(nums[i+1:], path+[num])