Scribbling

굉장히 전형적인 DP 문제 def solution(triangle): h = len(triangle) dp = [[] for _ in range(h)] dp[0].append(triangle[0][0]) for i in range(1, h): dp[i].append(dp[i-1][0] + triangle[i][0]) for j in range(1, i): dp[i].append(max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]) dp[i].append(dp[i-1][-1] + triangle[i][-1]) return max(dp[h-1])

난이도가 높지는 않은 문제. N을 1개씩 늘려가면서 완전탐색하되, number가 있는지 확인한다. 예컨대... 5가 네개인 경우를 완전탐색하려면, (5, 5, 5, 5) (5) + (5, 5, 5) (5, 5) + (5, 5) (5, 5, 5) + (5) 위의 모든 케이스를 다 따져 주면 된다. 여기서 +는 더하라는 의미가 아니라, 왼쪽에서 발생되는 모든 케이스와 오른쪽에서 발생되는 모든 케이스를 조합하는 모든 케이스를 생성하라는 의미이다. def solution(N, number): if number == N: return 1 dp = [[] for _ in range(9)] dp[1] = [N] for i in range(2, 9): dp[i].append(int(str(N)*i)) for j in ..

# Definition for a binary tree node. # 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, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: return self.builder(inorder, postorder) def builder(self, inorder, postorder): if not inorder: return None head = TreeNode(val=postor..

route들이 최대한 잘 겹치게 만드는 것이 목표인 문제이다. 이런 문제는 input의 순서를 강제하는 것이 큰 도움이 되는 경우가 많은데, 여기서는 routes를 사전에 정렬하는 것이 이에 해당된다. 정렬이 필요한 이유에 대해서는 생각해 볼 필요가 있는데, 이 문제에서는 group간 겹치는 문제를 회피하기 위해서이다. 아래 예제를 보자. [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] groups = [[-20, -15] 정렬하면, [[-20, -15], [-18, -13], [-14, -5], [-5, -3]] 1) [-18, -13] 처리 group 내의 [-20, -15]와 겹치므로 group[0]를 [-20, -15]와 [-18, -13]의 교집합인 [-18, -15]..

섬을 연결하는 최소 비용을 구하는 문제로, 최소 신장 트리 문제에 해당된다. 자연스럽게 크루스칼 알고리즘을 떠올릴 수 있다. 최소 신장 트리 혹은 크루스칼 알고리즘이 궁금하다면, 아래 링크로! (간단히 말하자면, 크루스칼 알고리즘은 비용이 가장 적게 드는 edge부터 연결시켜가는 알고리즘이다) https://focalpoint.tistory.com/15 신장 트리, 최소 신장 트리, Kruskal Algorithm 1. 신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다. 2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리 3. Kruskal Algorithm: 최소 신장 트리를 찾는 알 focalpoint.tistory.com def solutio..

몸무게로 줄을 세우고, 돼지와 홀쭉이를 매칭시켜준다. def solution(people, limit): answer = 0 people.sort(reverse=True) i, j = 0, len(people) - 1 while i

def solution(number, k): stack = [] for num in number: while stack and stack[-1] 0: k -= 1 stack.pop() stack.append(num) return ''.join(stack[:len(stack)-k])

재귀로 풀어주자 # Definition for a binary tree node. # 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]) -> Optional[TreeNode]: return self.builder(preorder, inorder) def builder(self, preorder, inorder): if not preorder: return None head = TreeNode(val..

102번 문제를 풀면 하나 더 주는 공짜 문제. 밑의 코드만 추가해준다. for i in range(len(ret)): if i % 2 == 1: ret[i].reverse() https://focalpoint.tistory.com/128 LeetCode: 102. Binary Tree Level Order Traversal - 시바견의 끄적임 BFS하면서 기록해준다. from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # s.. focalpoint...

BFS하면서 기록해준다. from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] ret = [] q = deque() q.append((root, 0)) while q: cur_node, cur_level = q.popleft() ..