자료구조(Data Structure) 총정리

대표적 자료구조 및 알고리즘 정리

최근에 자료구조 분류 도식, 배열(array), 연결 리스트(linked list), 스택(stack), 재귀함수와 스택 메모리, 큐(queue), 멀티스레딩과 큐에 대해 다시 공부했다. 이 외에도 해시테이블, 그래프, 트리, 힙 등 중요한 자료구조를 포함해 중요 자료구조 8개를 정리해보려한다. 

---

0. 자료구조 분류 도식

자료구조는 크게 선형(Linear) 자료구조와 비선형(Non-linear) 자료구조로 분류된다

• 선형 자료구조:
  배열, 연결 리스트, 스택, 큐 등이 대표적
  • 특징: 메모리 상에 연속적 또는 순차적으로 데이터를 저장하며, 삽입/삭제 연산이 한쪽 끝 또는 중간에서 이루어짐
• 비선형 자료구조:
  트리, 힙, 그래프 등이 있으며, 계층적 또는 네트워크 형태로 데이터를 저장
  • 특징: 노드들 간의 관계가 계층적(트리, 힙) 또는 임의(그래프)로 연결되어 있어 복잡한 데이터 관계를 표현할 수 있음

또한 해시테이블은 키-값 쌍을 기반으로 하는 자료구조로, 일반적으로 빠른 검색과 삽입을 위해 사용됨

---

1. 배열 (Array)

• 정의:
  동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조
• 특징:
  • 장점:
    • 인덱스를 통한 **O(1)**의 빠른 접근 속도
    • 메모리 할당이 단순함
  • 단점:
    • 크기가 고정되어 있어 동적 크기 조절이 어렵거나, 별도의 동적 배열 구현이 필요함
    • 삽입/삭제 시 전체 요소의 이동이 필요할 수 있음
• 활용:
  기본적인 데이터 저장, 정렬 알고리즘의 기초 자료구조 등

---

2. 연결 리스트 (Linked List)

• 정의:
  각 노드가 데이터와 다음 노드에 대한 포인터(참조)를 가지며, 노드들이 연결된 형태의 자료구조
• 특징:
  • 장점:
    • 동적 메모리 할당으로 크기 조절이 자유로움
    • 삽입/삭제가 빠름 (특히 리스트 중간에서) – 포인터 조작만으로 가능
  • 단점:
    • 임의 접근이 어렵고, 순차 접근(O(n))이 필요함
    • 각 노드에 추가적인 포인터 저장 공간 필요
• 활용:
  스택, 큐의 내부 구현, 데이터 저장 시 빈번한 삽입/삭제 작업 등

---

3. 스택 (Stack)

• 정의:
  후입선출(LIFO, Last In First Out) 원칙을 따르는 선형 자료구조
• 주요 연산:
  • Push: 스택의 top에 요소 삽입
  • Pop: 스택의 top에서 요소 삭제
• 활용:
  • 함수 호출 시 사용하는 콜 스택
  • undo/redo 기능, 괄호 검사, 깊이 우선 탐색(DFS) 등

📍 재귀함수와 스택 메모리

• 재귀 함수:
  자기 자신을 호출하는 함수로, 문제를 더 작은 하위 문제로 나눠서 해결함
• 스택 메모리와의 관계:
  • 각 재귀 호출 시 함수의 상태(매개변수, 지역 변수, 반환 주소 등)가 스택 프레임으로 스택에 저장됩니다.
  • **종료 조건(Base Case)**에 도달하면 호출이 종료되고, 스택 프레임이 하나씩 pop되어 결과가 차례로 반환됩니다.
  • 재귀 깊이가 너무 깊으면 스택 오버플로우가 발생할 수 있음
• 예제:
  팩토리얼, 피보나치 수열 등이 대표적인 재귀 알고리즘

---

4. 큐 (Queue)

• 정의:
  선입선출(FIFO, First In First Out) 원칙을 따르는 선형 자료구조
• 주요 연산:
  • Enqueue: 큐의 rear(뒤쪽)에 요소 삽입
  • Dequeue: 큐의 front(앞쪽)에서 요소 삭제
• 활용:
  • 작업 대기열, 이벤트 처리, 너비 우선 탐색(BFS) 등
  • Python의 경우 queue.Queue 또는 collections.deque를 사용해 구현할 수 있습니다.

📍 멀티스레딩과 큐

• 멀티스레딩:
  하나의 프로세스 내에서 여러 스레드가 동시에 실행되어 병렬 처리나 동시에 여러 작업을 처리할 수 있게 함
• 큐와의 결합:
  • 생산자-소비자 패턴:
    • 생산자 스레드: 작업(데이터, 요청)을 큐에 추가
    • 소비자 스레드: 큐에서 작업을 꺼내어 처리
  • 스레드 안전 큐:
    • 멀티스레딩 환경에서는 동기화가 필요한데, 스레드 안전한 큐(예: Java의 ConcurrentLinkedQueue, Python의 queue.Queue)를 사용해 데이터의 일관성을 보장
• 예제 코드:
  • Python에서는 threading 모듈과 queue.Queue를 활용
  • Java에서는 ExecutorService와 스레드 안전 큐를 활용하여 구현

---

5. 해시테이블 (Hash Table)

• 정의:
  해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
• 특징:
  • 평균 O(1)의 검색, 삽입, 삭제 속도를 보장
  • 해시 충돌(Collision) 해결 기법: 체이닝, 오픈 어드레싱 등
• 활용:
  데이터베이스 인덱스, 캐시, 딕셔너리 구현 등

---

6. 그래프 (Graph)

• 정의:
  노드(정점)와 간선(연결)으로 구성된 비선형 자료구조
• 유형:
  • 무방향 그래프: 간선이 방향성을 갖지 않음
  • 유방향 그래프: 간선에 방향성이 있음
  • 가중치 그래프: 간선에 가중치(비용)가 있음
• 활용:
  • 소셜 네트워크, 지도(최단 경로), 웹 크롤링 등
  • 탐색 알고리즘: 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

---

7. 트리 (Tree)

• 정의:
  계층적 구조를 가진 비선형 자료구조로, 하나의 루트 노드와 여러 자식 노드들로 구성됩니다.
• 종류:
  • 이진 트리(Binary Tree) 및 이진 탐색 트리(BST)
  • AVL 트리, 레드-블랙 트리 등 균형 잡힌 트리
• 활용:
  • 파일 시스템, 데이터베이스 인덱스, 파싱, 게임 AI 등
  • 트리 순회 방법: 전위(preorder), 중위(inorder), 후위(postorder)

---

8. 힙 (Heap)

• 정의:
  완전 이진 트리 형태의 자료구조로, 각 부모 노드가 자식 노드보다 우선순위가 높다는 특성을 가집니다.
  • 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같음
  • 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같음
• 특징 및 활용:
  • 우선순위 큐: 힙을 사용하여 우선순위 기반 작업 처리를 효율적으로 수행
  • 힙 정렬(Heapsort): 정렬 알고리즘의 한 방법