거누의 개발노트

문제 정수 배열에서 (첫번째 최대값-1)*(두번째 최대값-1)을 해주는 프로그램을 작성. 입력 Input: nums = [3,4,5,2] 출력 Output: 12 # (5-1)*(4-1) 작성한 코드1 def maxProduct(nums: List[int]) -> int: n = sorted(nums, reverse=True) return (n[0]-1)*(n[1]-1) 작성한 코드2 def maxProduct2(nums: List[int]) -> int: h = heapq.nlargest(2, nums) return (h[0] - 1) * (h[1] - 1) list를 sort 할 때 는 시간 복잡도가 O(NlogN) 이고, heapq는 push, pop 할 때 O(logN) 이여서 힙이 빠르다는걸 알..

문제 이진 트리를 직렬화 및 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방식에는 제한이 없습니다. 이진 트리를 문자열로 직렬화할 수 있고 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인하기만 하면 됩니다. 입력 Input: root = [1,2,3,null,null,4,5] 출력 Output: [1,2,3,null,null,4,5] 작성한 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): q..

문제 BST에서 노드의 값이 val과 같은 노드를 찾고 해당 노드의 하위 트리를 반환하는 코드를 작성. 그러한 노드가 존재하지 않으면 null을 반환 합니다. 입력 Input: root = [4,2,7,1,3], val = 2 출력 Output: [2,1,3] 작성한 코드1 # 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 searchBST(self, root: Optional[TreeNode], val: int) -> Opt..

문제 이진 탐색 트리의 노드와 두 개의 정수 low와 high 가 주어지면 포함 범위 에 있는 값을 가진 모든 노드의 값 합계를 반환하는 코드를 구현하시오. 입력 Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 출력 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32. 작성한 코드1 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.ri..

문제 이진 트리가 주어지면 root트리를 반전 하고 루트 를 반환합니다. 입력 root = [4,2,7,1,3,6,9] 출력 [4,7,2,9,6,3,1] 작성한 코드 # 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 def list_to_tree(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value is not None: parent = TreeNode(value) parent.left = list_to_tree..

문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 Input: root = [5,4,5,1,1,5] 출력 Output: 2 처음에 지나온 노드의 개수 인줄 알고 엥? 왜 2개이지 한참 고민했다. 출력을 다시 생각해보니 간선의 개수였다... 아무튼 이 문제도 처음 접근하는 나에게는 어려운 친구들이었다. 역시 그냥은 잘 안 풀려서 책에 도움을 받았다. 뭐 어떤가..잘 이해해서 내걸로 만들면되지! def longestUnivaluePath(root) -> int: rtn = [0] def dfs(node:TreeNode): if node is None: return 0 #왼쪽 노드 값도 구해와 줄래? left = dfs(node.left) #오른쪽 노드 값도 구해와 줄래? right = dfs(node.r..

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 입력 TreeNode [1,2,3,4,5] 출력 3 먼저 내 코드에서 테스트 해보려면 배열을 리스트로 만드는 과정이 필요했다. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def make_tree_by(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value == None: return parent = TreeNode(value) parent.left = make_tree_by(lst, 2 * idx + 1) ..

문제 [문제 설명] △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다. 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가..