Computer Science

자료구조(Data Structure) 총정리

haeunkim.on 2025. 2. 24. 19:33

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

최근에 자료구조 분류 도식, 배열(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): 정렬 알고리즘의 한 방법

 

반응형