[CS] 자료구조

1. Array

• 논리적, 물리적 저장 순서 일치 → 인덱스로 접근 가능 😎
• 삽입 삭제 시 배열의 연속적 특성 깨짐 → worst case O(n) 시간 소요 🥲

2. Linked List

• 각각의 원소들은 다음 원소만 기억 → Tree 구조에서 유용하게 사용됨 😎
• 삽입 삭제 시 O(1) → Search에 O(n) 시간 소요 → Search, 삽입, 삭제 모두 worst case O(n) 🥲

---

3. Stack

• LIFO (Last In Frist Out)
• 선형 자료구조
• 괄호 유효성 찾기에 자주 사용됨

4. Queue

• FIFO (First In First Out)
• 선형 자료구조
• PriorityQueue → 우선순위 큐

---

5. Tree

• 비선형 자료구조, 계층적 관계
• 사이클이 허용되지 않는 그래프
• 구성요소
  • Node - 트리를 이루는 각각의 요소
  • Edge - 노드와 노드를 연결하는 선
  • Root Node - 최상위 노드
  • Leaf Node - 가장 아래 층 단말 노드
• Binary Tree (이진 트리)
  • 두 개의 서브 트리로 계속해서 나뉘어진 트리
  • Perfect Binary Tree (포화 이진 트리)
    • 모든 노드가 꽉 찬 트리
  • Complete Binary Tree (완전 이진 트리)
    • 위 → 아래, 왼 → 오 순서대로 채워진 트리
  • Full Binary Tree (정 이진 트리)
    • 모든 노드가 0개 | 2개의 자식 노드를 갖는 트리
• BST (Binary Search Tree, 이진 탐색 트리)
  • 규칙
    1. 이진 탐색 트리의 노드는 유일하다
    2. 부모가 왼쪽 자식 노드보다 크다
    3. 부모가 오른쪽 자식 노드보다 작다
    4. 왼쪽과 오른쪽의 서브트리도 이진 탐색 트리이다
  • O(log n) 의 시간 복잡도 → 한 쪽으로만 노드가 채워질 경우 O(n) (편향 트리)
  • 배열보다 메모리를 많이 써 효율을 높였지만 시간 복잡도가 같아짐 …. 🤮
  • 이를 해결하기 위해 Rebalancing 기법 등장 → Red-Black-Tree
• Binary Heap
  • 배열에 기반한 Complete Binary Tree
  • 종류
    • max heap - 자식의 값보다 크거나 같음 / Root Node 값이 최대값
    • min heap - 자식의 값보다 작음 / Root Node 값이 최소값
    • 최대값, 최소값을 찾을 때 O(1) 소요
    • Heap 구조를 유지하기 위해 제거된 Root Node를 채워야 함
      1. 맨 마지막 노드를 루트 노드로 대체한 뒤 재정렬
      2. O(log n) 시간 복잡도 소요
• Red Black Tree
  • BST 기반의 트리
  • Search, 삽입, 삭제 → O(log n) 소요
  • 정의
    • 각 노드는 Red, Black 색을 가짐
    • Root Node는 Black
    • leaf Node는 Black
    • 층마다 교차로 색상 대입
    • leaf node 까지 black nodes 개수 - Black-Height
  • 특징
    • BST의 모든 특징을 가짐
    • 자식 노드가 없을 경우 NIL 값 지정 - leaf node로 간주

---

6. Hash Table

• 배열 사용해 데이터 저장 → Search 시 고유 인덱스로 접근, O(1)
• hashcode는 중복 없이 고유의 값을 가짐

---

7. Graph

• 요소
  • 정점(vertex), 간선(edge), 가중치 (없는 그래프도 존재)
• 종류
  • Undirected Graph (무향 그래프) - 방향이 없는 양방향 그래프
  • Directed Graph (유향 그래프) - 방향성이 존재하는 그래프
• 구현 방법
  • 인접 행렬 - vertex 간의 연결 관계 확인 → 2차원 행렬로 정보 확인
  • 인접 리스트 - 간선이 얼마 없는 희소 그래프에 유용 → 연결 리스트로 정보 확인
• 그래프 탐색
  • 깊이 우선 탐색 (DFS) - 재귀를 통해 한 정점으로만 탐색을 진행, 더 이상 연결될 수 없는 정점까지 탐색 한 뒤 돌아감
  • 너비 우선 탐색 (BFS) - Queue를 활용해 연결된 모든 정점을 탐색 (최단 경로 구하기)
• 최소 신장 트리 (Minimum Spanning Tree)
  • edge weight 의 합이 최소인 spanning tree (사이클 없는 그래프)