자료구조(Data Structure) (21) 썸네일형 리스트형 서로소집합(Disjoint Set) - 합집합-찾기(union–find) 서로소집합에 대한 개념은 위키백과에 너무 잘 설명되어 있어 위키백과를 기준으로 개념을 알아보자. Q. 서로소집합(Disjoint Set : 디스조인트 셋) 은 무엇인가 ? 서로소 집합이란 우선 집합이란 단어가 들어 갔으니 수학적으로 집합 개념일 것이다. 수학적으로 집합의 개념을 컴퓨터에서는 자료구조 셋(Set)으로 표현할 수 있다. 나중에 설명하겠지만 서로소집합의 자료구조는 원래 집합 자료구조인 셋(Set)과는 다르게 트리로 구성된다. 오키 그러니 집합이라 했으니 그림1 처럼 생겼겠구나 생각하면 된다. 그럼 집합은 집합인데 서로소(disjoint)는 또 무엇일까? 디스조인트란 말은 서로 공통적인 원소가 없다는 것이다. 서로서로 각자 다르다. 예를들어 그림2. 집합개념에서 좌-상단이 Disjoin sets.. 방향그래프(Directed Graph) 구현 방향그래프(Directed Graph) 구현도 무방향 그래프(Unidrect Graph) 구현 에서 한 것과 동일하게 인접리스트와 인접행렬을 이용하여 구현할 수 있다. 차이점은 그림1 (비방향 그래프 vs 방향그래프) 처럼 방향그래프는 정점마다 연결된 에지에 화살표로 들어오고(incoming) 나가는(outgoing) 방향이 있기 때문에 구현하는데 약간 변형을 해야 한다. 인접행렬과 인접리스트를 이용하여 구현하는 상세 설명은 무방향 그래프(Unidrect Graph) 구현 을 참고하고 여기서는 무방향 그래프 구현과 차이가 나는 부분만 코드내 주석으로 설명하도록 하겠다. 인접리스트 이용하여 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24.. 방향 비순환 그래프(DAG, Directed Acyclic Graph) 지금까지 그래프(Graph)란 무엇인지 간략하게 살펴보고 인접행렬과 인접리스트를 통해 그래프를 구현해보기도 하였다. 그리고 그래프를 순환(traversal) 하기위해 방향있는 그래프던 없는 그래프던 똑같이 적용할 수 있는 너비우선탐색(BFS, Breadth First Search) 과 깊이우선탐색(DFS, Depth First Search) 알고리즘도 알아보았다. 이번 시간에는 DAG(Directed Acyclic Graph)에 대해서 알아볼텐데 DAG란 유향 비순환 그래프 or 유향 비사이클 그래프 or 방향 비순환 그래프 or 방향 비사이클 그래프 or 방향성 비사이클 그래프처럼 다양하게 번역되어지는데 핵심은 그래프 간선(에지)에 방향이 있고 처음 출발한 노드(정점) v에서 시작하여 끝내 다시 v로 .. 무방향 그래프(Undirected Graph) 구현 그래프(Graph) 란 무엇인지 어느정도 확인을 하였는데 그럼 이런 G = (V,E)로 표현되는 그래프를 프로그래밍에서 어떻게 표현할수 있을까?를 고민해야 한다. 그래프를 프로그래밍에서 표현하기위한 방법은 크게 2가지 방법이 존재하는데 하나는 인접행렬(Adjacency matrix)이고 다른 하나는 인접리스트(Adjacency list)이다. ▲ [출처] https://algorithmtutor.com/Data-Structures/Graph/Graph-Representation-Adjacency-List-and-Matrix/ 여기서는 2가지 모두 살펴볼것이고 인접행렬부터 알아보도록하자. 인접행렬(adjacency matrix) 인접행렬은 그래프를 N * N 행렬(matrix)로 정점과 에지를 표현하기 위.. 그래프(Graph)란? 수학에서, 더 구체적으로 그래프 이론에서, 그래프는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조라고 얘기한다. 컴퓨터에서의 그래프는 수학에서 객체 간에 짝을 이루는 관계를 자료구조로 모델링한 것이다. 그래프에서는 객체를 정점(Vertext) 또는 노드(Node), 점(포인트/Point) 등으로 표현하는데 보통 정점(Vertex)를 더 많이 사용하고 두개의 객체간 어떤 관계가 있는지를 나타낼 때는 에지(Edge), 간선, 링크(Link) 등으로 표현다. 따라서 객체간의 관계를 이루는 집합을 그래프 G 라고 하면 이는 버텍스 집합 V와 에지의 집합 E의 순서쌍을 G = (V, E)로 나타낼수 있다. ▲ [출처] https://www.geeksforgeeks.org/graph-data-stru.. 자료구조(Data Structure)란 SW 프로그램 구현시 우리는 많은 자료들을 사용합니다. 자료들은 크게 2가지 타입으로 나뉘는데 각 언어(language) 에 내장된(built-in) 타입과 사용자가 정의한 타입이 있습니다. 이런 자료들을 선언하면 컴퓨터는 각 자료의 크기에 맞게 메모리를 할당하고 사용자는 자료에 접근 할 때 메모리에 엑세스하여 읽 고/쓰게 (R/W) 하게 됩니다. ▲ [출처] https://www.freecodecamp.org/news/these-are-the-best-free-courses-to-learn-data-structures-and-algorithms-in-depth-4d52f0d6b35a/ 문제는 이런 자료들을 메모리에 저장 할 때 중구난방으로 막 저장하게 되면 자료를 효율적 다루기가 어려워 진다. 실생활을.. 최소신장트리(Minimum Spanning Tree) 최소신장트리란? 하나씩 분해하면서 살펴보자. Q. 신장트리란 ? 그래프는 각 정점과 정점간 연결된 에지의 집합임. G=(V,G). 그런 그래프중 모든 정점을 포함하고 & 정점간 서로 연결(connected)되어 있고 & 사이클(cycle)이 없는 그래프를 말한다. 트리자료구조가 바로 이 조건에 성립하고 그래서 신장트리라고 함. 그림2 에서 (a)는 무방향 그래프인이고 모든 정점간 연결되어 있으나 사이클(a-b-c, b-c-d등등)이 존재해서 신장트리가 아니다. (b), (c), (d) 는 모든 정점을 포함하고 & 정점이 서로 연결되어 있고 & 사이클이 하나도 없으니 신장트리라고 할 수 있음. 따라서 신장트리는 그래프의 부분그래프(subgraph) 라고 볼 수 있고 모든 신장트리는 정점 V 가 N개 라면 .. 균형 이진탐색트리(Balanced Binary Search Tree) 트리에서는 기본적인 트리 자료구조에 대해서 알아 보았고 이어서 자식이 2개 이하로만 구성되어 있는 이진트리(Binary Tree) 그리고 이진트리 중 검색을 매우 빠르게 할 수 있는 자료구조인 이진탐색트리(Binary Search Tree) 까지 하나씩 살펴보았다. 여기서 부모의 노드보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 추가하면서 서브트리가 계속 구성되어지는 이진탐색트리는 치명적인 단점이 있다는것인데 자료가 많아질수록 트리의 높이(height)가 커지기 때문에 검색에 불리해지고 최악의 경우 (worst case) 노드는 탐색하는데 log(n) 이 소요될수도 있다. 예를들어 지금까지 배운 방식대로 1 , 2, 3, 4 를 이진트리에 추가한다면 그림1 처럼 된다. 그림1 에서 4를 찾는다면 4번의 탐.. 이전 1 2 3 다음
