pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 연결 리스트의 홀수 노드 다음 짝수 노드가 오도록 재구성, 공간 복잡도 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 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 데이터 요소의 선형 집합 메모리에 물리적인 순서대로 저장되지 않음 다양한 추상 자료형(ADT) 구현의 기반 시간 특정 인덱스에 접근 : O(n) - 전체를 순차 탐색 해야함 시작/끝 지점 - 추가/삭제/추출 O(1)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력 책에서 구현된 코드 def arrayPairSum(self, nums: list[int]) -> int: return sum(sorted(nums)[::2]) 내가 구현한 코드 def array_part_one(nums: list[int]) -> int: nums.sort() return sum(nums[::2]) 리트코드 제출시 두 코드가 메모리에서 차이 0.1 MB 차이로 90%와 34%라는 큰 차이를 보임 그런데 왜 새로운 객체를 생성하는 sorted가 in-place sort보다 메모리를 적게 소비하지? 속도도 똑같음 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 합을 0으로 만드는 3개 엘리먼트 모두 출력 책에서 구현된 코드 def threeSum(self, nums: list[int]) -> list[list[int]]: results = [] nums.sort() for i in range(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: continue left, right = i+1, len(nums)-1 while left 0: right -= 1 else: result.a..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 높이에 따라 쌓일 수 있는 물의 총계 계산 책에서 구현된 코드 def trap(self, height: list[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(height[left], left_max), max(height[right], right_max) if left_max int: stack = [] volume = 0 for i in..