pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 스택으로 큐 구현 책에서 구현된 코드 class MyQueue: def __init__(self): self.input = [] self.output = [] def push(self, x: int) -> None: self.input.append(x) def pop(self) -> int: self.peek() return self.output.pop() def peek(self) -> int: if not self.output: while self.input: self.output.append(self.input.pop()) return self.output[-1] def empty(self) -> bo..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 큐를 이용해 다음 연산을 지원하는 스택 구현 push(x) pop() top() empty() 책에서 구현된 코드 class MyStack: def __init__(self): self.q = collections.deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 온도 리스트를 입력받아 각 온도가 더 높은 값을 만날 때까지의 걸린 시간 리스트 출력 책에서 구현된 코드 def dailyTemperatures(self, T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in enumerate(T): while stack and cur > T[stack[-1]]: last = stack.pop() answer[last] = i - last stack.append(i) return answer 기억해야할 기법 [0] * len(T) 더 짧아서 깔끔해보임 index와 list를 알 경우, stack..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 중복 문자 제거 사전식 순서로 나열 책에서 구현된 코드 # 재귀를 이용한 분리 def removeDuplicateLetters(self, s: str) -> str: for char in sorted(set(s)): suffix = s[s.index(char):] if set(s) == set(suffix): return char + self.removeDuplicateLetters(suffix.replace(char,'')) return '' # 스택을 이용한 문자 제거 def removeDuplicateLetters(self, s: str) -> str: counter, seen, stack = coll..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 괄호로 된 입력이 올바른지 판별 책에서 구현된 코드 def isValid(self, s: str) -> bool: stack = [] table = { ')': '(', ']': '[', '}':'{' } for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0 기억해야할 기법 for의 in에 dict는 key로 비교한다 bool로 return할 시, 비교 연산 사용이 깔끔한듯 내가 구현한 코드 def isValid(s:..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 스택, 큐는 가장 고전적인 자료구조 중 하나 스택은 거의 모든 애플리케이션을 만들 때 사용됨 파이썬은 스택/큐 자료형을 따로 제공하지 않지만, 리스트가 두 기능을 모두 제공 추상 자료형 (ADT) 스택에 요소들이 차곡차곡 쌓인 것처럼 생각됨 실제로 연결 리스트로 구현시, 물리 메모리에 순서와 관계 없이 여기저기 무작위 배치됨 스택 후입선출 (LIFO, Last In First Out) 주요 2가지 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형 - push() : 요소를 컬렉션에 추가 - pop() : 가장 최근 삽입한 요소를 제거 큐 선입선출 (FIFO, First In First Out) 시퀀스의 한쪽 끝에..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 인덱스 m에서 n까지를 역순으로 만들기 책에서 구현된 코드 def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head or m == n: return head root = start = ListNode(0) root.next = head for _ in range(m-1): start = start.next end = start.next for _ in range(n-m): tmp, start.next, end.next = start.next, end.next, end.next.next start.next.next = t..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 연결 리스트의 홀수 노드 다음 짝수 노드가 오도록 재구성, 공간 복잡도 O(1), 시간 복잡도 O(n) 책에서 구현된 코드 def OddEvenList(self, head: ListNode) -> ListNode: if head in None: return None odd = head even = head.next even_head = head.next while even and even.next: odd.next, even.next = odd.next.next, even.next.next odd, even = odd.next, even.next odd.next = even_head return head 기..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 연결 리스트를 페어 단위로 스왑 책에서 구현된 코드 def swapPairs(self, head: ListNode) -> ListNode: if head and head.next: p = head.next head.next = self.swapPairs(p.next) p.next = head return p return head 기억해야할 기법 반복되는 substruct에 대한 재귀 설계 node1 -> node2 -> node3 ... node2가 node1을 가리킴 node1이 swap이 끝난 node3을 가리킴 내가 구현한 코드 def swapPairs(self, head: ListNode) -> Li..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 역순으로 저장된 연결리스트의 숫자 덧셈 책에서 구현된 코드 def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: root = head = ListNode(0) carry = 0 while l1 or l2 or carry: sum = 0 if l1: sum += l1.val l1 = l1.next if l2: sum += l2.val l2 = l2.next carry, val = divmod(sum+carry, 10) head.next = ListNode(val) head = head.next return root.next 기억해야할 기법 두 연결리스트의 길..