pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 k개의 슬라이드마다 최대값을 담아 출력 책에서 구현된 코드 # 테스트케이스 변경으로 현재 책의 방식으로 통과되지 않음 (책에도 이슈관련 내용이 적혀있음) # github에 다른 분이 작성하신 수정된 방식 from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: deq, ans = deque(), [] for i in range(len(nums)): # 앞에서부터 out of window -> 제거 if deq and i-de..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 슬라이딩 윈도우 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용하는 문제를 풀이하는 알고리즘 네트워크에 사용되던 용어 (MAC 계층에서 본 적 있음) 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법 투포인터와의 차이점 고정 사이즈 윈도우를 사용함 정렬 여부에 관계없이 활용 좌->우로만 이동

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 unsigned int 입력의 1비트 개수 출력 책에서 구현된 코드 # 문자열 사용 class Solution: def hammingWeight(self, n: int) -> int: return bin(n).count('1') # 문자열 없이 구현 class Solution: def hammingWeight(self, n: int) -> int: count = 0 while n: # 1을 뺀 값과 AND 연산 횟수 측정 n &= n - 1 count += 1 return count 기억해야할 기법 내가 구현한 코드 # 문자열 사용 class Solution: def hammingWeight(self, n:..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 입력값이 UTF-8 문자열인지 검증 책에서 구현된 코드 class Solution: def validUtf8(self, data: List[int]) -> bool: # 문자 바이트 만큼 10으로 시작 판별 def check(size): for i in range(start + 1, start + size + 1): if i >= len(data) or (data[i] >> 6) != 0b10: return False return True start = 0 while start > 3) =..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 + / - 없이 정수의 덧셈 구현 책에서 구현된 코드 class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF INT_MAX = 0x7FFFFFFF # 합, 자릿수 처리 while b != 0: a, b = (a ^ b) & MASK, ((a & b) INT_MAX: a = ~(a ^ MASK) return a 기억해야할 기법 비트연산을 구현할 때 자리수가 미리 지정되어야함 내가 구현한 코드 class Solution: def getSum(self, a: int, b: int) -> int: cnt = 1023 mask = 0b1 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 두 수의 해밍 거리 계산 책에서 구현된 코드 class Solution: def hammingDistance(self, x: int, y: int) -> int: return bin(x ^ y).count('1') 기억해야할 기법 count 겹치지 않는 문자열을 포함하는 개수 출력 내가 구현한 코드 class Solution: def hammingDistance(self, x: int, y: int) -> int: return sum(map(int, bin(x ^ y)[2:])) char 비교연산보다 sum이 매우 약간 더 빠른가보다

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 단 하나의 수를 제외하고 모든 숫자가 2번씩 나올 때, 하나의 숫자 찾기 시간 복잡도는 linear, 공간 복잡도는 상수로 해결하기 책에서 구현된 코드 class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for num in nums: res ^= num return res 기억해야할 기법 XOR를 이용한 중복 확인 0과 XOR -> 숫자가 가진 특정 비트의 1만 1로 표시 = 자신과 같은 값 같은 값과 XOR -> 모든 비트가 같으므로 0 2번씩 등장하는 값들을 임의의 순서로 0과 XOR - 각 비트마다 1이 짝수번 등장 = 0으로..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 row / column 순서로 정렬된 2D 행렬에서 target 찾기 책에서 구현된 코드 # 첫 행의 맨 뒤에서 탐색 class Solution: def searchMatrix(self, matrix, target): # 예외 처리 if not matrix: return False # 첫 행의 맨 뒤 row = 0 col = len(matrix[0]) - 1 while row = 0: if target == matrix[row][col]: return True # 타겟이 작으면 왼쪽으로 elif target ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 합이 target이 되는 두 수의 인덱스 출력 책에서 구현된 코드 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: for k, v in enumerate(numbers): expected = target - v i = bisect.bisect_left(numbers, expected, k + 1) if i < len(numbers) and numbers[i] == expected: return k + 1, i + 1 기억해야할 기법 bisect로 lo, hi를 설정할 수 있음 내가 구현한 코드 # 이진 검색 cla..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 두 배열의 교집합 출력 책에서 구현된 코드 class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: result: Set = set() # 양쪽 모두 정렬 nums1.sort() nums2.sort() i = j = 0 # 투 포인터 우측으로 이동하며 일치 여부 판별 while i nums2[j]: j += 1 elif nums1[i] < nums2[j]: i += 1 else: result.add(nums1[i]) i +=..