최소 스패닝 트리 알고리즘 비교: Kruskal, Prim, Boruvka
Kruskal 알고리즘
희소 그래프(Sparse Graph)에 적합한 크루스칼 알고리즘은 간선 기반의 탐욕적 접근 방식을 사용한다. 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 사이클을 만들지 않는 한도 내에서 순차적으로 선택한다. 이때 연결 여부는 유니온-파인드(Union-Find) 자료구조로 관리한다.
n개의 정점이 주어졌을 때, 최소 스패닝 트리는 정확히 n-1개의 간선으 ...
6월 17일 18:25에 게시됨
문제 해결을 위한 알고리즘 접근
A 문제
링크
연속된 두 개의 '달콤한' 요소가 있으면 나머지 요소들을 모두 먹을 수 없습니다.
코드 보기
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string dishes[105];
for (int i = 0; i < n; ++i) {
cin >> dishes[i];
if (i > 0 && ...
5월 28일 19:00에 게시됨