Scribbling

class Solution: def maxProfit(self, prices: List[int]) -> int: profit, prev = 0, prices[0] for i in range(1, len(prices)): if prices[i] >= prev: profit += prices[i] - prev prev = prices[i] return profit

전형적인 DP 문제 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [[0] * (i+1) for i in range(len(triangle))] dp[0][0] = triangle[0][0] for i in range(1, len(triangle)): dp[i][0] = dp[i-1][0] + triangle[i][0] for j in range(1, i): dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][-1] = dp[i-1][-1] + triangle[i][-1] return min(dp[len(triangle)-1])

""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Node') -> 'Node': self.helper(root) return root def helper(self, node): if not node: return leftmost, prev = None, None cur = node while cur: if c..

개인적으론 매우 어려웠던 문제이다. Binary Search를 이용하라는 힌트가 있음에도 풀지 못하였다. 처음 떠올렸던 방식은 O(N**2)이었는데 N이 너무 커서 안될것 같았다. 이래저래 Binary Search를 적용할 방안을 떠올려보았지만, 끝까지 생각이 나지 않아 구글링을 해따... 아이디어는 매우 간단하다. --> 돌 사이의 간격에 대해 binary search를 하면된다. 효율성은 O(log(D)*N)이므로 최선의 알고리즘이다. def solution(distance, rocks, n): answer = -1 rocks.sort() rocks.append(distance) l, r = 0, distance while l = mid: prev = rock else: num_removed += 1..

1. 네트워크와 인터넷 초기의 컴퓨터 네트워크는 한 건물 안에 있는 컴퓨터를 연결하는 수준이었다. 그리고 이러한 의미에서 이를 LAN(Local Area Network)라고 불렀다. 개인 PC의 메인보드에는 랜카드가 달려 있는데, 이는 몇 킬로미터 내의 네트워크를 연결가능한 카드라는 의미이다. 여러 컴퓨터를 연결하여 LAN을 구성하는 방법은 많은데, 이를 토폴로지(Topology)라고 하며 스타형, 링형, 버스형 등이 있다. 제록스사는 버스형에 CSMA/CD(Carrier Sense Multiple Access/Collison Dectect) 프로토콜을 사용하는 LAN을 이더넷(ethernet)이라고 이름 붙였다. 이더넷은 버스에 연결만 하면 LAN에 기기를 추가할 수 있으며, 개별 기기의 고장이 네트워..

Binary Search를 이용한다. 숫자가 클 때는 Binary Search를 의심해봐야한다. def solution(n, times): answer = int(1e20) max_time = n * max(times) l, r = 0, max_time while l = n: answer = min(answer, mid) r = mid - 1 else: l = mid + 1 return answer

O(N) 메모리를 사용한다면 매우 쉬운 문제이지만, 아래 Follow-up을 반영하여 O(1) 메모리를 사용하여 푸는 것은 조금 생각이 필요하다. Constant Memory로 어찌 풀지 생각하다가 아래 조건에서 힌트를 얻었다. Node의 개수에 제한이 있다는 것. Perfect Binary Tree에서 이와 같은 조건은 곧 최대 높이로 직결된다. 이를 활용하면, 트리의 층마다 last node 주소를 저장해놓고 갱신하는 방식으로 풀 수 있다. """ # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val..

현재 node -> Flattened Left Tree -> Flattened Right Tree # 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 flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if not root: return None head, tail = self.helpe..

1. 파일 시스템 1.1 파일 시스템 컴퓨터 시스템에는 다양한 종류의 파일이 있으며, 하드디스크 등의 저장장치에 보관된다. 보관 과정에서 사용자가 직접 개입하면 다른 사용자의 파일이 훼손되거나 저장장치 내부를 어지럽히는 등의 문제가 발생할 수 있다. 운영체제는 이를 방지하기 위해 사용자가 직접 파일을 보관하거나 접근하지 못하도록 한다. 대신 파일을 보관하고 관리하는 파일 관리자를 두는데, 이를 파일 시스템이라고 한다. 파일 시스템에서 파일 관리자는 사용자의 요청에 따라 파일을 저장하거나 읽을 수 있다. 파일 관리자는 파일 테이블을 사용하여 파일의 생성, 수정, 삭제 등을 수행한다. 사용자가 특정 파일에 접근하려면 파일 관리자로부터 권한을 획득해야 하는데, 이를 파일 디스크립터라고 한다. 1.2 파일 시스..

그냥...DFS로 푼다... from collections import defaultdict import copy def solution(tickets): tickets.sort() # dictionary["ICN"] = ["ATL", "SFO"] dictionary = defaultdict(list) for ticket in tickets: dictionary[ticket[0]].append(ticket[1]) def dfs(cur, dictionary, edges, path): if not edges: return path for v in dictionary[cur]: next_dictionary = copy.deepcopy(dictionary) next_dictionary[cur].remove(v)..