hyunkookim 님의 블로그

✅ 순열 (Permutation) 요약 정리:정의:주어진 원소들을 모두 사용하여, 순서를 고려해 나열하는 것.예시:{1, 2, 3}의 순열 →[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]총 3! = 6가지순열 vs 조합  구분 순열 (Permutation) 조합 (Combination) 순서중요함중요하지 않음원소 사용모두 사용함일부만 사용할 수도 있음예시(1,2,3), (1,3,2) 등{1,2}, {2,3} 등💡 수학 공식:n개의 서로 다른 원소를 모두 사용한 순열의 개수:n! (팩토리얼)예: 3! = 3 × 2 × 1 = 6✅ 재귀 방식 permutationsRecursive(nums)# 시간 복잡도: O(n^2 * n!)def permutation..

480. Sliding Window Median heapq을 사용해 Two Heaps 방식으로 구현한 것입니다.앞서 봤던 방식과 비슷하지만,좀 더 간결하게 balance 변수로 크기 조정을 처리한 형태입니다. import heapqfrom collections import defaultdictfrom typing import Listclass Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: small, large = [], [] # small: 최대 힙 (음수 저장), large: 최소 힙 d = defaultdict(int) # 삭제 예약 딕셔..

145. Binary Tree Postorder Traversal 재귀 방법# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 후위 순회: 왼쪽 -> 오른쪽 -> 자신 if not root: return [] # 트리가 비어..

144. Binary Tree Preorder Traversal  재귀 방식 # 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 전위 순회(preorder traversal): 자신 -> 왼쪽 -> 오른쪽 res = [] def dfs..

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