pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 문자열 s에 대해 k개를 변경하여 만들 수 있는 가장 긴 반복문자열의 길이 출력 책에서 구현된 코드 class Solution: def characterReplacement(self, s: str, k: int) -> int: left = right = 0 counts = collections.Counter() for right in range(1, len(s) + 1): counts[s[right - 1]] += 1 # 가장 흔하게 등장하는 문자 탐색 max_char_n = counts.most_common(1)[0][1] # k 초과시 왼쪽 포인터 이동 if right - left - max_char_n..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 t의 모든 문자, 개수가 포함된 s의 최소 윈도우 출력 책에서 구현된 코드 import collections class Solution: def minWindow(self, s: str, t: str) -> str: need = collections.Counter(t) missing = len(t) left = start = end = 0 # 오른쪽 포인터 이동 for right, char in enumerate(s, 1): missing -= need[char] > 0 need[char] -= 1 # 필요 문자가 0이면 왼쪽 포인터 이동 판단 if missing == 0: while left < right..

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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 부울 대수 (Boolean Algebra) true / false의 2개 값으로 논리 연산을 정의 부울 연산자 NOT AND OR XOR 비트 연산자 & | ^ ~ >> 0b0110을 기대 - 결과가 -0b1010 (NOT연산으로 인해 보이지 않는 비트들까지 1로 변경됨 - 0b0000...0101 ^ 0b1111...0011 -> 0b1111...0110 MASK를 이용해 원하는 비트수 만큼 자르기 - MASK = 0b1111 - bin(0b0101 ^ ~0b1100 & MASK)