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

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