Tech for good

# 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) 알고리즘을 사용할 수 있다.완전 이진 트리는 모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽부터 채워진 상태이다.즉 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 같다면, 트리가 완전하게 채워진 형태라는 뜻이다. 다시 말해, 전체 노드 개수 == 꽉 찬 부분(완전한 트리) + 마지막 레벨의 노드 개수이다.이렇게 노드가 모두 꽉 차 있는 완전 트리의 경우, 개수를 구하는 공식은 아래와 같다. ..

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

class Solution: def countGoodSubstrings(s: str) -> int: count = 0 for i in range(len(s) - 2): # 길이가 3인 모든 부분 문자열을 검사 substring = s[i:i+3] # 길이 3의 부분 문자열 추출 if len(set(substring)) == 3: # 중복 문자가 없는지 확인 count += 1 return countset() => 중복을 허용하지 않는 집합(set) 자료형을 생성하는 함수중복 제거: 리스트나 문자열 등의 중복된 요소를 자동으로 제거.순서 없음: 요소의 순서가 보장되지 않음.빠른 멤버십 테스트 ..

https://neetcode.io/problems/permutation-string NeetCode neetcode.io🛠 해결 전략이 문제는 슬라이딩 윈도우(Sliding Window) + 해시맵(딕셔너리) 활용으로 O(n)에 해결할 수 있다.s1의 모든 문자 빈도 수를 계산 (char_count_s1).s2에서 길이가 len(s1)인 윈도우를 이동하며 같은 빈도 수를 갖는지 비교 (char_count_window).첫 번째 윈도우 확인 후 한 칸씩 이동하며 검사만약 동일한 빈도 수를 가지는 구간이 있다면 True 반환.class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: n, m = len(s1), len(s2)..

🔍 슬라이딩 윈도우(Sliding Window)배열에서 부분 합을 효율적으로 계산하는 기법매번 전체 합을 다시 계산하지 않고, 최초 윈도우의 합을 미리 계산해둔 후 기존 윈도우의 값을 조금씩 변경하면서 업데이트한다.즉, 현재 합에서 빠질 값과 추가할 값만 업데이트하면 O(1) 시간에 갱신이 가능한 효율적 알고리즘이다! class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: n = len(code) # 원래 코드 배열의 길이 # k가 0이면 모든 원소를 0으로 변경 if k == 0: return [0] * n # Extend..

https://neetcode.io/problems/longest-repeating-substring-with-replacement NeetCode neetcode.io🛠 해결 방법슬라이딩 윈도우를 사용하여 left와 right 두 개의 포인터로 윈도우 크기를 조정한다.윈도우 내에서 가장 많이 등장한 문자를 찾고, 나머지 문자들을 k번 변경할 수 있는지 확인한다.윈도우 크기에서 가장 많이 등장한 문자 개수를 제외한 나머지 문자가 k보다 크면 left 포인터를 이동하여 윈도우를 줄인다.최대 윈도우 크기를 갱신하면서 탐색을 진행한다.class Solution: def characterReplacement(self, s: str, k: int) -> int: left = 0 m..

// calories = [1,2,3,4,5]// k = 2// lower = 5// upper = 6// 1st: (1,2) = 3 -1// 2nd: (2,3) = 5 -> 0슬라이딩 윈도우 접근법:슬라이딩 윈도우를 사용하면 매번 k 길이의 구간을 합산하는 대신, 윈도우를 한 칸씩 이동하며 기존 합에서 가장 왼쪽 값을 빼고, 새롭게 들어온 값을 더하는 방식으로 효율적으로 합계를 구할 수 있다.시간 복잡도는 O(n)으로, calories 길이가 최대 10^5까지 가능하므로 효율적으로 동작한다.class Solution: def dietPlanPerformance(self, calories: List[int], k: int, lower:int, upper: int) -> int: points = ..