먼저. 최소 신장 트리란? 최소 신장 트리란, 최소 가중치의 간선을 사용해서 싸이클이 생기지 않으며 모든 정점을 연결한 그래프이다. 앞선 글에서 최소 신장 트리를 구하는 크루스칼 알고리즘에 대해 배웠다. 하지만 또 한가지 최소 신장 트리를 구하는 알고리즘이 있다. 바로 프림 알고리즘이다. 오늘은 크루스칼과 프림 알고리즘을 비교하며 최소 신장 트리를 구하는 과정을 파헤쳐보자. 크루스칼(Kruskal) 동작 원리 - 1. 모든 간선을 가중치 기준 오름차순 정렬한다. - 2. 최소 가중치 간선부터 순차적으로 선택한다. 만약, 선택을 함으로써 싸이클이 형성된다면(Find 연산 사용하여 판단) 해당 간선은 선택하지 않는다 - 3. 이렇게 순차적으로 간선을 선택하면서 정점-1개의 간선이 선택되면 완료. 프림(Pri..
OSI 7계층 OSI 7 계층은 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것을 말한다. 왜 7계층으로 나눴을까? 통신이 일어나는 과정을 단계별로 확인할 수 있다. 가장 중요한 핵심은 오류제어를 쉽게 할 수 있다는 점이다. Layerd Architecture의 특성상 상위 계층은 하위계층 하고만 상호작용한다. 그렇기 때문에 통신에 이상이 생겼을때, 에러가 난 부분의 상위 계층은 상관이 없기때문에 건들이지 않아도 되는 에러 추적 및 처리에 이점이 있다. 총 7개의 계층으로 나눠지고 각 계층마다 역할이 있다. 1계층 : 물리 계층 전기적, 기계적 특성을 이용해서 데이터를 통신케이블로 전송하는 역할 이 계층은 단순히 데이터를 송수신할 뿐, 그 데이터가 무엇인지 어떤 에러를 가지고 있는지 전혀 체크하지 ..
크루스칼(Kruskal) 알고리즘. 이름 좀 멋지네? 널 샅샅이 파헤쳐주마. 개념 그래프의 모든 정점을 최소 비용으로 연결하기 위한 알고리즘! 즉, 그래프에는 정점(Vertex)와 간선(Edge)이 존재하며, 간선에는 가중치(Weight)가 있는데, 모든 정점을 연결했을때 싸이클이 존재하지않고, 최소 비용의 가중치로 간선을 사용하는 알고리즘이다! 이렇게 모든정점이 싸이클 없이 최소 가중치로 연결된 그래프를 "최소신장트리"라고 부른다. 먼저 신장 트리에 대해 알아보자. 신장 트리란? (1) 모든 정점을 포함하고, (2) 정점 간 서로 연결이 되며 (3) 싸이클이 존재하지 않는 그래프를 뜻한다. 그리고 그래프의 신장 트리중에서 가중치 합이 최소가 되는 것이 바로 최소 신장 트리인 것이다. 최소 신장트리(Mi..
기존의 Union-Find 일반적으로 Find 연산은 부모 노드를 재귀를 통해 찾아나간다. 또한 Union연산은 특별한 기준없이 어느 한쪽에 합쳐지게 된다. 하지만 매번 Find를 수행한다면 root 노드를 계속해서 찾아나가는 불필요한 연산을 계속 하게되는 것이다. 또한 Union 연산 시, 아무렇게나 그래프를 합친다면 트리의 높이가 비효율적으로 늘어나서 최악의 경우 O(N)의 시간복잡도를 보이게 된다. 이를 개선하기 위한 방법에는 2가지가 있다. 1. 경로 압축 위 그림과 같이 find을 한번 수행할때, 방문하는 해당 노드의 부모를 root 노드로 갱신시켜주는 것이다. 그 결과 경로를 압축한 노드들에 대해서는 부모 노드가 이미 root로 갱신된 상태이므로 또 다시 재귀를 통해 root 노드를 찾아나서는..
이름을 들으면 뭔지 잘 모르겠는 disjoint...Set..? 과 Union-Find..? 파헤쳐보자. 개념 disjoint Set은 '서로소 집합'으로 공통 원소를 갖지 않는 2개 이상의 집합을 의미한다. (왼쪽은 1이라는 공통원소를 가지고 있으므로 서로소 관계가 아니다.) MakeSet, Union, Find 1) MakeSet : 모든 원소들을 각각 독립적인 집합으로 만든다. 이것을 구현한다면, int[] set = new int[5]; for(int i=0; i
그래프는 나에게 있어서 항상 어려운 자료구조였다. 이번 기회에 제대로 이해해보자. 개념 그래프는 정점(Vertex)와 간선(Edge)으로 구성된 집합이다. 간선의 특징에 따라 크게 3가지로 분류할 수 있다. 1) 무방향 그래프(undirected graph) 간선의 방향이 없는 양방향 그래프 2) 방향 그래프(directed graph) 간선의 방향이 있는 그래프 3) 가중치 그래프(weight graph) 간선에 가중치(weight)가 있는 그래프 기타 종류 1) 연결, 비연결 그래프 연결 그래프는 무방향 그래프에서 모든 정점에 대해 연결이 되어 있는 그래프 ps) 이때 트리(Tree)는 그래프의 일종으로, 사이클을 가지지 않는 연결 그래프이다. 2) 사이클, 비순환 그래프 경로상에 중복되는 정점이 없..
