programmer life guidance 101

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 (..

> 유니온 파인드(Union-Find) 그래프 알고리즘으로 합집합 찾기 알고리즘이다. 상호 배타적 집합(Disjoint-set)이라고도 한다. Disjoint Set이란 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 유니온파인드의 특징 Union-Find란 Disjoint Set을 표현할 때 사용하는 알고리즘이다. 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그중 가장 효율적인 트리 구조를 이용하요 구현한다. make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x,y) 합하기 x가 속한 집합과 y가 속한 집합을 합친다. find(x) 찾기 x가 속한 집합의 대표값(루트 노드값)을 반환한다. 즉 ..