OILAT

수강한 강의 Part 5. 패캠 제작 문제 풀이 Chapter 01. 문제풀이 - 나동빈의 패캠 제작 문제 해설 2 학습 후기 1. https://www.acmicpc.net/problem/21922 21922번: 학부 연구생 민상 첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$ www.acmicpc.net 추천 풀이 시간: 40분 40분에서 최대 2시간까지 생각해보고 풀지 못하면 풀이를 보고 확인한다. 문제 유형: 시뮬레이션, 구현 단순한 시뮬레이션 문제이므로 반복문 또는 DFS/BFS를 사용하..

수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 최소 신장 트리의 이해와 크루스칼 알고리즘 학습 후기 신장 트리(Spanning Tree)는 모든 노드들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. n개의 노드로 이루어진 그래프는 n-1개의 간선으로 연결된다. 최소 신장 트리(Minimum Spanning Tree, MST) 최소 신장 트리는 Spanning Tree 중 1. 사용된 간선의 가중치 합이 최소이고 2. n개의 노드를 가지는 그래프에서 간선이 n-1개이고 3. 사이클이 포함되지 않은 트리이다. 크루스칼 알고리즘(Kruskal Algorithm) 그래프에서 최소 신장 트리(MST)를 찾는 알고리즘으로 탐욕 알고리즘에 기초하여 각 단계에서 사이클을 이루지 않는 최소 비용의 ..