pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 덧셈으로 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴 책에서 구현된 코드 def twoSum(self, nums: List[int], taregt: int) -> List[int]: nums_map = {} for i, num in enumerate(nums): if target - num in nums_map: return [nums_map[target - num], i] nums_map[num] = i 기억해야할 기법 enumerate test = [1,2,3] list(enumerate(test)) # [(0, 1), (1, 2), (2, 3)] in dict()시 key를 기준 test = {..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 7장 배열 정의 값 또는 변수 엘리먼트의 집합으로 구성된 구조 하나 이상의 인덱스 또는 키로 식별 연속 방식 자료구조는 연속 방식과 포인터 기반 연결 방식으로 나뉨 배열은 연속 방식 요소의 주소가 연속적인 값으로 연결된 형태 추상 자료형 (ADT)의 실제 구현은 대부분 배열 또는 연결 리스트를 기반 - ex) 스택을 연결 리스트로 구현, 큐를 배열로 구현 C언어 기준의 배열 크기를 지정하고, 해당 크기만큼 연속된 메모리 공간을 할당 받는 자료형 생성 후 크기를 변경할 수 없음 (크기 고정) 어느 위치나 O(1)에 조회가 가능하다는 장점 동적 배열 전체 데이터 크기를 미리 가늠하기 어려움 크기를 지정하지 않고 자동 re..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 책에서 구현된 코드 def longestPalindrome(self, s:str) -> str: def expand(left: int, right: int) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left+1:right] if len(s) < 2 or s == s[::-1]: return s result = '' for i in range(len(s)-1): result = max(result, expand(i, i+1), expand(i, i+2), key=len) return re..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 애너그램 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 의미 문자의 순서가 바뀌면 같아지는 단어들끼리 묶은 리스트 반환 책에서 구현된 코드 def groupAnagrams(self, strs: list[str]) -> list[list[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams[''.join(sorted(word))].append(word) return list(anagrams.values()) 기억해야할 기법 frozenset을 dict의 key로 사용시 주의 문자의 개수를 생략하기 때문에, 사용된 알파벳이 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 금지 단어 제외 대소문자 구분하지 않음 구두점(마침표, 쉼표 등) 무시 책에서 구현된 코드 def mostCommonWord(self, paragraph: str, banned: list[str]) -> str: words = [word for word in re.sub(r'[^\w]', ' ', paragraph) .lower().split() if word not in banned] counts = collections.Counter(words) return counts.most_common(1)[0][0] 기억해야할 기법 정규식 다시 확인 \w 같은 표현 기억이 잘 안남 리스트 컴프리헨션 활용 특정 조..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 로그 재정렬 기준 가장 앞 부분은 식별자 우선순위 : 문자 > 숫자 문자가 같으면 식별자 숫자 로그는 입력 순서 유지 책에서 구현된 코드 def reorderLogFiles(self, logs: list[str]) -> list[str]: letters, digits = [], [] for log in logs: if log.split()[1].isdigit(): digits.append(log) else: letters.append(log) letters.sort(key=lambda x: (x.split()[1:], x.split()[0])) return letters + digits 기억해야할 기법 문제..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 책에서 구현된 코드 def reverseString(self, s: list[str]) -> None: s.reverse() 기억해야할 기법 책에 기술된 s의 type이 현재는 불가능 책에 기술된 내용 - s: List[str] - List를 찾지 못함 가능한 방식으로 변경 - s: list[str] 값을 저장하는 등호에 쉼표(,) 활용 a, b = c, d 객체 내부값을 수정할 시 메서드를 호출할 것 내가 구현한 코드 def reverse_string(s:list): for i in range(len(s) // 2): s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i] 함수 parameter ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 책에서 구현된 코드 def isPalindrome(s: str) -> bool: s = s.lower() s = re.sub('[^a-z0-9]', '', s) return s == s[::-1] 기억해야할 기법 isalnum(), isalpha() 알파벳인지, 숫자인지 등등을 확인해주는 내장함수가 있음 re(pattern, replace, str) str에서 pattern을 찾아 replace로 바꿈 re.sub('[^a-z0-9]', '', s) - 알파벳 소문자와 숫자가 아닌 것은 삭제 - [] 중에 하나 - ^는 not 문자 뒤집기 [::-1]이 reverse보다 빠름 [시작인덱스 : 끝인덱스 : 다음인덱스에 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 5장 리스트, 딕셔너리 리스트와 딕셔너리는 코딩 테스트에서 무조건 사용 문제 풀이에 자유자재로 활용할 수 있도록 숙지 1) 리스트 리스트란? 순서대로 저장하는 시퀀스 - 입력 순서가 유지됨 값을 변경할 수 있는 Mutable 동적 배열로 구현됨 - C++의 Vector, Java의 ArrayList 매우 다양한 기능을 제공 - 스택/큐로써의 기능도 모두 제공 - 이는 다른 언어에 비해 매우 유리한 조건 큐로써 사용할 시 주의 - pop(0)는 O(n)을 소요 - 가장 앞의 요소를 제외한 나머지 요소들을 copy해야하기 때문 - Deque를 대산 사용 (추후 다룰 예정) min/max도 O(n) - 순차탐색을 하는듯 -..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 4장 빅오, 자료형 1) 빅오 빅오란? 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기법 = 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나 시간 복잡도(Time Complexity) = 점근적 실행 시간 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity) 빅오로 시간 복잡도를 표현할 때는 최고차항만 표기, 계수 무시 (ex) $$4n^2+3n+4 \approx O(n^2)$$ 빅오의 종류 1 O(1) 해시 테이블 상수 시간 매우 가치있음 2 O(log n) 이진 탐색 입력에 영..