선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하나의 자료가 존재하는 구조이다. 이에 반대되는 개념으로 비선형자료구조가 있는데, 비선형자료구조란 말그래도 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태라고 볼수 있다. 이에 대한 예시로는 트리, 그래프가 대표적이다. 이번 글에서는 선형자료 중, 배열과 연결 리스트에 대해서 알아보도록 하겠다. 정적 배열 (Static array) 맨 처음 선언 시, 해당 배열의 크기를 지정하고, 한번 지정된 크기는 절대 변경할 수 없다 배열에 저장된 자료들은 메모리 상에서 연속적으로 위치한다. 임의 접근(Random A..

신장 트리(Spanning Tree) 한 그래프의 부분 그래프이며, 그래프에서 모든 정점을 포함한다. 정점 간 서로 연결이 되어있어야 한다. 사이클이 존재하지 않는다. 그래프에서 신장트리는 1개가 아닌 다수일 수 있다. 신장트리는 트리이다. 원래 그래프에서 n개의 정점을 가지고 있었다면, 신장 트리는 n개의 정점과 n-1개의 간선을 가진다. 그래프 자료구조에 대한 자세한 설명은 아래 링크에 기술되어 있다. 그래프(Graph) 그래프(Graph)란? 그래프란 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. 즉 정점들 사이의 관계를 나타내는 자료구조이다. G = (V,E)의 형식으로 정의하는데 여기서 V는 정점, E는 간선을 currygamedev.tistory.com 최소 비용 신장..

서로소 집합(Disjoint Set) 서로 중복 포함된 원소가 없는 집합(= 교집합이 없는 집합)들을 표현하는 자료구조이다. Union(합집합), Find(집합 탐색) 연산이 가능하다. 집합에 속한 하나의 특정 원소를 대표자라고 하며 이를 통하여 집합들을 구분할 수 있다. 이 자료구조를 Array혹은 List로 구현했을 경우 최선의 시간복잡도가 O(n + u*log(u) + f)이다. (u와 f는 각각 Union과 Find연산이 실행된 횟수이다.) 하지만 이를 Tree로 구현할 경우 시간복잡도는 O(n + f)에 근접해진다. {2, 4, 5, 9, 11, 13, 30}의 원소를 가지는 집합을 트리로 표현한다면 위와 같이 다양한 모양으로 나올 수 있다. Find 연산 Find(i)를 하게 되면 i를 포함하..

선택트리는 승자트리(Winner Tree)와 패자트리(Loser Tree)로 구분된다. 승자트리 (Winner Tree) n개의 외부 노드(external node)와 n-1개의 내부 노드(internal node)를 가지는 완전 이진 트리(Complete Binary Tree) 이다. 외부 노드는 토너먼트의 플레이어라고 생각하면되고 내부 노드는 플레어이 간의 경기라고 생각하면 된다. 가장 작은 수가 우승한다. 이 트리의 루트는 최종 승자이다. 승자트리를 이용한 정렬 n개의 수를 정렬하려고 할때, Winner Tree를 가장 작은 수가 우승하는 트리라고 정하면, n개의 수를 트리의 외부 노드레 넣고 승자를 찾는다. 정렬된 숫자들을 넣은 배열을 sortedArr이라 한다면, 승자는 가장 작은수 이므로 승자..

이진탐색트리(Binary Search Tree) 란? 이진탐색트리의 정의는 다음과 같다. 이진트리(Binary Tree)이다. 각 노드는 (key, value)쌍을 가지고 있다. 임의의 노드 x에 대해서 x의 왼쪽 서브트리에 있는 노드들의 key는 모두 x보다 작고 오른쪽 서브트리에 있는 노드들의 key는 모두 x보다 크다. 이진탐색트리의 연산 이진탐색트리는 탐색, 삽입, 수정, 삭제의 연산을 가진다. IsEmpty() Get(key) -> 탐색 Insert(key, value) -> 삽입, 수정 Delete(key) -> 삭제 Get : 탐색 시간복잡도: O(n) (n은 Tree의 원소수) T Get(T item) { TreeNode ptr; ptr = root; while(ptr != null) { ..