Overview 최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다. 이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 ..

풀이 이전 포스팅에서 다루었던 최소 스패닝 트리 문제를 아주 간단하게 응용하여 풀 수 있는 문제입니다. 최소 스패닝 트리를 이전과 마찬가지로 구하고 나서, 최소 스패닝 트리를 잇는 가장 가중치가 큰 간선을 제외하면 가장 작은 비용으로 두 마을을 나누어줄 수 있습니다. 따라서 최소 스패닝 트리를 생성할 때에 추가되는 간선의 가중치 중, 가장 큰 값을 저장해두었다가 트리의 생성 비용에서 제거해주면 됩니다. 소스 코드(JAVA) import java.util.*; import java.io.*; public class Kruskal { public static int[] parent; public static ArrayList edgeList; public static void main(String[] arg..

풀이 최소 스패닝 트리를 구하는 데에는 크게 2가지 알고리즘 (크루스칼 알고리즘, 프림 알고리즘)이 알려져 있습니다. 위 문제는 최소 스패닝 트리의 가중치 값을 묻는 기본적인 문제이기 때문에, 개인적으로 구현하기 편했던 크루스칼 알고리즘을 사용하였습니다. 크루스칼 알고리즘을 사용하기 위해서는 먼저 상호 배타적 집합 (Disjoint Set)을 먼저 구현해야 합니다. 크루스칼 알고리즘은 프림 알고리즘 과는 다르게, 간선을 가중치 순으로 먼저 정렬한 후에, 가중치가 작은 간선부터 이어 나가면서, 해당하는 간선의 두 정점이 이미 같은 트리에 속해 있는지를 판단해야 합니다. 예를 들어, 1과 2를 잇는 가중치 1인 간선을 추가하려고 할 때, 1과 2를 이어주는 경로가 이미 존재한다면 해당 간선을 추가해서는 안된..

Overview 스위치(브릿지)에 관한 지난 포스팅 에서 스위치의 정의와 특징에 대해 살펴보았습니다. (스위치와 브릿지는 거의 같은 기능을 수행하므로 편의상 이 글에서는 스위치로 통일하겠습니다.) 스위치는 서로 다른 네트워크 장비들을 연결해주는 허브와 같은 기능을 합니다. 다만, 콜리전 도메인을 나누어 주지 못하는 허브와는 다르게 스위치는 서로 다른 네트워크 장비들의 콜리전 도메인을 나누어서, 서로 다른 포트에 연결된 네트워크들 끼리 딜레이 없이 통신이 가능하도록 도와줍니다. (스위치는 브로드캐스트 도메인은 나누어주지 못합니다. 이 기능은 라우터가 수행합니다.) Network Looping 스위치를 통해 네트워크를 설계할 때 가장 주의 해야 할 사항중의 하나가 바로 루핑(Looping)입니다. 루핑이란,..

Overview 허브를 설명한 지난 포스팅에서 콜리전 도메인(Collision Domain)에 관한 언급을 잠깐 했었습니다. 허브와 브릿지, 스위치는 모두 외관상으로는 비슷한 모양을 띠지만, 허브는 콜리전 도메인을 나누어주지 못한다는 특징을 가지고 있습니다. 따라서 CSMA/CD방식의 Collision Detect Method를 사용하는 이더넷 케이블의 경우 아무리 전송속도가 빠르다고 해도, 허브로 연결된 네트워크에서는 한 번에 한 컴퓨터만 데이터를 전송할 수 있었습니다. 이를 보완하는 것이 오늘 설명할 스위치(Switch)와 브릿지(Bridge) 입니다. 이 포스팅 전반에 걸쳐서 스위치와 브릿지는 거의 비슷한 기능을 수행합니다. 따라서 스위치와 브릿지가 갖는 공통적인 특징들에 대해서 주로 설명하도록 하..

Overview & Definition 머지 소트 트리는 백준 알고리즘 문제 13544 수열과 쿼리3 문제를 해결하기 위해서 사용하였던 자료구조입니다. 세그먼트 트리를 변형하여 만든 구조이기 때문에 초기화 하는 방법과, 쿼리 날리는 방법 등이 세그먼트 트리와 상당히 유사합니다. 세그먼트 트리는 리프 노드(Leaf Node)에 각 배열의 원소를 집어넣고, 부모노드에 자식 노드들의 최댓값이나 최솟값, 혹은 부분합을 저장해서 특정 구간에 대한 질의(Query)를 빠르게 처리하는데 특화된 자료구조입니다. 머지 소트 트리는 부모 노드에 각 자식 노드를 머지한 결과값을 저장한 배열을 저장합니다. 예를 들어서 왼쪽 자식 노드가 [1, 3, 5], 오른쪽 자식 노드가 [2, 4, 6]인 상태라면, 부모 노드는 [1, ..