자료구조(Data Structure) 정리

자료구조

 

- Array 와 Linked List

  Array는 index로 해당 원소에 접근할 수 있고, 찾고자 하는 원소의 index 값을 알고 있으면, O(1)에 해당 원소로 접근할 수 있습니다.  즉, Random access가 가능하다는 장점이 있습니다. 하지만, 삽입과 삭제의 경우에는 배열의 연속적인 특징을 위해 shift를 해야 하기 때문에 비용이 발생하며, 최악의 경우 O(n)의 시간 복잡도를 가집니다.

  Linked List는 이러한 문제를 해결할 수 있습니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지를 기억하고 있습니다. 따라서 삽입, 삭제 연산을 O(1)만에 해결할 수 있습니다. 그러나 index 값으로 접근을 할 수 없기 때문에 탐색 과정에서 최악의 경우 O(n)의 시간 복잡도를 가집니다. 이 Linked List는 Tree 구조의 근간이 되는 자료구조 입니다.

 

- Stack 과 Queue

  Stack은 선형 자료구조의 일종으로, 후입선출의 특징을 가집니다. 즉, 나중에 들어간 원소가 가장 먼저 나옵니다. 차곡차곡 쌓이는 구조로 먼저 Stack에 들어가게 된 원소는 맨 바닥에 깔리게 되고, 맨 마지막에 나가게 됩니다.

  Queue는 선형 자료구조의 일종으로, 선입선출의 특징을 가집니다. 즉, 먼저 들어간 원소가 가장 먼저 나옵니다. 덧붙여, Java collection에서 Queue는 인터페이스이며, 이를 구현하고 있는 Priority queue등을 사용할 수 있습니다.

 

- Tree

  Tree는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조입니다. 이는 계층형 관계를 표현하는 자료구조입니다. 트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말합니다.

관련 용어로는 - Node, Edge, Root node, Leaf node, Internal node 등이 있습니다.

 

- Binary Tree

  Leaf node를 제외한 모든 노드가 최대 2개의 자식 노드를 가지는 트리입니다. 

Perfect Binary Tree - 모든 레벨이 꽉 찬 이진 트리

Complete Binary Tree - 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리

Full Binary Tree - 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리

 

- BST (Binary Search Tree)

  Binary Search Tree는 Binary Tree의 일종입니다. Binary Search Tree 는 데이터를 저장하는 규칙을 두어, 탐색을 좀 더 효율적으로 할 수 있게 합니다. 규칙은 다음과 같습니다.

1. 노드에 저장된 값은 유일합니다.

2. 부모의 값은 왼쪽 자식의 값보다 큽니다.

3. 부모의 값은 오른쪽 자식의 값보다 작습니다.

4. 왼쪽과 오른쪽 서브트리도 Binary Search Tree입니다.

 

Binary Search Tree에서의 탐색 연산은 O(log n)입니다. 그러나 Binary Search Tree의 한쪽에만 데이터가 계속해서 저장이 되면 편향 트리가 되어 최악의 경우에는 O(n)의 시간 복잡도를 가집니다. 따라서 이를 해결하기 위해 트리의 재조정인 Rebalancing 기법이 등장하였습니다. 이 기법을 구현한 트리 중 하나는 Red-Black Tree가 있습니다.

 

- Binary Heap

  Complete Binary Tree 의 형태를 가집니다. Heap의 종류에는 Max heap과 Min heap이 존재하는데, Max heap은 각 노드의 값이 자식 노드의 값보다 크거나 같은 형태로 저장되어 있습니다. 따라서, Root node의 값이 가장 큰 값이며, 가장 큰 값을 찾는데 O(1)의 시간 복잡도를 가집니다. 데이터를 빼거나 추가할 때는 re-heapification을 수행하여, heap 구조를 유지하며 이때의 시간 복잡도는 O(log n)입니다.

 

- Red-Black Tree

  시간이 남으면 공부하고 정리 예정

 

- Hash Table

  Key-Value 값 쌍으로 저장하는 자료구조입니다. hash function을 사용하여, key 값을 input으로 넣어 나오는 output 값을 hash code라 하는데, 이를 index로 사용합니다. 서로 다른 두 Key가 같은 index로 hashing 되는 상황을 collision이 발생했다고 합니다. Collision이 많아질 수록 탐색에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워지므로, hash function을 잘 설계하는 것이 중요합니다.

  Collision을 해결하는 방식은 크게 두 가지가 있습니다.

1. Open Address 방식 - 중 하나로 순차적으로 비어 있는 공간을 탐색하여 저장합니다

2. Separate Chaining 방식 - 각 저장 공간을 Linked List 또는 Tree를 사용하여 저장합니다.

 

데이터의 수가 작을 때는, Open Address 방식이 효율적일 수 있으나, 데이터의 수가 커질 때는 Separate Chaining 방식이 Hash Table 크리의 확장을 늦출 수 있습니다.

 

저장 공간의 개수가 적다면 메모리 사용을 아낄 수 있지만, 해시 충돌로 인해 성능 상 손실이 발생할 수 있어, Java의 HashMap은 데이터가 일정 공간(75%)을 차지하면 저장 공간을 2배로 늘립니다.

 

- Graph

  Vertex와 Edge의 집합으로 이루어진 자료구조입니다. 방향성이 있는 Directed Grpah와 방향성이 없는 Undirected Grpah가 있습니다.

 

그래프를 표현하는 방법으로는 두 가지가 존재합니다.

1. Adjacent Matrix : 연결관계를 O(1)의 시간 복잡도로 확인할 수 있으나, 공간 복잡도는 edge의 개수와 상관없이 vertex^2입니다.

2. Adjacent List : 연결관계를 단번에 확인할 수는 없으나, 공간 복잡도는 edge+vertex입니다.

 

그래프의 모든 정점을 탐색하는 방법으로는 두 가지가 존재합니다.

1. DFS : Stack 자료구조를 사용하며, 특정 vertex에서 시작하며, 해당 vertex와 연결되어 있는 하나의 vertex 방향으로 탐색을 진행합니다. 이를 반복적으로 수행하다가, 연결된 vertex가 존재하지 않으면, backtrack하여 이전 level의 vertex에서 탐색을 진행합니다.

2. BFS : Queue 자료구조를 사용하며, 특정 vertex에서 시작하며, Tree에서 level이 존재하는데, 이 level을 내려오면서 탐색을 진행하는 방법입니다. 가중치가 없는 edge의 경우 BFS 방법을 사용하면 항상 최적의 해를 구할 수 있습니다.

 

- Minimum Spanning Tree

  그래프의 모든 vertex가 연결되어 있으면서, 사이클이 존재하지 않는 것이 Spanning Tree입니다. 하나의 그래프에는 여러 개의 Spanning Tree가 존재할 수 있는데, 이들 중 edge 가중치의 총 합이 가장 작은 것을 Minimum Spanning Tree라고 합니다.

 

1. Kruskal Algorithm

초기에 edge를 고려하지 않고, vertex 들로만 그래프를 구성합니다. 이후 edge들을 오름차순으로 정렬한 후, 가장 작은 edge를 그래프에 추가시켜 보면서, 사이클이 발생하지 않는다면 그래프에 추가하여 MST를 만들어 나갑니다.

 

2. Prim Algorithm

초기에 vertex 하나로만 그래프를 구성합니다. 이후 vertex를 하나씩 선택하는 과정을 거치며 MST를 만들어 나갑니다. 구체적으로, 아직 선택된 vertex와 선택되지 않은 vertex를 연결하는 edge중 가장 작은 edge를 추가시켜 나가는 과정을 반복합니다.