Algorithm/이론(17)
-
(2)최소 비용 신장 트리(MST) Generic MST
최소 신장 트리는 일반적으로 kruskal Alogorithm과 Prim의 알고리즘으로 이루어져있다. 이 두 알고리즘을 알아보기전에 두 알고리즘은 공통적인 특징을 가지고 있는데 이를 Generic MST라고 한다. Generic MST에 대해 알아보자!!! Generic MST 처음에는 A = 공집합 으로 둔다. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다. (MST의 규칙을 어기지 않는 에지를 찾은 후) 에지의 수 n-1이 될 때 까지 2번을 반복한다. 안전한 엣지 찾기 그럼 위의 알고리즘을 완성하기 위해 안전한 엣지를 찾는 방법에 대해 알아보자 1. 그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 cut(S, V-S)라고 부른다. 2. 에지 (u, v)에 대해서 u가 ..
2019.05.20 -
(1)최소 비용 신장 트리(MST) 기본이론
최소 비용 신장 트리(MST) 최소비용신장트리란 아래의 사진에서 각 노드들이 최소의 비용으로 모든 노드들이 연결되어야 하는 경우를 말한다. 자세히 보면 무방향 가중치 그래프이다. 각 노드사이에 방향성은 없고 노드 사이에 가중치가 존재하는 형태이다. 아래와 같은 사진을 보면 굵을 곡선으로 이루어진 트리가 최소비용신장트리이다. 하지만 사진을 자세히 보면 알 수 있듯이 최소비용신장트리는 유일하지 않다. 만약 b와 c의 연결고리 대신 a와 h를 선택해도 같은 가중치에 모든 노드들이 연결되었을 것이다. 위의 내용들을 정리해보자면 무방향 가중치 그래프이다. 각 에지에 대한 가중치는 w(u, v)와 같이 표현가능하다. 조건 - T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다. - 가중치의 합이 최소가된..
2019.05.20 -
Hashing
Hashing의 권오흠 교수님의 수업을 들으며 교수님께서 말하긴 이 친구는 너네 식으로 말하면 치트키다라는 말씀이 인상깊었다. 그럼 왜 그런말을 했는지 알아보자!! Binary Search Tree는 Hashing과 비슷한 Dynamic Set이다. Dynamic Set은 동적으로 데이터가 저장되고 삭제되고 검색하는 것을 뜻한다. Binary Search Tree는 높이에 비례하기 때문에 insert, search, delete는 O(n)이고 red black은 O(logn)입니다. 그렇지만 Hashing은 O(1)의 시간이 소요된다. 혹은 최악으로 O(n)이 소요된다. 왜 이렇게 되는지 알아보자!! 기본적으로 key와 value의 조합으로 이루어 져있으며 (key, "hoony) 이러한 형태로 이루어 ..
2019.04.29 -
이진 탐색트리
이진 탐색 트리 1. 이진트리의 조건을 유지하면서 2. 자기 부모나 루트보다 작거나 같은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내버리는 이진트리를 의미한다. 3. 이에 대응하는 서브트리들도 이 조건들을 모두 만족해야한다. 그림으로 만들어보면 아래와 같이 볼 수 있을 것이다. 특정한 값을 검색하고 찾는데 더 효율적일 것이다. 입력, 탐색, 삭제 모두 높이에 비래해서 시간복잡도가 걸린다. O(n)이다. 입력은 특정한 값이 들어오면 루트나 부모와 비교하여 왼쪽 혹은 오른쪽으로 이동하게 만들어준다. 계속 자기의 자리를 찾아가다 자리를 완전히 찾게되면 node를 반환해준다. 트리는 누가봐도 재귀를 사용하시요 같은 구조이다. 그래서 값을 비교하여 재귀를 통해 값을 넣어줄 수 있다. Node* addNode(Nod..
2019.04.24 -
이진트리
특징 1. 트리는 하나의 루트 노드를 갖고있다. 2. 루트 노드는 2개 이하의 자식노드를 갖고 있다. 3. 그자식 또한 2개 이하의 자식노드를 갖고있고 이는 반복적으로 정의 된다. 노드들과 다른 노드들을 연결하는 간선으로 구성되어있다. 일반적으로 아래와 같은 모습으로 이루어져있다. 자식은 2개가 있어도 되고 없어도 되고 한개만 있어도 된다. 모든 노드들에 상응한다. 방법은 일반적으로 배열과 연결리스트 와 같은 방식으로 구성된다. 배열은 크기가 제한적이고 빈칸이 생길 수 있다. 그렇지만 쉽고 간단하게 표현할 수 있다. 용어 정리 Root: 제일 상위 노드 부모-자식 관계: 노드의 상위 노드가 부모이고 그 밑의 노드를 자식이라고 한다. 형제: 부모가 동일한 노드들을 형제라고 부른다. leaf: 자식이 없는 ..
2019.04.22