효팍이의 프로그래밍

문제 당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라. 입력 : [1, 2, 3, 1] 출력: 4 설명 첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4 입력 : [2, 7, 9, 3, 1] 출력 : 12 설명 첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다. 코드 """ fixme. https://leetcode.com/problems/house-robber/ fixme. Q88. 집도둑 fixme. 당신은 전문털이범이다. 어느 집에서..

문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..

문제 연결 리스트를 삽입정렬로 정렬하라. 코드 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..

문제 연결 리스트를 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..

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 다음과 같은 이진 트리가 주어졌을 때, 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..

전화 번호 문자 조합 문제 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..

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, ..