거누의 개발노트

문제 정수 배열에서 (첫번째 최대값-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) 이여서 힙이 빠르다는걸 알..

이진 탐색 트리란? 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가진다. 평균적으로 탐색의 시간복잡도는 O(logN), 치우친(skewed) 경우 O(n) 따라서 균형이 중요하다. 아래 그림에서 균형잡힌 경우와 치우친 경우를 확인할 수 있다. 이진 트리의 검색, 삽입, 삭제 검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 ..

문제 이진 트리를 직렬화 및 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방식에는 제한이 없습니다. 이진 트리를 문자열로 직렬화할 수 있고 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인하기만 하면 됩니다. 입력 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..

트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 트리구조는 위 그림에서 보는 것 처럼 폴더 구조와 같습니다. 이진 트리 이진 트리는 최대 두 개의 자식을 가집니다. ( 0, 1, 2 ) 완전 이진 트리 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있습니다. 마지막 레벨은 꽉 차 있지 않아도 되지만, ..

문제 이진 트리가 주어지면 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..