Scribbling

파이썬 코드로 작성한 KMP 알고리즘이다. 이해하기 어렵다면 아래 사이트를 참고하자. https://bowbowbow.tistory.com/6 def getPi(pattern): m, j = len(pattern), 0 pi = [0] * m for i in range(1, m): while j > 0 and pattern[i] != pattern[j]: j = pi[j-1] if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi def kmp(string, pattern): ret = [] pi = getPi(pattern) n, m, j = len(string), len(pattern), 0 for i in range(n): while j > 0 and s..

class Solution: def removeDuplicates(self, nums: List[int]) -> int: prev = None i = 0 for num in nums: if num != prev: nums[i] = num prev = num i += 1 return i

문제의 쉬운 version... 재귀를 이용해서 푸는 방법을 익혀두자. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: k = 2 count, node = 0, head while node and count < k: node = node.next count += 1 if count < k: return head n..

1. 통신 1.1. 병렬 통신 - 말 그대로 신호선을 여러개 사용하는 통신 방식. 가격이 비싸서 요즘에는 잘 사용하지 않음. 1.2. 직렬 통신 - 신호선을 2개만 사용하는 통신 방식. 전형적으로는 시작 비트와 정지 비트 그리고 시분할 멀티플렉싱 방식을 사용함. 1.3. USB (Universial Serial Bus) - 병렬 통신 및 직렬 통신은 하나의 포트에 하나의 기기밖에 연결할 수 없다는 큰 단점을 가진다. 이를 해결하기 위해, 인터페이스를 통합하여 하나의 커넥터(or 포트)로 각종 주변기기를 연결할 수 있도록 한 것이 바로 USB이다. USB는 데이터 패킷 (Packet) 방식을 사용한다. 패킷은 마치 소포의 송장처럼 데이터가 어디에서 왔고, 어디로 가야하는지 등의 정보를 포함한다. 2. 네트..

Recursion solution. Time Complexity: O(N), Memory Complexity: O(1) # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: return self.helper(head, k) def helper(self, node, k): if not node: return None cur = node for i in ran..

1. 컴퓨터 아키텍처: 컴퓨터의 여러 구성 요소를 배치하는 방법 - 프로세서 코어 (CPU): CPU = ALU + 레지스터 + 실행 장치 - 마이크로프로세서: 메모리와 I/O가 프로세서 코어와 같은 패키지에 들어 있지 않은 프로세서 - 마이크로컴퓨터: 메모리 및 I/O가 프로세서 코어와 같은 패키지에 들어 있는 프로세서 (e.g. 식기세척기의 컴퓨터) - 단일 칩 시스템(SOC): 다소 복잡한 마이크로컴퓨터 (e.g. WIFI SOC) 2. 함수(프로시저) 호출 흐름 함수를 호출하는 부분에서 함수를 실행한 후, 원래의 자리로 돌아올 필요가 있다. 이 때, 원래의 자리를 기억해야 한다. 3. 스택 재귀 함수가 제대로 동작하기 위해서는 반환 주소를 여럿 저장할 수 있어야 한다. 또한 함수에서 호출 지점으로..

class Solution: def generateParenthesis(self, n: int) -> List[str]: self.ret = [] self.helper(n, n, '') return self.ret def helper(self, l, r, path): if l == 0: self.ret.append(path + (')' * r)) return if l == r: self.helper(l-1, r, path + '(') else: self.helper(l-1, r, path + '(') self.helper(l, r-1, path + ')')

1. 컴퓨터 - 전자 부품을 다양하게 조합하여 비트를 조작하는 회로로, 메모리, 입출력, CPU로 나뉘어진다. - 32비트 컴퓨터는 보통 메모리를 4바이트 덩어리로, 64비트 컴퓨터는 8바이트 덩어리로 구성한다. 2. CPU 2.1. 산술 논리 장치 (ALU) - CPU의 핵심 장치로 산술 계산, 불리언 대수 및 기타 연산을 수행하는 방법을 알고 있는 장치. 2.2. 실행장치 (제어 장치) - 명령어: 어떤 일을 할지 알려주는 비트 패턴 - 프로그램 카운터: 명령어가 들어있는 메모리의 주소가 들어있는 카운터 - 실행 장치는 프로그램 카운터가 가리키는 주소에서 명령어를 fetch한다. - 누산기: ALU의 연산 결과를 임시로 보관하는 레지스터 2.3. 명령어 집합 구성 ㅣ모드 2비트ㅣㅣ명령코드 4비트ㅣㅣ주..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: length = 0 cur = head while cur != None: length += 1 cur = cur.next prv, cur = None, head num_move = length - n while num_move > 0: prv = cur cur = cur.next num_move -..

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: ret = [] nums.sort() previ = None for i in range(len(nums)-3): if nums[i] == previ: continue prevj = None for j in range(i+1, len(nums)-2): if nums[j] == prevj: continue preSum = nums[i] + nums[j] l, r = j + 1, len(nums) - 1 while l < r: summation = preSum + nums[l] + nums[r] if summation < target: l += 1 elif su..