pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 중복 문자 제거 사전식 순서로 나열 책에서 구현된 코드 # 재귀를 이용한 분리 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 기억해야할 기법 두 연결리스트의 길..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 연결 리스트 뒤집기 책에서 구현된 코드 # 재귀 def reverseList(self, head: ListNode) -> ListNode: def reverse(node: ListNode, prev: ListNode = None): if not node: return prev next, node.next = node.next, prev return reverse(next, node) return reverse(head) # 반복 def reverseList(self, head: ListNode) -> ListNode: node, prev = head, None while node: next, node.nex..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 정렬된 두 연결 리스트를 오름차순으로 합치기 책에서 구현된 코드 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if (not l1) or (l2 and l1.val > l2.val): l1, l2 = l2, l1 if l1: l1.next = self.mergeTwoLists(l1.next, l2) return l1 기억해야할 기법 병합 정렬 (17장에서 나온다고 함) 재귀를 이용 두 리스트의 포인터가 가리키는 값 중 더 작은 값을 선택 하나씩 소거한 후 재귀의 결과로 결과 연결 리스트가 만들어짐 내가 구현한 코드 None 또 low le..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 단일 연결 리스트의 팰린드롬 판별 책에서 구현된 코드 def isPalindrome(self, head: ListNode) -> bool: rev = None slow = fast = head while fast and fast.next: fast = fast.next.next # 단일 연결리스트 reverse rev, rev.next, slow = slow, rev, slow.next if fast: slow = slow.next while slow and slow.val == rev.val: slow, rev = slow.next, rev.next return not rev 기억해야할 기법 Runner ..