Scribbling

We already know that all the elements are in [0, 1, 2]. So, we count each element's frequencies. class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ count = [0] * 3 for num in nums: count[num] += 1 count[2] = count[1] + count[0] count[1] = count[0] for i in range(count[1]): nums[i] = 0 for i in range(count[1], count[2]): nu..

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if target matrix[-1][-1]: return False m, n = len(matrix), len(matrix[0]) row = 0 # row search l, r = 0, m - 1 while l target: r = mid - 1 else: row = max(row, mid) l = mid + 1 # column search l, r = 0, n - 1 while l

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) for y in range(m): for x in range(n): if matrix[y][x] == 0: self.inspect_row(matrix, y, x) self.inspect_column(matrix, y, x) elif matrix[y][x] == 'row inspected zero': self.inspect_column(matrix, y, x) elif matrix[y][x] == 'colum..

1. 컴퓨터의 기본 구성 1.1 하드웨어 - 컴퓨터는 CPU, 메인메모리, 입력장치, 출력장치, 저장장치로 구성된다. - 메인보드는 CPU와 메모리 등 다양한 부품을 연결하는 커다란 판이다. 메인보드에는 버스가 복잡하게 얽혀 있으며 전력이 공급되면 버스로 연결된 부품이 작동한다. 1.2 폰노이만 구조 오늘날의 컴퓨터는 대부분 폰노이만 구조를 따른다. 폰노이만 구조는 CPU, 메모리, 입출력장치, 저장장치가 버스로 연결되어 있는 구조를 말한다. 이는 메모리를 이용하여 프로그래밍이 가능한 컴퓨터 구조로, 하드웨어 변경 없이 프로그램만 교체하여 메모리에 올리는 방식이다. 폰노이만 구조의 핵심적인 특징은 '모든 프로그램은 메모리에 올라와야 실행 가능하다'는 것이다. 운영체제도 프로그램이기 때문에 메모리에 올라와..

class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (m+1) for _ in range(n+1)] for i in range(1, m+1): dp[0][i] = i for i in range(1, n+1): dp[i][0] = i for i in range(1, n+1): for j in range(1, m+1): if word1[j-1] != word2[i-1]: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 else: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp..

class Solution: def simplifyPath(self, path: str) -> str: stack = [] paths = path.split('/') for path in paths: if path: if path == '.': continue elif path == '..': if stack: stack.pop() else: stack.append(path) ret = '/' for path in stack: ret += path + '/' if not stack: return ret return ret[:-1]

class Solution: def mySqrt(self, x: int) -> int: ret = 0 l, r = 0, x while l x: r = mid - 1 else: ret = max(ret, mid) l = mid + 1 return ret

class Solution: def addBinary(self, a: str, b: str) -> str: if len(b) > len(a): a, b = b, a b = '0'*(len(a)-len(b)) + b ret = '' carry = 0 for i in range(len(a)-1, -1, -1): temp = int(a[i]) + int(b[i]) + carry ret += str(temp%2) carry = temp//2 if carry: ret += str(1) return ret[::-1]

가장 먼저 떠오르는 방법은 완전 탐색 --> Time Limit Exceeded class Solution: def minPathSum(self, grid: List[List[int]]) -> int: n, m = len(grid), len(grid[0]) dp = [[int(1e9)] * m for _ in range(n)] self.explorer(dp, grid, 0, 0, 0) return dp[n-1][m-1] def explorer(self, dp, grid, i, j, nowSum): nowSum += grid[i][j] if i == len(grid) - 1 and j == len(grid[0]) - 1: dp[i][j] = min(dp[i][j], nowSum) return if nowS..

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: n, m = len(obstacleGrid[0]), len(obstacleGrid) board = [[0] * n for _ in range(m)] board[0][0] = 1 obstacles = [] for i in range(m): for j in range(n): if obstacleGrid[i][j] == 1: board[i][j] = 0 obstacles.append((i, j)) for j in range(1, n): if (0, j) in obstacles: continue board[0][j] = board[0][j-1] for ..