cs-study

자료구조

이 디렉토리는 컴퓨터 과학의 핵심 개념 중 하나인 자료구조(Data Structure)에 대한 이론과 구현을 정리한 공간입니다.
자료구조는 데이터를 어떻게 효율적으로 저장하고, 접근하고, 처리할 것인가에 대한 방법론이며, 대부분의 알고리즘은 적절한 자료구조와 함께 설계됩니다.

분류

1. 선형 구조 (Linear Structures)

• 배열 (Array): 고정된 크기의 연속 메모리 공간, 인덱스를 통한 빠른 접근
• 리스트 (List): 삽입/삭제가 용이한 선형 자료구조 (배열 리스트, 연결 리스트 등)
• 스택 (Stack): LIFO 구조, 재귀 호출이나 백트래킹 등에 활용
• 큐 (Queue): FIFO 구조, 작업 예약이나 버퍼링에 적합
• 덱 (Deque): 양쪽 끝 삽입/삭제가 가능한 구조

2. 비선형 구조 (Non-Linear Structures)

• 트리 (Tree): 계층 구조 표현에 사용, 이진트리, 이진 탐색 트리(BST), 힙 등 포함
• 그래프 (Graph): 정점과 간선의 관계를 표현, DFS, BFS, 최소 신장 트리 등과 함께 사용

3. 해시 구조

• 해시 테이블 (Hash Table): 평균 O(1)의 빠른 접근을 위한 구조, 충돌 해결 방식 포함
• 집합(Set), 맵(Map): 중복 제거, 키-값 쌍 관리에 특화된 구조

4. 응용 구조

• 우선순위 큐 (Priority Queue): 힙 기반으로 구현되는 큐
• 트라이 (Trie): 문자열 탐색 및 자동완성 등에 활용
• 세그먼트 트리, 펜윅 트리: 구간 합/최댓값 등을 빠르게 처리하는 구조