문제 두 정수 a와 b의 합을 구하라. +또는 -연산자는 사용할 수 없다. 입력 a = 1, b = 2 출력 3 입력 a = -2, b = 3 출력 1 코드 전가산기 구현 class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF INT_MAX = 0x7FFFFFFF a_bin = bin(a & MASK)[2:].zfill(32) b_bin = bin(b & MASK)[2:].zfill(32) result = [] carry = 0 sum = 0 for i in range(32): A = int(a_bin[31 - i]) B = int(b_bin[31 - i]) # 전가산기 구현 Q1 = A & B Q2 = A ^ B Q3 = Q..
파이썬의 진법 표현 파이썬이 이진수(binary), 십진수(decimal), 16진수(hexadecimal)를 저장하고 표현하는 방법을 살펴보자. 먼저 이진수와 십진수는 다음과 같이 각각 bin()과 int()를 사용해서 서로 변환할 수 있다. >>> bin(87) '0b1010111' >>> int('0b1010111', 2) 87 bin()을 사용하면 이진수가 문자형 0b1010111으로 리턴된다. 반면 int()을 사용하면, 문자형인 이진수가 십진수 숫자 정수형 87로 리턴된다. 이진수임을 의미하는 접두사(Prefix) 0b는 다음과 같이 생략도 가능하다. >>> int('1010111', 2) 87 bin()을 사용해 변수에 값을 할당하면 다음과 같이 문자형이 된다. >>> a = bin(87) ..
any()와 all() 함수 >>> any([True, False, False]) True any()는 포함된 값 중 어느 하나가 참이라면 항상 참으로 출력한다. 논리 연산의 OR과 비슷하다. 반면 all()이라는 함수는 모든 값이 참이어야 True를 출력한다. >>> all([True, False, False]) False >>> all([True, True, True]) True 이처럼 all()은 논리 연산의 AND와 유사하다. 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]
문제 연결 리스트를 삽입정렬로 정렬하라. 코드 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def insertionSortList(self, head: ListNode) -> ListNode: cur = parent = ListNode(0) while head: while cur.next and cur.next.val head.val: cur = parent return parent.ne..
파이썬 콤마(,) 연산자 a += b, 연산자와 변수 뒤에 콤마(,)가 붙어 있다. 이렇게 하면 어떻게 동작할까? 먼저 콤마(,)가 없는 기본적인 추가 연산을 해보자. >>> a = [1] >>> b = [2, 3] >>> a += b >>> a [1, 2, 3] 단순히 +-를 했을 때는 요소를 이어붙인다. 행렬의 연결 연산과 동일하다. 이번에는 콤마를 넣어보자. >>> a = [1] >>> b = [2, 3] >>> a += b, >>> a [1, [2, 3]] 이렇게 중첩 리스트가 된다. 콤마는 중첩 리스트로 만들어주는 역할을 하며, 대괄호 []를 부여한 것과 동일한 역할을 한다. >>> a += [b] >>> a [1, [2, 3]] 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [..
@staticmethod 데코레이터 @staticmethod는 자바의 메소드 static 선언과도 비슷한데, 이렇게 정의한 메소드는 클래스와 독립적인 함수로서의 의미를 강하게 갖는다. 파라미터에도 항상 따라붙는 self가 빠져 있고, 함수 자체가 별도의 자료형으로 선언되어 있다. class CLASS: def a(self): pass @staticmethod def b(): pass 이 같은 클래스가 선언되어 있을 때, 함수 a()와 b()의 타입을 출력해보자. >>> type(CLASS.a), type(CLASS.b) (, ) 클래스를 생성하지 않고 바깥에서 직접 호출했을 때 타입은 이처럼 둘 다 함수가 된다. >>> cls = CLASS() >>> type(cls.a), type(cls.b) (, )..
문제 연결 리스트를 O(n*logn)에 정렬하라. 입력 4 → 2 → 1 → 3 출력 1 → 2 → 3 → 4 코드 병합 정렬 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2 def sortList(self, head: ListNode) -> ListNode: if n..
문제 단어 리스트에서 words[i] + words[j]가 펠린드롬이 되는 모든 인덱스 조합(i, j)를 구하라. 입력 ["abcd","dcba","lls","s","sssll"] 출력 [[0,1],[1,0],[3,2],[2,4]] ["dcbaabcd","abcddcba","slls","llssssll"]이 팰린드롬이다. 입력 ["bat","tab","cat"] 출력 [[0,1],[1,0]] ["battab","tabbat"]이 팰린드롬이다. 코드 import collections from typing import List # 트라이 저장용 노드. class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) se..
문제 트리의 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라. 전위 순회 결과: [3,9,20,15,7] 중위 순회 결과: [9,3,15,20,7] 결과는 밑의 그림과 같은 이진 트리가 된다. 코드 from typing import List class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if inorder: # 전위 순회 결과는 중위 순회 분할 인덱스 index = ino..
문제 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 입력 root = [4, 2, 6, 1, 3, null, null] 출력 1 노드 3과 노드 4의 값의 차이는 1이다. 입력 root = [10, 4, 15, 1, 8, null, null] 출력 2 이 경우 노드 간 값의 차이가 가장 작은 노드는 8과 10이다. 1과 4는 거리의 차이가 3이고, 4와 8은 차이가 4이지만 8과 10의 차이는 2로 최솟값이다. 코드 재귀 구조로 중위 순회 import sys class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solut..
문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 2 입력 출력 2 코드 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode): def dfs(node: TreeNode): if node is None: return 0 left = dfs(node.left) right = dfs(node.right) if node.left and node.left.val == node.val: left += 1 else: l..