pythaac의 개발노트

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