pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 2~9 범위의 문자열에 대해 가능한 모든 문자 출력 책에서 구현된 코드 def letterCombinations(digits: str) -> list[str]: def dfs(index, path): if len(path) == len(digits): result.append(path) return for i in range(idex, len(digits)): for i in dic[digits[i]]: dfs(i + 1, path + j) if not digits: return [] dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 1로 이어진 섬의 개수 출력 책에서 구현된 코드 def numIslands(self, grid: list[list[str]]) -> int: def dfs(i, j): if i = len(grid) or \ j = len(grid[0]) or \ grid[i][j] != '1': return grid[i][j] = 0 dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': dfs(i, ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 그래프 객체의 일부 쌍(pair)들이 '연관되어' 있는 객체 집합 구조 오일러 경로 한붓 그리기 모든 간선을 한 번만 방문하는 유한 그래프 NP-complete (Non-deterministic Polynomial time) problem 비결정론적 다항시간 해밀턴 경로 - 각 정점을 한 번씩만 방문하는 무향/유향 그래프 경로 - 오일러 경로는 간선 기준, 해밀턴 경로는 정점 기준 해밀턴 순환 - 해밀턴 경로이면서 원래 출발점으로 돌아오는 경로 외판원 문제 (TSP, Traveling Salesman Problem) - 해밀턴 순환 중 최단 경로 비교 해밀턴 경로 한 번만 방문하는 경로 해밀턴 순환 한 번만 방문하여 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 상위 k번 이상 등장하는 요소 출력 책에서 구현된 코드 # heapq 이용 def topKFrequent(self, nums: list[int], k: int) -> list[int]: freqs = collections.Counter(nums) freqs_heap = [] for f in freqs: heapq.heappush(freqs_heap, (-freqs[f], f)) topk = list() for _ in range(k): topk.append(heapq.heappop(freqs_heap)[1]) return topk # Counter def topKFrequent(self, nums: list..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 중복 문자가 없는 가장 긴 부분 문자열의 길이 리턴 책에서 구현된 코드 def lengthOfLongestSubstring(self, s: str) -> int: used = {} max_length = start = 0 for index, char in enumerate(s): if char in used and start int: start = max_len = 0 dic = defaultdict(int) for i in range(len(s)): end = i + 1 c = s[i] if dic[c] == 0: dic[c] = end else: start, dic[c] = max(dic[c], star..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 입력받은 두 문자열 jewels, stones에 대해, jewels의 각 문자들이 stones에 포함된 개수의 합 책에서 구현된 코드 def numJewelsInStones(self, J: str, S: str) -> int: return sum(s in J for s in S) 기억해야할 기법 Boolean을 1과 0으로 인식 가능 True + True -> 2 문제 접근 방식 Stone의 문자를 중심으로 True / False의 합을 구함 sum에서 리스트 기호([]) 없이 되는 이유? s in J for s in S의 return은 Generator Generator는 기본 표현은 parenthesiz..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 해시맵 구현 책에서 구현된 코드 # 생략 기억해야할 기법 doubling시 고려할 점 기존 배열을 살린 상태에서 복사하기 put을 진행하면서 load factor가 기준치를 넘으면 doubling을 하는데, 만약 doubling으로 copy를 put으로 진행하면서 load factor가 다시 기준치를 넘는다면? while로 다음 포인터 이동시 current = current.next를 자주 망각함 내가 구현한 코드 class ListNode: def __init__(self, key: int, val: int, next = None): self.val = val self.key = key self.next ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 해시 테이블 (해시 맵) 키를 값에 매핑할 수 있는 구조로, 연관 배열 추상 자료형 대부분의 연산이 Amortized O(1), 데이터 양에 관계 없이 빠른 성능을 기대할 수 있음 해시 해시 함수 - 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용하는 함수 해싱 - 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 - 정보를 빠르게 저장하고 검색하기 위한 중요한 기법 - 최적의 검색이 필요한 분야에서 사용 - 심볼 테이블 등 자료구조를 구현 - 체크섬, 손실 압축, 무작위화 함수, 암호 등에 관련됨 성능 좋은 해시 함수의 특징 충돌의 최소화 쉽고 빠른 연산 값의 균일 분포 키의 모든 정보 이용 높은 사용 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. GIL : Global Interpreter Lock 파이썬이 느린 주요 원인 원인 파이썬 최초의 공식 구현체 CPython의 개발 초기에 번거로운 동시성 관리를 편리하게 스레드 세이프를 하지 않은 CPython의 메모리 관리를 쉽게 하기 위해 스레드 세이프 - 멀티스레드 프로그래밍에서 어떤 함수 / 변수 / 객체가 여러 스레드로부터 동시에 접근이 일어나도 프로그램의 실행에 문제가 없음을 의미 - 전역 변수 등 공유 자원, Side Effect 등 GIL은 하나의 스레드가 자원을 독점하는 형태 멀티 코어가 당연한 현재에는 하나의 스레드가 자원을 독점하는 제약은 성능에 치명적임 PriorityQueue와 같은 시도에도 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합 책에서 구현된 코드 def mergeKLists(self, lists: List[ListNode]) -> ListNode: root = result = ListNode(None) heap = [] for i in range(len(lists)): if lists[i]: heapq.heappush(heap, (lists[i].val, i, lists[i])) while heap: node = heapq.heappop(heap) idx = node[1] result = next = node[2] result = result.next if result.next:..