Tech for good

class Solution: def maxProduct(self, nums: List[int]) -> int: # Convert to max-heap by pushing negative values max_heap = [-num for num in nums] heapq.heapify(max_heap) # Pop the two largest values first_max = -heapq.heappop(max_heap) second_max = -heapq.heappop(max_heap) return (first_max - 1) * (second_max - 1)

https://neetcode.io/problems/k-closest-points-to-origin NeetCode neetcode.io큐(Queue)는 선입선출(First In, First Out, FIFO)의 자료 구조로, 먼저 들어온 데이터가 먼저 나간다. 하지만 우선순위가 있는 작업에서는 큐의 기본 원칙을 따르지 않을 때가 있다. 우선순위 큐(Priority Queue) 는 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료 구조다.힙( Heap)이란?힙(Heap)은 우선순위 큐를 구현하기 위한 자료 구조다. 힙의 뜻을 살펴보면, "쌓아 올린 더미" 또는 "쌓아 올리다"라는 의미를 가진다. 힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한며,..

# 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 = rightclass Solution: def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: # 주어진 트리의 리프 노드(leaf node) 값을 순서대로 가져오는 함수 def get_leaf_sequence(root: Optional[TreeNode]) -> ..

https://neetcode.io/problems/binary-tree-right-side-view NeetCode neetcode.io첫번째 풀이 방법: BFS - Level Order Traversal각 레벨에서 가장 오른쪽에 있는 노드의 값만 저장하면 된다.BFS(너비 우선 탐색, Queue;)을 이용하여 레벨별 탐색을 수행한다.매 레벨의 마지막 노드 값을 결과 리스트에 추가한다.# 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 =..

# 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 = rightclass Solution: def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]: if not root1: # root1이 None이면 root2 반환 return root2 if not root2: # ro..

완전 이진 트리(Complete Binary Tree)의 노드 개수를 세는 문제이며, 최적화된 방법을 사용하여 O(n)보다 빠른 시간 복잡도로 해결해야 한다.완전 이진 트리는 왼쪽부터 차곡차곡 채워지는 성질이 있기 때문에, 일반적인 트리 탐색(O(n))이 아니라, 이진 탐색을 활용한 O(log n * log n) 알고리즘을 사용할 수 있다.완전 이진 트리는 모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽부터 채워진 상태이다.즉 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 같다면, 트리가 완전하게 채워진 형태라는 뜻이다. 다시 말해, 전체 노드 개수 == 꽉 찬 부분(완전한 트리) + 마지막 레벨의 노드 개수이다.이렇게 노드가 모두 꽉 차 있는 완전 트리의 경우, 개수를 구하는 공식은 아래와 같다. ..

https://neetcode.io/problems/level-order-traversal-of-binary-tree NeetCode neetcode.io Level-Order Traversal이란?Level-order traversal(레벨 순회) 는 트리(Tree) 를 탐색하는 방법 중 하나로, BFS(너비 우선 탐색, Breadth-First Search) 를 기반으로 한다.트리 탐색 (Tree > Traversal)의 대표적인 방법트리에서 노드를 방문하는 순서에 따라 탐색 방식이 여러 가지가 있다.DFS (깊이 우선 탐색, Depth-First Search)루트에서 시작해서 최대한 깊이 내려간 후 백트래킹(되돌아옴).구현 방법:전위 순회 (Preorder): Root → Left → Right중위..

mode: 최빈값🔹 Binary Search Tree(이진 탐색 트리, BST)란? 이진 트리의 한 종류이며, 노드의 배치에 특정한 규칙이 적용된다:왼쪽 서브트리의 모든 값은 현재 노드보다 작아야 한다.오른쪽 서브트리의 모든 값은 현재 노드보다 커야 한다.이 규칙 덕분에 탐색(검색), 삽입, 삭제 등의 연산이 효율적(평균 O(log n))으로 수행된다.  🔹 중위 순회(In-order Traversal)란?이진 탐색 트리(BST)에서 중위 순회(In-order Traversal) 를 수행하면 값이 오름차순(ascending order)으로 정렬된 순서로 방문된다.🌟 중위 순회 순서왼쪽 서브트리 탐색현재 노드 방문오른쪽 서브트리 탐색🔹 예제 트리아래와 같은 BST가 있다고 가정해보자. ..

https://neetcode.io/problems/lowest-common-ancestor-in-binary-search-tree NeetCode neetcode.io공통 조상 찾기!🔹 BST(Binary Search Tree)의 특징 활용BST(이진탐색트리)에서는 왼쪽 서브트리의 모든 값이 루트보다 작고, 오른쪽 서브트리의 모든 값이 루트보다 큽니다.따라서, LCA를 찾는 과정에서 다음 규칙을 사용할 수 있습니다.p.val과 q.val이 모두 현재 노드보다 작으면, LCA는 왼쪽 서브트리에 있음.p.val과 q.val이 모두 현재 노드보다 크면, LCA는 오른쪽 서브트리에 있음.p.val과 q.val이 현재 노드 양쪽에 걸쳐 있다면, 현재 노드가 LCA임.# Definition for a binar..

# 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 = rightclass Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 total = 0 # 왼쪽 자식이 리프 노드라면 값 추가 if root.left and not root.left.l..