Core Data Structures

1. Overview

핵심 자료 구조(Core Data Structures, CDS)는 데이터를 조직화하고 관리하여 연산의 효율성을 극대화하는 표준 모델들을 다룹니다.

추상 자료형(ADT)은 '무엇을 하는가'를 정의하고, 자료 구조는 '어떻게 구현하는가'를 결정합니다. 학습자는 단순 선형 구조(Stack, Queue, Hash)부터 비선형 구조(Tree)까지의 핵심 논리를 이해하고, 특히 해시 충돌(Collision) 해결 전략이나 이진 탐색 트리(BST)의 자가 균형(Self-balancing) 메커니즘을 학습합니다. 이를 통해 실제 애플리케이션의 성능 병목을 해결하는 최적의 저장 모델을 설계합니다.

2. Scope & Boundaries

In-Scope

• Linear Abstractions: Stack, Queue, Deque의 원리와 물리 구현(Array vs List)
• Hashing Mechanics: 해시 함수 설계, Open Addressing vs Chaining 충돌 회피 물리
• Tree Foundations: Binary Tree, BST, 균형 트리(AVL, Red-Black) 입문 이론
• Priority Structures: Heap(Max/Min)의 완전 이진 트리 기반 구현 및 동작

Out-of-Scope

• 그래프(Graph) 알고리즘 상세 (04-03 및 04-04 영역으로 위임)
• B-Tree 등 외부 저장 장치 전용 자료 구조 (06. Data Management 영역으로 위임)

Boundaries

• CDS vs. Technique: CDS는 '데이터를 담는 그릇의 형태'에 집중하며, Technique(04-03)은 '그 그릇을 사용하여 문제를 푸는 논리'에 집중합니다.

3. Counterexample

• 단순히 std::map이나 HashMap을 사용하는 것은 CDS 학습이 아닙니다. 해시 테이블의 **부하율(Load Factor)**이 임계치를 넘었을 때 일어나는 재해싱(Rehashing) 오버헤드와, Red-Black 트리가 왜 항상 $O(log N)$의 높이를 보장하는지 회전(Rotation) 물리 로직으로 설명할 수 있어야 합니다.

4. Prerequisites

• 기초 및 복잡도 (Basic): Big-O 분석법과 포인터/레퍼런스의 개념이 선행되어야 합니다. (04. Foundations)
• 디지털 논리 (Basic): 메모리 주소 할당과 오프셋 연산에 익숙해야 합니다. (01. Digital Logic)

5. Learning Map

1. Logical Abstractions: 데이터의 순서와 접근 권한을 제어하는 ADT(Stack/Queue)를 익힙니다.
2. Access Physics: 키를 통해 즉시 데이터에 접근하는 해싱(Hashing)의 물리적 비용을 이해합니다.
3. Hierarchical Logic: 계층 구조와 탐색 효율을 극대화하는 트리(Tree)의 속성을 배웁니다.
4. Ordering & Priority: 우선순위에 따른 동적 데이터 관리(Heap)를 실습합니다.

6. Learning Topics

Basic

Core: 선형 ADT와 구현 (Linear ADTs)

• Why to Learn: 작업의 순서를 제어하고(LIFO/FIFO) 임시 저장소를 효율화하기 위함입니다.
• What to Learn:
  • Stack(뒤로 가기)과 Queue(프로세스 스케줄링)의 물리적 용례
  • 고정 배열 기반 구현 vs 연결 리스트 기반 구현의 오버헤드 차이
  • 큐의 단점을 보완한 원형 큐(Circular Queue)와 덱(Deque)
• How to Learn:
  • 함수 호출 스택(Call Stack)의 메모리 구조를 Stack ADT로 가시화
  • 배열 기반 큐에서 데이터 이동(Shifting) 문제 체감 실습
• Implement: 배열을 이용해 오버플로우 처리가 가능한 기초 스택 라이브러리

Recommended

Core: 해싱과 맵 물리 (Hashing & Maps)

• Why to Learn: 대용량 데이터에서 평균 O(1) 탐색 성능을 보장하기 위해서입니다.
• What to Learn:
  • 결정론적(Deterministic) 해시 함수와 균등 분포(Uniform Distribution)
  • 충돌 해결 1: Chaining (연결 리스트 활용)
  • 충돌 해결 2: Open Addressing (Linear Probing, Double Hashing)
• How to Learn:
  • 부하율(Load Factor) 변화에 따른 해시 테이블 탐색 성공/실패 횟수 분석
  • 충돌 발생 시 물리적인 메모리 점유 시뮬레이션
• Implement: Chaining 방식을 사용하는 단순 해시 맵(Hash Map)

Practical

Core: 트리 구조와 이진 탐색 (Trees & BST)

• Why to Learn: 정렬된 상태를 유지하며 빠른 탐색과 삽입을 동시에 달성하기 위함입니다.
• What to Learn:
  • 이진 트리(Binary Tree)의 순회(Traversal: Pre/In/Post-order) 물리
  • 이진 탐색 트리(BST)의 속성과 최악의 경우(Skewed Tree) 분석
  • 완전 이진 트리(Complete Binary Tree)와 힙(Heap)의 배열 매핑 원리
• How to Learn:
  • 트리의 각 노드가 메모리에서 포인터로 연결되는 구조 가시화
  • 재귀를 이용한 트리 순회와 스택 메모리 사용량 관계 분석
• Implement: 힙 정렬(Heap Sort)에 사용되는 Up-heap/Down-heap 로직

Advanced

Core: 자가 균형 트리와 특수 구조 (Self-balancing & Specialized)

• Why to Learn: 데이터가 편향되게 입력되어도 일정한 성능($O(log N)$)을 보장하기 위해서입니다.
• What to Learn:
  • AVL 트리의 BF(Balance Factor)와 LL/RR/LR/RL 회전 물리
  • Red-Black 트리의 색상 규칙과 리밸런싱 메커니즘 기초
  • 다차원 탐색을 위한 Tries(Prefix Tree)의 노드 구조 최적화
• How to Learn:
  • 시뮬레이터를 통해 노드 삽입 시 트리가 회전하며 균형을 잡는 과정 관측
  • 문자열 검색 시 해시와 트라이의 시간/공간 복잡도 손익 비교
• Implement: 단순화된 AVL 트리의 삽입 및 회전 유닛 테스트

7. Terminology

8. References

Primary References

• [P1] CS2023 - AL/Fundamental Data Structures — Core ADTs and trees.
• [P4] DS-BoK - Data Infrastructure — Implementation patterns.

Secondary References

• [Algorithms in C++, Parts 1-4] Robert Sedgewick — Detailed implementation focus.
• [Open Data Structures] Pat Morin — Mathematical and code symmetry.

Industry References

• [Java Collections Framework Design] — Real-world DS engineering.
• [Python Internal Dictionary (dict) Wiki] — Advanced hashing patterns in industry.

9. Final Checklist

Primary Checklist

• 스택과 큐를 배열로 구현할 때의 '고정 크기' 한계와 리스트 구현 시의 '참조 오버헤드'를 비교 설명 가능한가? (P1)
• 해시 테이블에서 충돌이 잦아질 때의 검색 성능 저하를 $O(1) \to O(N)$ 관점에서 증명할 수 있는가? (P1, P4)

Secondary Checklist

• 완전 이진 트리가 배열 인덱스만으로 부모/자식 노드를 찾는 물리적 수식($2k, 2k+1$)을 유도할 수 있는가?
• BST 탐색 성능이 입력 순서에 따라 왜 변하는지, 그리고 균형 트리가 이를 어떻게 해결하는지 이해하는가?

Industry Checklist

• 대규모 문자열 자동완성 시스템 설계 시 해시 대신 트라이(Trie)를 선택해야 하는 복잡도 근거를 제시 가능한가? (SFIA)
• 실무 언어의 맵(Map)이 내부적으로 트리(SortedMap)인지 해시(HashMap)인지에 따른 순회 순서 차이를 인지하는가?