pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 원형 데크 설계 책에서 구현된 코드 class MyCircularDeque: def __init__(self, k: int): self.head, self.tail = ListNode(None), ListNode(None) self.k, self.len = k, 0 self.head.right, self.tail.left = self.tail, self.head def _add(self, node: ListNode, new: ListNode): n = node.right node.right = new new.left, new.right = node, n n.left = new def _del(self, no..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 데크(Deque, Double-Ended Queue) 양쪽 끝을 모두 추출할 수 있는 큐 형태의 추상 자료형 양쪽에서 삽입/삭제 모두 가능 스택과 큐의 특징을 모두 가짐 배열 / 연결 리스트 모두 구현 가능하지만, 이중 연결 리스트 구현이 어울림 우선순위 큐 큐 / 스택 같은 추상 자료형과 유사하나 요소의 우선순위와 연관 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형 - ex) 최댓값 추출 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있음 시간 정렬에 대한 시간 - S(n) = O(n log n) 새 요소의 삽입/삭제 시간 - O(S(n)) 최대값을 가져오는데 걸리는 시간 - O(1) 그러나 실제로..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 원형 큐 디자인 책에서 구현된 코드 class MyCircularQueue: def __init__(self, k: int): self.q = [None] * k self.maxlen = k self.p1 = 0 self.p2 = 0 def enQueue(self, value: int) -> bool: if self.q[self.p2] is None: self.q[self.p2] = value self.p2 = (self.p2 + 1) % self.maxlen return True else: return False def deQueue(self) -> bool: if self.q[self.p1] is Non..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 스택으로 큐 구현 책에서 구현된 코드 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..