hyunkookim 님의 블로그

729. My Calendar I https://youtu.be/fIxck3tlId4 class MyCalendar: def __init__(self): # 예약된 일정들을 저장할 리스트 (각 요소는 (start, end) 튜플) self.events = [] def book(self, startTime: int, endTime: int) -> bool: # 기존에 예약된 모든 일정과 하나씩 비교하면서 겹치는지 확인 for start, end in self.events: # 겹치는 조건: 두 구간이 공통 범위를 가질 때 # 즉, [startTime, endTime)와 [start, end)가 겹치면 Fal..

2407. Longest Increasing Subsequence II  증가하는 서브시퀀스 구해서, 두개 차이가  Longest Increasing Subsequence II (LeetCode 2407)nums: 정수 배열k: 최대 차이값조건:엄격히 증가하는(subsequence) 부분 수열이어야 함 (즉, 이전 값보다 무조건 커야 함)인접한 값들의 차이 ≤ k 이어야 함 (nums[j] - nums[i] ≤ k where i ➡️ 이런 조건을 만족하는 가장 긴 subsequence의 길이를 구하는 문제입니다.  "두 숫자 간 차이가 k 이하인 가장 긴 증가 부분 수열의 길이"를 세그먼트 트리를 사용해 빠르게 구하는 것# 세그먼트 트리 클래스 정의class SegmentTree: def __ini..

406. Queue Reconstruction by Height LeetCode 406번 문제 "Queue Reconstruction by Height" 는 사람들의 [키, 앞에 있어야 할 사람 수] 조건을 바탕으로 원래의 줄(큐) 을 복원하는 문제예요.✅ 문제 요약각 사람 people[i] = [hi, ki]는 다음을 의미해요:hi: 이 사람의 키ki: 이 사람보다 키가 크거나 같은 사람이 앞에 정확히 ki명 있어야 한다 ✅ 핵심 아이디어 (그리디 + 정렬 + 삽입)키가 큰 사람부터 정렬 (내림차순)이유: 키가 큰 사람이 먼저 자리를 차지해야 작은 사람이 영향을 안 받음같은 키일 경우 ki 오름차순 정렬이유: 같은 키라면, ki가 작을수록 먼저 위치해야 조건이 맞음정렬된 순서대로 ki 위치에 삽입삽입 ..

307. Range Sum Query - Mutable 이 문제는 세그먼트 트리로 아주 잘 풀리는 전형적인 문제예요.구간 합을 빠르게 구하면서 값도 실시간으로 바꾸는 기능이 필요하기 때문이에요. 아래는 NumArray 클래스를 세그먼트 트리를 이용해 구현한 코드예요.  class SegmentTree: def __init__(self, total, L, R): # 현재 노드가 담당하는 구간 [L, R]의 합을 저장 self.sum = total # 왼쪽 자식 노드 self.left = None # 오른쪽 자식 노드 self.right = None # 구간의 왼쪽 경계 (시작 인덱스) self.L = ..

721. Accounts Merge 이 문제는 Union-Find(Disjoint Set) 을 사용하는 대표적인 그래프 문제입니다.각 이메일을 노드로 보고, 같은 사람의 이메일끼리 연결(merge) 해주는 방식입니다.✅ 문제 핵심 정리accounts[i][0]: 이름 (예: "John")accounts[i][1:]: 이메일 주소들공통 이메일이 있으면 같은 사람 → 이메일들을 하나의 집합으로 merge결과는 [이름, 정렬된 이메일 목록] 형식으로 반환✅ 전략Union-Find 구조 생성이메일 간 연결을 Union-Find로 묶기각 이메일의 루트를 기준으로 그룹핑이름을 이메일과 매핑해 최종 결과 구성✅ 전체 코드 (풀 구현 + 설명 주석)class Solution: def accountsMerge(se..

745. Prefix and Suffix Search 문제 LeetCode 745. Prefix and Suffix Search를 해결하는 Trie 기반 풀이를 제공해드릴게요.접두사(prefix)와 접미사(suffix)를 동시에 만족하는 단어를 빠르게 찾기 위해, 특수한 방식으로 Trie를 구성합니다.✅ 핵심 아이디어:모든 단어에 대해 "suffix#prefix" 형태로 key를 만들어서 Trie에 저장합니다.예시단어 "apple" → "e#apple", "le#apple", ..., "#apple" 등으로 여러 key 생성검색할 때 "suff#pref" 형식으로 Trie에서 찾기✅ 완성된 코드 (딕셔너리 기반 Trie 사용)class TrieNode: def __init__(self): ..

876. Middle of the Linked List # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: """ - slow는 한 칸씩 - fast는 두 칸씩 이동 - fast가 끝에 도달하면, slow는 중간에 도달 """ slow = fast = head ..

724. Find Pivot Index 1) Prefix Sums 누적합 이용 풀이 방법class Solution: def pivotIndex(self, nums: List[int]) -> int: # 자신을 제외한 왼쪽 합 == 오른쪽 합이 되는 pivot index를 찾는 문제 total = 0 # 전체 합을 계산하기 위한 변수 PrefixSum = [] # 0번 인덱스부터의 누적합 배열 for n in nums: total += n # 현재까지의 누적합을 계산 PrefixSum.append(total) # 누적합을 배열..

304. Range Sum Query 2D - Immutable class NumMatrix: def __init__(self, matrix: List[List[int]]): self.matrix = matrix rows, cols = len(matrix), len(matrix[0]) # prefixSums[i][j]는 (0,0)부터 (i,j)까지의 누적합을 저장 self.prefixSums = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): top = self.prefixSums[r-1][c] if ..

303. Range Sum Query - Immutable class NumArray: def __init__(self, nums: List[int]): self.nums = nums self.area = [0]*len(nums) self.area[0] = nums[0] # 첫 원소는 그대로 할당 for i in range(1, len(nums)): self.area[i] = self.area[i - 1] + nums[i] # 누적합 계산 def sumRange(self, left: int, right: int) -> int: if left == 0: return self.area[righ..