{Programing}/Data Structure18 Minimum Spanning Tree, MST - 최소 신장 트리 임의의 그래프에서 가중치의 합이 최소인 최소 연결 부분 그래프. 부분 그래프 : 임의의 그래프에서 일부 간선을 제거한 그래프. 전체 그래프의 부분 집합. 연결 그래프 : 부분그래프 중에 그래프의 모든 두 노드 사이의 경로가 존재하는 그래프. 최소 신장 트리는 그래프의 특수한 경우인 트리, 트리의 특수한 경우이기 때문에 두가지 조건을 만족한다. 1. 사이클이 존재하지 않는다. - 트리의 특징. 2. 모든 노드가 연결되어 있다. 2020. 3. 9. Graph 그래프는 저장된 자료들사이의 관계를 나타내기를 위한 구조. 정점(Vertex) : 자료를 나타내는 단위로 리스트나 트리의 노드와 같은 의미. 간선(Edge) : 정점을 연결하는 선을 의미하며 자료사이의 관계를 나타냄. 가중치(Weight) : 한 정점에서 다른 정점으로 이동하는데 필요한 자원을 나타냄. 즉, 간선의 값. 가중치를 표시하지 않는다면 1로 생각해도 무방. 차수(Degree): 그래프에 연걸된 간선 수. 노드사이의 모든 연결 간선수를 나타냄. - 입력 차수 : 방향성 그래프일때 노드로 들어오는 간선수. - 출력 차수 : 방향성 그래프일때 노드에서 나가는 간선수. 단순 경로 : 그래프의 한 정점에서 다른 정점으로의 경로 중, 모든 정점을 단 한번씩만 방문하는 경로. 사이클(Cycle) : 단순 .. 2020. 3. 5. Array 많은 프로그래밍 언어에서 기본적으로 지원하는 자료구조로 선형 자료구조의 대표격으로 리스트와 거의 비슷하다. 리스트와 차이점은 물리적 메모리의 주소값이다. 리스트는 포인터로 구성된 만큼 물리적 메모리가 선형적으로 딱 붙어있지 않는다. //리스트 그림. 메모리 주소 배열은 물리적 메모리가 딱 붙어서 저장된다. //배열 그림. 메모리 주소 배열에는 정적 배열, 동적 배열이 있다. 정적 배열 : 배열 선언시 크기가 정해지는 배열. c++ 에서는 선언후에 길이를 재조정 할 수 없다. 동적 배열 : 포인터를 기반으로 생성하는 배열로, 필요한 경우 재할당을 통한 길이 조정이 가능하다. 배열을 구성하는 단위를 '요소' 라고 하며 각 요소는 index라고 하는 고유의 번호를 가지게 된다. 실제로 저장되는 값은 아니다. .. 2020. 1. 28. Tree - Normal 나무를 형상화한 자료구조로 뿌리부터 가지, 나뭇잎으로 세분화되는 구조에서 착안된 구조. 그래프 구조의 특별한 타입이기도 하다. 루트 : 트리의 최상위 노드. 리프 : 트리의 최하위 노드. 엣지 : 부모자식노드사이를 연결하는 선. 노드 : 트리의 구성요소. 자식과 연결될 포인터와 데이터를 저장할 공간을 가짐. 차수 : 같은 부모에 최다 연결된 노드의 수. 깊이 : 루트에서 해당 노드까지의 직선 엣지수 형제 노드 : 부모가 같은 노드들. 조상 노드 : 부모부터 루트까지의 모든 노드 자손 노드 : 자식에서 리프 노드까지의 모든 노드. 레벨 : 루트를 기준으로 1부터 깊이에 따른 노드집합. 트리의 특수한 타입으로 이진트리, 이진 탐색트리, AVL 트리, Red-Black 트리, B 트리, B+ 트리, 최소 신장.. 2020. 1. 21. 이전 1 2 3 4 5 다음