hyunkookim 님의 블로그

✅ 1. 최소 신장 트리(Minimum Spanning Tree)란?정의: 주어진 무방향 연결 그래프에서 모든 정점들을 연결하면서 가중치의 합이 최소가 되는 트리 구조의 부분 그래프.조건모든 정점이 연결되어 있어야 함.사이클(순환)은 없어야 함.여러 개의 MST가 존재할 수도 있음.📌 기본 개념Undirected Graph (무방향 그래프)모든 노드가 연결되도록 (Connected)전체 간선의 가중치 합이 최소가 되도록 (Minimum Total Cost)노드가 n개라면 MST는 항상 n - 1개의 간선만 포함→ 그래서 사이클이 생기지 않음어느 노드에서 시작해도 결과는 동일한 MST 완성 가능✅ 2. Prim's Algorithm이란? (프림 알고리즘)핵심 아이디어: 하나의 정점에서 시작해서, 가장 작..

✅ 1. Dijkstra 알고리즘이란?가중치가 있는 그래프에서 **최단 경로(가장 비용이 적은 경로)**를 구할 때 사용하는 알고리즘이에요.**BFS(너비 우선 탐색)**은 모든 간선의 가중치가 1일 때만 최단 경로를 찾을 수 있어요. 하지만 Dijkstra는 가중치가 다를 때도 최단 경로를 보장해줘요.✅ 2. 왜 BFS로는 안 될까?예: edges = [[A,B], [A,C], [B,D], [C,B], [C,D], [C,E], [D,E]]이건 가중치 없는 그래프라서 BFS로 A → D 최단 경로를 구할 수 있어요.하지만 가중치가 달라지면 BFS는 "몇 개의 노드를 지나느냐"만 고려하기 때문에 최단 경로가 아닐 수 있어요.✅ 3. Dijkstra 알고리즘의 핵심 원리**Greedy 알고리즘(탐욕 알고리즘..

✅ 개념 정리: Combination (조합)조합(combination) = 특정 개수(k) 만큼만 고른 부분집합순서 상관 없음[1, 2] 와 [2, 1] → 같은 조합조건: 집합에서 k개의 원소만 선택📌 예시n = 5, k = 2 → [1, 2, 3, 4, 5] 중에서 2개씩 고르는 조합결과 (총 10개):[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]💡 해결 방법 2가지1. 백트래킹 (Backtracking) – 직접 조합을 구성 ✅ combinations(n, k) – DFS + 백트래킹 방식 (브랜치 두 갈래로 분기)  # Given n numbers (1 - n), return all possible..

✅ 부분집합이란?Set A가 Set B의 부분집합이라는 것은 → A에 있는 모든 원소가 B에도 있어야 함.기호로는 A ⊆ B 로 씀.📌 중요한 성질모든 집합은 자기 자신의 부분집합이다.예: A ⊆ A**공집합(∅)**은 모든 집합의 부분집합이다.예: ∅ ⊆ A (어떤 A라도)원소의 순서는 중요하지 않음.예: {1,2,3}과 {3,1,2}는 같은 집합.원소는 중복될 수 없음.예: {1,1,2}는 {1,2}와 같은 집합으로 본다.✔ 예시 복습A = {1,2,3,4,5}, B = {5,2,1} → ✅ B는 A의 부분집합B = {2,5,1} → ✅ 여전히 부분집합 (순서 상관 없음)C = {9,10,11,12}, D = {6,9,10} → ❌ D는 C의 부분집합 아님 (6이 C에 없음)✅ 부분집합이란?n개의 ..

중간값(median)을 빨리 구하기 위해서 2개의 heap 을 만들고small heap 은 max heap 으로, large heap 은 min heap 으로 만들면small heap 의 최대값과 large heap 의 최소값을 비교해서,median 값을 빨리 계산할 수 있음 그런데, 두개 heap 의 사이즈 차이가 2 이상(같거나 1개 정도는 그냥 둠) 나면 , heap 조절해줘야 함small heap 크기 > large heap 크기 +1 이면, small heap 의 최대값을 large heap 으로 보내고small heap 크기 +1    이 코드는 데이터 스트림에서 중간값(Median)을 실시간으로 추적하는 클래스를heapq (Python의 우선순위 큐)를 이용해 구현한 것입니다.import h..

지금까지 본 inorder, preorder, postorder 순회 방식은 모두**Iterative DFS (반복형 깊이 우선 탐색)**입니다.즉, 재귀 없이 스택(stack) 을 사용해 직접 순서를 제어하면서 깊이 우선 탐색을 구현한 방식이에요.✅ Iterative DFS란?DFS (Depth-First Search) = 트리를 아래(깊이)로 먼저 탐색하는 알고리즘일반적으로는 재귀로 많이 구현하지만,Stack을 이용해서 반복문으로 구현한 DFS를 Iterative DFS라고 부릅니다.✅ 언제 Iterative DFS를 쓰는가?상황이유상황이유🔁 재귀 호출이 너무 깊어질 수 있는 경우Python은 재귀 깊이 제한(기본 1000) 때문에 RecursionError 발생 위험🧠 재귀보다 명시적 흐름이 필..

class SegmentTree: def __init__(self, total, L, R): # 현재 노드가 표현하는 구간의 합 self.sum = total # 왼쪽 자식 노드 (L ~ M 구간) self.left = None # 오른쪽 자식 노드 (M+1 ~ R 구간) self.right = None # 현재 노드가 커버하는 시작 인덱스 self.L = L # 현재 노드가 커버하는 끝 인덱스 self.R = R # 세그먼트 트리를 생성하는 정적 메서드 # 시간 복잡도: O(n) @staticmethod def build(nums, L, R): ..

✅ Union-Find (Disjoint Set Union, DSU)란?📌 무엇인가요?여러 개의 서로소 집합(disjoint sets) 을 관리하는 자료구조입니다.주로 그래프에서 사이클을 판별하거나, 네트워크 연결 여부, 클러스터 관리 등에 사용됩니다.✅ 주요 연산 두 가지연산설명find(x)원소 x가 속한 집합의 대표(루트 노드) 를 찾음union(x, y)x와 y가 속한 두 집합을 하나로 합침✅ 최적화 기법Path Compression (경로 압축)find(x) 호출 시, 경로에 있는 노드들을 직접 루트에 연결해서 다음 검색을 빠르게 함Union by Rank / Height집합을 합칠 때, 작은 트리를 큰 트리에 붙임 → 트리 깊이를 줄여 성능 개선✅ 시간복잡도거의 O(1) 에 가깝습니다 (아커만..

Trie (접두사 트리) - 동기 우리가 왜 trie가 필요한지에 대한 동기를 살펴봅시다. 예를 들어, 오이(cucumbers), 콜리플라워(cauliflower), 토마토(tomatoes) 같은 여러 채소가 들어 있는 큰 상자가 있다고 해 봅시다.만약 이 채소들을 이름 기준으로 정리하고 싶다면, 우리는 먼저 더 작은 상자들을 준비해서 알파벳 각 글자를 이름표로 붙일 수 있을 거예요.예를 들어, "A"로 시작하는 채소들은 "A" 상자에 넣는 식으로요. 접두사(prefix)가 같은 단어들을 처리하는 방식Trie에서는 중복되는 접두사를 공유된 경로로 나타내어 공간을 절약하고 효율적으로 구조화할 수 있음 Trie의 계층 구조: 상자 안에 또 상자를 넣는 방식으로, 단어의 각 글자마다 하나씩 노드를 추가해 나가..

prefix sum(프리픽스 섬, 누적합)은 배열의 앞에서부터의 합을 미리 계산해서 저장해두는 것이에요.🔸 예시로 설명할게요:nums = [1, 2, 3, 4, 5]  이 배열의 prefix sum은 다음과 같아요:prefix[0] = 1 prefix[1] = 1 + 2 = 3 prefix[2] = 1 + 2 + 3 = 6 prefix[3] = 1 + 2 + 3 + 4 = 10 prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 즉, prefix = [1, 3, 6, 10, 15] 🔹 왜 쓰냐면?예를 들어 nums[1] + nums[2] + nums[3] 이런 계산을 자주 해야 하면매번 더하는 대신에 한 번에 구할 수 있어요:prefix[3] - prefix[0] = 10 - 1 = 9 *..