pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 중복 문자가 없는 가장 긴 부분 문자열의 길이 리턴 책에서 구현된 코드 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와 같은 시도에도 ..

이 글은 "TCPschool/코딩과 데이터/MySQL"을 읽고 주관적으로 작성된 글입니다. https://tcpschool.com/mysql/intro 코딩교육 티씨피스쿨 4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등 tcpschool.com 1. MySQL 개요 가장 널리 사용되고 있는 관계형 데이터베이스 관리 시스템 오픈소스 다중 사용자와 다중 스레드 지원 C, C++, Java, PHP 등 여러 언어의 API 제공 2. 데이터베이스 1) 데이터베이스란? 통합하여 관리되는 데이터의 집합체 데이터베이스 관리 중복된 데이터 제거 자료 구조화 효율적 처리 여러 업무에 여러사용자가 데이터베이스 사용 가능 응용 프로그램과 다르게 별도의 미들웨어에 의해 관리됨 데이터..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 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:..

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