Core Data Structures

1. Overview

핵심 자료 구조(Core Data Structures, CDS)는 컴퓨터 과학이 수십 년간 다듬어온 데이터 저장과 접근의 표준 형태들을 다룹니다.

데이터는 무작정 메모리에 구겨 넣는다고 가치가 생기지 않습니다. 언제, 어떤 순서로 넣고 뺄 것인지(LIFO/FIFO)에 따라 스택(Stack)과 큐(Queue)를 설계하고, 키-값 쌍을 $O(1)$ 속도로 찾기 위해 수학적 해시(Hash) 함수를 사용하며, 대소 관계 기반의 계층적 탐색을 위해 이진 탐색 트리(BST)와 자가 균형 트리(AVL, Red-Black)를 고안합니다. 학습자는 각 자료 구조의 추상 자료형(ADT)을 명확히 정의하고, 이를 바탕으로 실제 메모리 상에서 어떻게 물리적으로 구현되는지 그 트레이드오프를 체득합니다. 이를 통해 단순히 컬렉션 프레임워크를 가져다 쓰는 코더를 넘어, 1억 개의 데이터를 지연 없이 다루는 백엔드 시스템 아키텍트의 자질을 기릅니다.

2. Scope & Boundaries

In-Scope

• 순차 및 추상 선형 제어 (Linear ADTs): 스택(Stack)의 LIFO 원리, 큐(Queue)의 FIFO 특성, 원형 큐(Circular Queue) 포인터 연산, 덱(Deque).
• 키-값 매핑과 해싱 역학 (Hashing Mechanics): 해시 함수 설계 조건, 부하율(Load Factor), 충돌 회피 기법(Chaining, Open Addressing - Linear/Quadratic Probing).
• 계층형 트리 기초 (Tree Foundations): 이진 트리(Binary Tree) 노드 구조, Pre/In/Post-order 순회, 이진 탐색 트리(BST)의 삽입, 삭제(후계자 찾기) 알고리즘.
• 우선순위 및 자가 균형 고도화 (Advanced Structures): 완전 이진 트리(Complete Binary Tree) 기반 힙(Heap) 물리, AVL / Red-Black 트리의 회전(Rotation) 개념과 높이 보장 수식, 트라이(Trie) 기반 고속 문자열 매칭.

Out-of-Scope

• 그래프(Graph) 위상 및 네트워크 알고리즘: 다익스트라(Dijkstra) 최단 경로, 최소 신장 트리(MST), 위상 정렬 등은 자료구조 자체보다 '알고리즘 기법'에 가깝기 때문에 → 04-03, 04-04 Graph, String & Optimization 영역으로 위임.
• 디스크 저장 장치 최적화 B-Tree / LSM Tree 상세 구현: RDBMS나 NoSQL 엔진 내부의 디스크 블록 정렬 트리 물리 → 06. Data Management 영역으로 위임.

Boundaries

• CDS vs. Algorithm Design (04-03): CDS가 '데이터를 담아두는 영리한 박스(Box) 자체의 모양과 유지보수 로직'에 집중한다면, Algorithm Design 영역은 '그 박스에 든 데이터를 꺼내어 분할 정복(Divide & Conquer)하거나 동적 계획법(DP)으로 문제를 푸는 로직의 흐름'에 집중합니다.

3. Counterexample

• 인터페이스(ADT)와 물리적 구현(Data Structure)의 혼동: 자바의 Stack 클래스를 쓰면서 "스택은 배열이다"라고 단정하는 좁은 시야. 스택(Stack)은 '가장 나중에 들어온 것이 먼저 나간다(LIFO)'는 **기능적 약속(ADT)**일 뿐, 이것을 실제 물리 메모리에서 배열로 만들든, 연결 리스트로 만들든 그건 자유로운 선택이며 각각 캐시 효율성이나 메모리 할당 속도 측면에서 장단점이 존재한다는 점을 분리하여 설명할 수 있어야 합니다.
• 해시 충돌 방치 및 부하율 미고려: "해시 맵은 무조건 탐색이 $O(1)$이다"라는 맹신. 데이터가 가득 차 해시 테이블의 **부하율(Load Factor)**이 1.0을 넘어가면 모든 데이터가 하나의 버킷에서 연결 리스트로 줄줄이 엮여 탐색이 $O(N)$으로 처참히 추락하는 해시 충돌(Collision) 물리 현상을 망각한 설계. 재해싱(Rehashing)과 동적 크기 확장의 오버헤드를 증명해야 합니다.

4. Prerequisites

• 기초 및 복잡도 (Basic): 각 자료 구조 연산(삽입, 탐색, 삭제)의 효율성을 Big-O 표기법으로 검증해야 합니다. (04-01. Foundations & Complexity)
• 메모리 할당 로직 (Recommended): 트리의 노드들이 포인터로 동적 할당되는 힙(Heap) 메모리 할당(malloc/new) 원리가 권장됩니다. (03. Operating Systems)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 선형 제어 추상화 (Stack, Queue, Deque)

• Why to Learn: 함수 호출 복귀, 웹 브라우저 뒤로 가기, 프린터 작업 대기열 등 데이터의 '순서(Order)'가 핵심 로직인 도메인 문제를 풀기 위함입니다.
• What to Learn:
  • Concepts: 추상 자료형(ADT), LIFO(Last-In First-Out) 스택, FIFO(First-In First-Out) 큐.
  • Skills: 단순 배열 기반 큐에서 발생하는 앞부분 메모리 낭비 문제(Shifting) 인지, 원형 큐(Circular Queue)의 모듈로(%) 연산을 통한 포인터 랩어라운드(Wrap-around).
  • Tools: 스택을 활용한 괄호 매칭, 후위 표기법(Postfix) 수식 계산 로직.
  • Trade-offs: 스택과 큐를 정적 배열로 구현할 때의 최고 속도 보장(단점: 오버플로우 한계) vs 연결 리스트 구현의 무한 확장성(단점: 잦은 메모리 할당/해제 오버헤드).
• How to Learn:
  • 1단계: 미로 찾기 게임에서 DFS 알고리즘이 되돌아올 갈림길 좌표들을 스택 메모리에 Push/Pop 하며 추적하는 논리 흐름을 그림으로 추적합니다.
  • 2단계: 크기가 5인 배열로 큐를 만들고 요소 5개를 넣었다가 3개를 빼면, 앞의 3칸이 비어 있음에도 새 데이터를 넣을 수 없는 '가짜 포화' 상태를 확인하고, 인덱스를 처음으로 돌리는 원형 큐 포인터 로직을 설계합니다.
• Implement: 배열을 활용하되 Front와 Rear 인덱스를 모듈로 연산으로 제어하여 데이터 이동 연산 없는 $O(1)$ 스피드의 원형 큐(Circular Queue) 객체 개발.

Recommended

Core Topic 02: 해싱 물리와 딕셔너리 구조 (Hashing & Maps)

• Why to Learn: 고객 ID 등 수억 개의 유니크한 데이터를 단 한 번의 해시 연산으로 $O(1)$ 즉시 찾아내는 현대 키-값(Key-Value) 데이터베이스의 척추를 세우기 위해서입니다.
• What to Learn:
  • Concepts: 해시 함수(Hash Function), 유니폼 분배(Uniform Distribution), 부하율(Load Factor = 데이터 수 / 버킷 수).
  • Skills: 충돌(Collision) 해결 기법 1: 체이닝(Chaining, 연결 리스트), 충돌 해결 기법 2: 개방 주소법(Open Addressing - 선형/이차 탐사, 이중 해싱).
  • Tools: 실무 해시 라이브러리 소스코드 분석.
  • Trade-offs: 체이닝 기법이 메모리 추가 할당으로 충돌을 우아하게 넘기는 장점 vs 빈 칸을 찾아 나서는 개방 주소법이 메모리를 아끼고 캐시 친화적인 반면 클러스터링(데이터 군집화) 현상으로 탐색 속도가 박살나는 단점 간의 타협.
• How to Learn:
  • 1단계: 해시 함수를 $f(x) = x \bmod 10$으로 정하고 15, 25, 35를 차례대로 넣을 때, 5번 버킷 하나에 3개의 데이터가 주렁주렁 매달려 $O(1)$ 탐색이 $O(N)$으로 파괴되는 과정을 스케치합니다.
  • 2단계: Load Factor가 0.75에 도달할 때 테이블 크기를 두 배로 늘리고 기존의 모든 키를 새 함수로 맵핑(Rehashing)하는 확장 비용 공식을 수학적으로 수립합니다.
• Implement: 임의의 문자열을 해싱하여 인덱스를 산출하고, 충돌 발생 시 해당 버킷에서 단일 연결 리스트를 길게 늘어뜨리는 체이닝(Chaining) 방식 해시 맵 구현.

Practical

Core Topic 03: 계층적 조직과 이진 탐색 트리 (Tree Foundations & BST)

• Why to Learn: 데이터를 단순히 한 줄로 늘어놓지 않고, '크고 작음'에 따라 가지를 뻗어 탐색 범위를 절반씩 줄이는 $O(\log N)$ 성능의 데이터베이스 구조를 얻기 위함입니다.
• What to Learn:
  • Concepts: 루트(Root), 리프(Leaf), 차수(Degree), 트리 높이(Height).
  • Skills: 이진 탐색 트리(BST)의 속성(왼쪽 자식 < 부모 < 오른쪽 자식), 노드 삭제 로직(자식이 2개인 경우 중위 후계자 대체 법칙), 재귀적 트리 순회(In-order로 오름차순 출력하기).
  • Tools: 트리 시각화 유틸리티 및 디버거.
  • Trade-offs: 랜덤하게 입력된 트리(높이 $\log N$)의 환상적 속도 vs 1, 2, 3, 4 순서대로 편향되게 입력되어 한쪽으로 기우러진 링크드 리스트 꼴 트리(Skewed Tree)가 내는 최악의 $O(N)$ 시간.
• How to Learn:
  • 1단계: 임의의 숫자를 차례대로 BST 규칙에 맞춰 노드로 동적 할당하여 그림을 그리고, 탐색 시 루트부터 대소 비교를 통해 하위 서브트리 절반을 버리는 원리를 이해합니다.
  • 2단계: 양쪽 자식이 모두 있는 BST 노드를 삭제할 때, 왼쪽 서브트리의 최댓값 또는 오른쪽 서브트리의 최솟값 노드를 찾아 기존 자리에 복사해 넣는 알고리즘 물리 시퀀스를 훈련합니다.
• Implement: 삽입, 탐색, 그리고 복잡한 후계자 처리 삭제 로직을 모두 지원하는 온전한 이진 탐색 트리(Binary Search Tree) C++ 템플릿.

Advanced

Core Topic 04: 자가 균형 트리의 역학과 우선순위 힙 (Balancing & Heap Priority)

• Why to Learn: 악의적인 입력(이미 정렬된 데이터 삽입)에도 시스템이 다운되지 않도록 트리가 스스로 회전하며 절대적 균형을 유지하고, 우선순위가 높은 데이터를 즉각 뽑아내는 $O(\log N)$ 엔진을 세팅하기 위함입니다.
• What to Learn:
  • Concepts: 자가 균형(Self-balancing), AVL 트리의 Balance Factor(BF), Red-Black 트리의 색칠 규칙, 완전 이진 트리(Complete Binary Tree) 기반의 Max/Min Heap.
  • Skills: LL/RR/LR/RL 4가지 균형 붕괴 케이스에 대한 포인터 회전(Rotation) 스왑 구조, 힙 배열 매핑 인덱스 연산(부모 = $i/2$, 왼쪽 자식 = $2i$), Sift-Up / Sift-Down 역학.
  • Tools: 힙이 활용되는 운영체제 타이머 큐, std::priority_queue.
  • Trade-offs: AVL 트리가 완벽한 좌우 대칭을 고집해 탐색이 빠르지만 잦은 삽입 시 회전 오버헤드가 큰 단점 vs Red-Black 트리가 헐거운 균형 조건을 통해 실무적 삽입/삭제 성능의 최적 스위트스팟을 잡아낸 타협.
• How to Learn:
  • 1단계: 배열 인덱스 1번에 루트를 놓고 자식들을 순서대로 배열에 집어넣는 힙(Heap) 트리에서, 왜 포인터 없이도 상하 노드를 탐색할 수 있는지 배열 메모리 연속성과 결부하여 분석합니다.
  • 2단계: 이진 트리에 데이터 삽입 후 균형 계수(왼쪽 서브트리 높이 - 오른쪽 서브트리 높이)가 2 이상 틀어지는 순간, 조부모-부모-자식 노드 포인터의 결합 방향을 뒤집는 LL/RR 회전 동작을 손으로 그려 추적합니다.
• Implement: 삽입 시 배열 끝에 노드를 추가하고, 부모 값과 비교해 더 크면 재귀적으로 자리를 위로 끌어올리는 Sift-Up 논리가 적용된 최대 힙(Max Heap) 기반 우선순위 큐 작성.

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)인지에 따른 순회 순서 차이를 인지하는가?