효팍이의 프로그래밍

문제 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL 코드 """ fixme https://leetcode.com/problems/reverse-linked-list/ Q15. 역순 연결 리스트 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL """ class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def reverseListRecur(self, head: ListNode) -> ListNode: def re..

문자열 내장 함수 upper() 문자열을 대문자로 변경합니다. >>> string = 'abc' >>> string.upper() 'ABC' lower() 문자열을 소문자로 변경합니다. >>> string = 'ABC' >>> string.lower() 'abc' capitalize() 첫 문자만 대문자로 변경하고, 나머지 문자들은 소문자로 변경합니다. >>> string = 'aBC' >>> string.capitalize() 'Abc' splitlines() 개행 문자를 기준으로 쪼갠다. >>> string = 'IU is \nvery pretty.' >>> string.splitlines() ['IU is ', 'very pretty.'] join() 리스트를 문자열로 바꿀 때 사용한다. >>> l..

문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : height = [0,1,0,2,1,0,1,3,2,1,2,1] 출력 : 6 입력 : height = [4,2,0,3,2,5] 출력 : 9 코드 from typing import List class Solution: def trapTwoPointer(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(left_max, heig..

문제 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라. 입력 : "2 - 1 - 1" 출력 : [0, 2] 설명 ((2 - 1) - 1) = 0 (2 - (1 - 1)) = 2 입력 : "2 * 3 - 4 * 5" 출력 : [-34, -14, -10, -10, 10] 설명 (2 * (3 - (4 * 5))) = -34 ((2 * 3) - (4 * 5)) = -14 ((2 * (3 - 4)) * 5) = -10 (2 * ((3 - 4) * 5)) = -10 (((2 * 3) - 4) * 5) = 10 코드 """ fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/ fixme. Q84. 괄호를 삽입하는 여러 가지 방법..

문제 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. 입력 : S = "AD0BEC0DEBANC", T = "ABC" 출력 : "BANC" 코드 """ fixme. https://leetcode.com/problems/minimum-window-substring/ fixme. Q76. 부분 문자열이 포함된 최소 윈도우 fixme. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. fixme. 입력 : S = "AD0BEC0DEBANC", T = "ABC" fixme. 출력 : "BANC" """ import collections class Solution: def minWindowPointer(self, s: str, t..

문제 두 정수 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..

문제 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 입력 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..

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 다음과 같은 이진 트리가 주어졌을 때, 1 2 3 4 5 가장 긴 경로는 4 → 2 → 1 → 3 또는 5 → 2 → 1 → 3으로 3이다. 코드 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: longest: int = 0 def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(node: TreeNode) -> int: # 리프노드의 left, right 노드를 None으로 초기화하므로 거기까지..

문제 K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (u, v, w)는 각각 출발지, 도착지, 소요시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. 입력 times = [[2,1,1], [2,3,1], [3,4,1]], N = 4, K = 2 출력 2 코드 from typing import List import collections, heapq class Solution: def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append..

문제 입력 2, [[1,0]] 출력 True 입력 2, [[1,0],[0,1]] 출력 False 코드 visited 없을 때 from typing import List import collections class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = collections.defaultdict(list) for x, y in prerequisites: graph[x].append(y) traced = set() def dfs(i): if i in traced: return False traced.add(i) for y in graph[i]: if not dfs(y): ret..

문제 [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다. 입력 [["MUC", "LHR"], ["JFK", "MUC"], ["SF0", "SJC"], ["LHR", "SF0"]] 출력 ["JFK", "MUC", "SF0", "SJC"] 입력 [["JFK", "SF0"], ["JFK", "ATL"], ["SF0", "ATL"], ["ATL", "JFK"], ["ATL", "SF0"]] 출력 ["JFK", "ATL", "JFK", "SF0", "ATL", "SF0"] 코드 DFS from typing import List import collections class Solution: def findItinerary(s..

문제 서로 다른 정수를 입력 받아 가능한 모든 순열을 리턴하라. 입력 [1,2,3] 출력 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 코드 재귀 함수 from typing import List class Solution: def permute(self, nums: List[int]) -> List[List[int]]: results = [] prev_elements = [] def dfs(elements): if len(elements) == 0: results.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.remove(e) prev_elem..

문제 전체의 수 n을 입력받아 k개의 조합을 리턴하라. 입력 : n = 4, k = 2 출력 [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ] 코드 dfs from typing import List class Solution: def combine(self, n: int, k: int) -> List[List[int]]: results = [] def dfs(elements, start: int, k:int): if k == 0: results.append(elements[:]) for i in range(start, n+1): elements.append(i) dfs(elements, i+1, k-1) elements.pop() dfs([], 1, k) return res..

객체 복사 파이썬의 중요한 특징 중 하나는 모든 것이 객체라는 점이다. 심지어 숫자, 문자까지도 모두 객체다. 숫자, 문자가 리스트, 딕셔너리 같은 객체와의 차이점이라면 불변 객체라는 차이뿐이다. 그러다 보니 별도로 값을 복사하지 않는 한, 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다. 이 말은 참조가 가리키는 원래의 값을 변경하면 모든 참조, 즉 모든 변수의 값 또한 함께 변경된다는 말이기도 하다. 그렇다면 참조가 되지 않도록 값 자체를 복사하려면 어떻게 해야 할까? 가장 간단한 방법은 [:]로 처리하는 방법이다. >>> a = [1,2,3] >>> b = a >>> c = a[:] >>> id(a), id(b), id(c) (4362781552, 4362781552, 43615800..

전화 번호 문자 조합 문제 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. 입력 : "23" 출력 : ["ad","ae","af","bd","be","bf","cd","ce","cf"] 코드 from typing import List class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): if len(path) == len(digits): result.append(path) return for i in range(index, len(digits)): for j in dic[digits[i]]: dfs(i + 1, path + j) if not digits: r..

중첩함수 중첩 함수(Nested Function)란 함수 내에 위치한 또 다른 함수로, 바깥에 위치한 함수들과 달리 부모 함수의 변수를 자유롭게 읽을 수 있다는 장점이 있다. 중첩 함수가 부모 함수의 변수를 공유하는 예제는 다음과 같다. def outer_function(t: str): test: str = t def inner_function(): print(text) inner_function( outer_function("Hello!&#39;) ----- Hello! 여기서 outer_function()은 inner_functuion()을 호출했고, 아무런 파라미터도 남기지 않았지만 부모 함수의 text 변수를 자유롭게 읽어들여 그 값인 Hello!를 출력했다. 이처럼 매번 파라미터를 전달하지 않아..

파이썬에서 언팩킹과 팩킹 zip()의 파라미터는 1개가 될 수도 있고, 2개가 될 수도, 10개가 될 수도 있다. 밑의 실험을 보면 알 수 있다. >>> a = ['a1', 'a2'] >>> b = ['b1', 'b2'] >>> c = ['c1', 'c2'] >>> d = ['d1', 'd2'] >>> list(zip(a)) [('a1',), ('a2',)] >>>list(zip(a, b)) [('a1', 'b1'), ('a2', 'b2')] >>> list(zip(a, b, c)) [('a1', 'b1', 'c1'), ('a2', 'b2', 'c2')] 여기에는 아스테리스크(Asterisk) 혹은 흔히 별표라고 부르는 *를 활용한다. 파이썬에서 *는 언팩(Unpack)이다. 시퀀스 언패킹 연산자(Seq..

해시란? 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 충돌 아무리 좋은 해시 함수라도 밑의 그림과 같이 충돌은 발생하게 된다. 이 그림에서 윤아와 서현은 해시 값이 2로 같은 값이 되어 충돌이 발생했다. 이처럼 충돌이 발생할 경우 어떤 식으로 처리하게 되는지 살펴보자. 개별 체이닝 입력 값을 밑의 표와 같이 정해보자. 해시는 키를 해싱한 결과며, &#39;윤아&#39;와 &#39;서현&#39;을 해싱한 결과는 충돌한다고 가정한다. 이 표를 개별 체이닝(Separate Chaining) 방식으로 구현하면 밑의 그림과 같다. 해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 이 그림과 같이 연결 리스트로 연결하는 방식이다. 충돌이 발생한 &#39..

k개 정렬 리스트 병합 문제 k개의 정렬된 리스트를 1개의 정렬 리스트로 병합하라 입력 [1 → 4 → 5, 1 → 3 → 4, 2 → 6] 출력 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 코드 from typing import List import heapq class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: root = result = ListNode(None) heap = [] for i in range(len(lists)): if lists[i]: heapq.heappush(heap, ..

내부 함수 명명 규칙 내부에서 사용한다는 의미로 PEP8 명명 규칙 기준에 따라 밑줄(_) 하나로 시작하도록 메소드 명을 정한다. class MycircularDeque: """ skip.... """ def _add(self, node: ListNode, new: ListNode): n = node.right node.right = new new.left, new.right = node, n n.left = new def insertFront(self, value: int) -> bool: if self.len == self.k: return False self.len += 1 self._add(self.head, ListNode(value)) return True 출처 파이썬 알고리즘 인터뷰 (글 :..

중복 문자 제거 문제 중복된 문자를 제외하고 사전식 순서로 나열하라. 예제1 입력 "bcabc", 출력 "abc" 예제2 입력 "cbacdcbc", 출력 "acdb" 코드 정답 # 재귀 class Solution: def removeDuplicateLetters(self, s: str) -> str: # 집합으로 정렬 for char in sorted(set(s)): suffix = s[s.index(char):] # 전체 집합과 접미사 집합이 일치할때 분리 진행 if set(s) == set(suffix): return char + self.removeDuplicateLetters(suffix.replace(char, '')) return '' # 스택 import collections class So..

연결 리스트를 이용한 스택 ADT 구현 코드 class Node: def __init__(self, item, next): self.item = item self.next = next class Stack: def __init__(self): self.last = None def push(self, item): self.last = Node(item, self.last) def pop(self): item = self.last.item self.last = self.last.next return item stack = Stack() stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) 헷갈린 부분 처음에 Stack 클래스가 만들어지면..