pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 이진 검색 (Binary Search) 정렬된 배열에서 타겟을 찾는 검색 알고리즘 시간 복잡도 O(log n) 이진 탐색 트리(Binary Search Tree)와의 차이 이진 탐색 트리 - 정렬된 구조를 저장하고 탐색하는 '자료구조' 이진 검색 - 정렬된 배열에서 값을 찾아내는 '알고리즘' 이진 검색의 구현 mid를 구할 때 보통 (left+right) // 2를 사용 그러나 두 수의 합으로 인해 오버플로우가 발생할 수 있음 따라서 다음과 같이 구함 mid = left + (right - left) // 2

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 원점(0,0)으로부터 유클리드 거리가 가까운 순서 k개의 좌표 출력 책에서 구현된 코드 class Solution: def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]: heap = [] for (x, y) in points: dist = x ** 2 + y ** 2 heapq.heappush(heap, (dist, x, y)) result = [] for _ in range(K): (dist, x, y) = heapq.heappop(heap) result.append((x, y)) return result 기억해야할 기법 heapq..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 [0,1,2] 중 하나의 값인 배열을 in-place sort하기 책에서 구현된 코드 class Solution: def sortColors(self, nums: List[int]) -> None: red, white, blue = 0, 0, len(nums) while white 1: blue -= 1 nums[white], nums[blue] = nums[blue], nums[white] else: w..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 t가 s의 애너그램인지 출력 책에서 구현된 코드 class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t) 기억해야할 기법 문자열에 포함된 알파벳의 종류, 개수가 모두 일치하는지 확인하려면 정렬할 것 내가 구현한 코드 class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t) 책과 일치

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 숫자 배열을 이어붙여 만들 수 있는 가장 큰 수 출력 책에서 구현된 코드 class Solution: # 문제에 적합한 비교 함수 @staticmethod def to_swap(n1: int, n2: int) -> bool: return str(n1) + str(n2) str: i = 1 while i 0 and self.to_swap(nums[j - 1], nums[j]): nums[j], nums[j - 1] = nums..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 단일 연결리스트의 삽입정렬 구현 책에서 구현된 코드 class Solution: def insertionSortList(self, head: ListNode) -> ListNode: # 초기값 변경 cur = parent = ListNode(0) while head: while cur.next and cur.next.val head.val: cur = parent retur..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 [start, end] 구간의 리스트가 주어질 때, 이 구간들의 겹치는 부분을 병합하여 출력 책에서 구현된 코드 class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: merged = [] for i in sorted(intervals, key=lambda x: x[0]): if merged and i[0] List[List[int]]: result = [] for start, end in sorted(intervals, key=lambda x: x[0]): if result and end

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 연결 리스트 정렬 책에서 구현된 코드 class Solution: def sortList(self, head: ListNode) -> ListNode: # 연결 리스트 -> 파이썬 리스트 p = head lst: List = [] while p: lst.append(p.val) p = p.next # 정렬 lst.sort() # 파이썬 리스트 -> 연결 리스트 p = head for i in range(len(lst)): p.val = lst[i] p = p.next return head 기억해야할 기법 연결 리스트 정렬 방법 연결 리스트를 순차탐색하여 비교할값들의 배열로 바꿈 정렬 연결 리스트를 순차탐색하..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 정렬 알고리즘 목록의 요소를 특정 순서대로 넣는 알고리즘 숫자식 순서(Numerical Order) / 사전식 순서(Lexicographical Order) 버블 정렬 이웃한 두 데이터의 대소비교를 n번 수행하는 알고리즘 시간복잡도 O(n2) def bubblesort(A): # (1) for i in range(1, len(A)): # (2) for j in range(0, len(a)-i): # (3) if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A[j] # (1) 2개씩 비교하니까 n-1번 수행 # (2) 0부터 매 루프마다 i개씩 뺀 범위에서 비교 수행 # (3) 앞 요소가 더 크면..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 리스트에 포함된 두 문자열이 더해져서 팰린드롬이 되는 문자열의 인덱스 pair들 출력 책에서 구현된 코드 import collections from typing import List # 트라이 저장할 노드 class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) self.word_id = -1 self.palindrome_word_ids = [] class Trie: def __init__(self): self.root = TrieNode() @staticmethod def is_palindrome(word: s..