Oneulog

https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬..

크루스칼 알고리즘 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 -> 여러 개의 도시가 있을 때 각 도시의 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하기 위해 적용되는 알고리즘 핵심 개념 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 주의 사항 사이클이 발생하지 않아야 한다. 사이클이란 그래프가 서로 연결되어 사이클을 형성하는 경우 최소 비용 신장 트리에서는 사이클이 발생하지 않아야 한다. 사이클 발생 여부는 Union-Find 알고리즘을 적용하면 된다. 동작 과정 모든 간선들을 '거리(비용)' 기준으로 먼저 오름차순 정렬 수행 정렬된 순서에 맞게 그래프에 포함시킨다. 포함시키기 전에 사이클 테이블을 확인한다. 사..