핵심 인사이트

  1. 본질: 자료구조는 데이터를 효율적으로 저장하고 접근하기 위해 조직화된 구조이며, 각 구조는 특정 작업(삽입, 삭제, 탐색)에서 서로 다른 성능 특성을 갖는다.
  2. 가치: 적절한 자료구조 선택은 알고리즘 성능을 결정적으로 좌우하며, 부적절한 선택은即使是 정렬된 알고리즘도非효율적으로 만든다.
  3. 융합: 운영체제의 프로세스 관리, 파일 시스템, 네트워크 프로토콜 등 시스템 소프트웨어 전반에서 기본 자료구조가 활용된다.

Ⅰ. 개요 및 필요성

개념 정의

자료구조란 데이터를 효율적으로 저장, 검색, 조작하기 위해 컴퓨터에서 데이터를 조직화하는 방식이다. 자료구조의 선택은 알고리즘의 시간 복잡도와 공간 복잡도에 직접적인 영향을 미치며, 프로그램의 성능을 결정하는 핵심 요소다.

알고리즘이 "문제를解く 방법"이라면, 자료구조는 "データを保存する形式"에 해당한다. 동일한 알고리즘이라도 자료구조가 다르면 성능이 크게 달라질 수 있다. 예를 들어 해시 테이블에서 탐색하면 O(1)이 소요되고, 배열에서는 O(n)이 필요할 수 있다.

왜 자료구조 선택이 중요한가

실무에서 좋은 자료구조 선택의 중요성을 보여주는 사례를 생각해보자. 100만 개의 데이터에서 특정 값 찾기를 생각해보자. 배열에서는 O(n)이 필요한 반면, 균형 이진 탐색 트리에서는 O(log n)이면 충분하다. 이것은 100만 번의 비교와 약 20번의 비교의 차이다.

또한, 탐색뿐 아니라 삽입과 삭제 작업의 빈도수도 자료구조 선택에 영향을 미친다. 해시 테이블은 탐색과 삽입이 O(1)으로 매우 빠르지만, 순서 보존이 되지 않는다. 반면 이진 탐색 트리는 O(log n)로 상대적으로 느리지만, 순서가 유지되고 범위 질의에 효율적이다.

자료구조 발전 과정

[자료구조 발전 타임라인]

1960년대 이전: 배열, 연결 리스트
  ↓
1960년대: 스택, 큐, 트리 개념 정립
  ↓
1970년대: 이진 탐색 트리, AVL 트리
  ↓
1978년: B-Tree (바이어, 맥크레이거) - 디스크 기반 저장소 최적화
  ↓
1980년대: 해시 테이블, 레드-블랙 트리의 구현 및 표준화
  ↓
1990년대: 스킵 리스트, 트립 등 난수 기반 자료구조
  ↓
2000년대~현재: 레디스 자료구조, LSM 트리, 분산 해시 테이블

[다이어그램 해설] 자료구조의 발전은 하드웨어 특성과 응용 프로그램 요구사항의 변화에 맞춰 진행되어 왔다. 디스크 기반 저장소가 등장하면서 B-Tree가, 네트워크 통신에서 순서 보존이 중요해지면서 연결 리스트가 발전했다. 현대의 LSM 트리는 쓰기 성능을 높이기 위해 설계되었으며, 이는 SSD의 특성(순차 쓰기 빠름, 랜덤 쓰기 느림)과 맞물린다.

📢 섹션 비유

자료구조는 도서관의 장서 관리 방식과 같다. 책장을 분류별로 정리하면 원하는 책을 빠르게 찾을 수 있지만, 새로운 책을 끼워넣을 때 위치를 찾아야 하는 수고가 든다. 반면 아무렇게나 쌓아두면 삽입은 빠르지만 찾기가 오래 걸린다. 컴퓨터의 자료구조도 마찬가지로, 저장 방식에 따라 탐색, 삽입, 삭제의 효율성이 달라진다.

Ⅱ. 아키텍처 및 핵심 원리

자료구조 분류 체계

자료구조는 다양한 기준으로 분류되며, 각 유형은 서로 다른 작업에서 효율적이다. 크게 선형 자료구조, 비선형 자료구조, 해시 기반 자료구조로 나눌 수 있다.

┌────────────────────────────────────────────────────────────────┐
│                    자료구조 분류 체계                            │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  [선형 자료구조]                                                │
│       │                                                        │
│       ├── 정적: 배열 (고정 크기)                                │
│       │                                                        │
│       └── 동적: 연결 리스트, 스택, 큐, 데크                      │
│           │                                                   │
│           ├── 단일 연결 리스트                                  │
│           ├── 이중 연결 리스트                                  │
│           ├── 원형 연결 리스트                                  │
│           └── 자유 연결 리스트                                  │
│                                                                │
│  [비선형 자료구조]                                              │
│       │                                                        │
│       ├── 트리 계열                                            │
│       │    ├── 이진 트리                                      │
│       │    ├── 이진 탐색 트리                                  │
│       │    ├── 균형 탐색 트리 (AVL, 레드-블랙)                 │
│       │    ├── B-Tree / B+ Tree                               │
│       │    ├── 힙 (최대/최소 힙)                              │
│       │    └──Trie (접두사 트리)                              │
│       │                                                        │
│       └── 그래프 계열                                          │
│            ├── 방향/무방향 그래프                               │
│            ├── 가중치/비가중치 그래프                            │
│            └── 인접 행렬/목록 표현                              │
│                                                                │
│  [해시 기반 자료구조]                                           │
│       │                                                        │
│       ├── 해시 테이블 (분리 연결, 개방 주소법)                    │
│       ├── 해시 맵                                              │
│       └── 블룸 필터 (확률적)                                   │
│                                                                │
└────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 자료구조 선택의 핵심은 작업의 종류와 빈도를 분석하는 것이다. 탐색이 주요 작업이면 해시 테이블 또는 균형 이진 탐색 트리가 적합하고, 순서 보존이 필요하면 트리 기반 구조가 적합하다. 삽입과 삭제가 빈번하면 연결 리스트가 유리하고, 범위 질의가 필요하면 B+ 트리가 최적이다.

배열과 연결 리스트의 비교

배열과 연결 리스트는 가장 기본적인 선형 자료구조이며, 서로 다른 성능 특성을 갖는다. 연속 메모리 vs 노드 기반이라는 근본적인 구조적 차이가 성능을 결정한다.

┌────────────────────────────────────────────────────────────────┐
│              배열 vs 연결 리스트 비교                            │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  [배열 (Array)]                                                │
│  ─────────────────────────                                    │
│  인덱스:  0    1    2    3    4    5                           │
│  값:    [10 | 20 | 30 | 40 | 50 | 60]                         │
│          ▲                                                   │
│        기본 주소 + 인덱스 × 요소 크기 → O(1) 접근                   │
│                                                                │
│  메모리 배치: 연속적인 영역                                     │
│  접근: O(1) | 탐색: O(n) [순차] / O(log n) [이분 탐색, 정렬済み]│
│  삽입: O(n) | 삭제: O(n)                                      │
│                                                                │
│  [연결 리스트 (Linked List)]                                   │
│  ─────────────────────────                                    │
│  구조: 노드 = 데이터 + 다음 노드 포인터                         │
│                                                                │
│  ┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐                 │
│  │  10  │ → │  20  │ → │  30  │ → │  40  │ → NULL           │
│  │ 노드1 │    │ 노드2 │    │ 노드3 │    │ 노드4 │               │
│  └──────┘    └──────┘    └──────┘    └──────┘                 │
│                                                                │
│  메모리 배치: 불연속적인 영역 (포인터로 연결)                    │
│  접근: O(n) | 탐색: O(n)                                      │
│  삽입: O(1) | 삭제: O(1) (위치 파악 후)                       │
│                                                                │
│  [시간 복잡도 비교표]                                          │
│  ─────────────────────────                                    │
│  작업       │ 배열   │ 단일 연결 리스트 │ 이중 연결 리스트        │
│  ──────────┼────────┼────────────────┼──────────────────     │
│  접근       │ O(1)   │ O(n)           │ O(n)                │
│  탐색       │ O(n)   │ O(n)           │ O(n)                │
│  선두 삽입  │ O(n)   │ O(1)           │ O(1)                │
│  선두 삭제  │ O(n)   │ O(1)           │ O(1)                │
│  끝 삽입   │ O(1)   │ O(n)           │ O(1)*               │
│  순회       │ O(n)   │ O(n)           │ O(n)                │
│  ──────────────────────────────────────────────────────────── │
│  * 끝 포인터 유지 시                                             │
│                                                                │
└────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 배열은 연속된 메모리 공간에 데이터를 저장하므로 인덱스를 통한 O(1) 접근이 가능하지만, 크기 변경이 어렵고 삽입/삭제 시 요소 이동이 필요하다. 반면 연결 리스트는 노드를 동적으로 할당하고 포인터로 연결하므로 삽입/삭제가 O(1)에 가능하지만, 인덱스 접근이 O(n)이고追加的なポ인터 저장 공간이 필요하다. 실무에서는 하이브리드 접근으로, 예를 들어 연결 리스트의 노드에 배열을 조합하는 자료구조도 사용된다.

스택과 큐의 내부 동작

스택과 큐는 특별한 접근 방식(각각 LIFO, FIFO)을 갖는 추상 자료구조다. 이들은 알고리즘 구현에서基本的な 역할을 한다.

[스택 (Stack) 동작]

  LIFO: Last In, First Out
  ─────────────────────────
  주요 연산: push (삽입), pop (삭제), peek (최상단 확인)

  상태 변화:
  ─────────────────────────
  초기: []
  push(1): [1]
  push(2): [1, 2]
  push(3): [1, 2, 3]
  pop(): [1, 2] → 반환값 3
  pop(): [1] → 반환값 2
  peek(): [1] → 반환값 2 (삭제 없이 확인만)

  활용 예시:
  - 함수 호출 스택 (재귀)
  - 괄호 매칭
  - 실행 취소/다시 실행 기능
  - 깊이 우선 탐색


[큐 (Queue) 동작]

  FIFO: First In, First Out
  ─────────────────────────
  주요 연산: enqueue (삽입), dequeue (삭제), front (앞쪽 확인)

  상태 변화:
  ─────────────────────────
  초기: []
  enqueue(1): [1]
  enqueue(2): [1, 2]
  enqueue(3): [1, 2, 3]
  dequeue(): [2, 3] → 반환값 1
  dequeue(): [3] → 반환값 2
  front(): [3] → 반환값 3 (삭제 없이 확인만)

  활용 예시:
  - 너비 우선 탐색
  - 작업 스케줄링
  - 프린터 대기열
  - 메시지 큐


[데크 (Double-Ended Queue)]

  양쪽 끝에서 삽입/삭제가 가능한 큐
  ─────────────────────────
  ┌──────────────────────────────────────┐
  │ .front() │       데이터       │ .back()  │
  └──────────────────────────────────────┘
        │                        │
        └──── enqueue_front() ────┘
        └──── dequeue_front() ────┘
        └──── enqueue_back()  ────┘
        └──── dequeue_back()  ────┘

  활용: 슬라이딩 윈도우, 알고리즘의 양방향 탐색

[다이어그램 해설] 스택은 "쌓아올린 접시"와 같이 나중에 올린 것이 먼저 내려간다. 이 특성 때문에 재귀 호출, 함수 호출 스택, 괄호 매칭에天然適合한다. 큐는 "대기줄"과 같이 먼저 온 것이 먼저 서비스받는다. 너비 우선 탐색, 작업 스케줄링, 너비 우선 탐색에 필수적이다. 데크는 양쪽 끝에서의 작업이 모두 O(1)이므로, 슬라이딩 윈도우 알고리즘이나 양방향 탐색에 효율적이다.

해시 테이블의 충돌 해결

해시 테이블은 키를 해시 함수로 변환하여 데이터에 직접 접근하는 자료구조다. 그러나異なる 키가 동일한 해시 값을 가질 수 있으며, 이를 충돌이라고 한다. 충돌 해결 방법은 크게 분리 연결법과 개방 주소법으로 나눌 수 있다.

[해시 테이블 충돌 해결 방법]

  1. 분리 연결법 (Separate Chaining)
  ─────────────────────────────────────
  해시 버킷: 각 버킷이 연결 리스트의 헤드
  ┌─────┬─────┬─────┬─────┬─────┐
  │  0  │  1  │  2  │  3  │  4  │  ...
  ├─────┼─────┼─────┼─────┼─────┤
  │ [A] │[B,C]│ [D] │ [E] │     │
  │     │ ↓   │     │     │     │
  │     │[C]  │     │     │     │
  └─────┴──┬──┴─────┴─────┴─────┘
           └── 해시 충돌 시 연결 리스트로 추가

  장점: 충돌이 많으면 성능 저하가緩やか
  단점:追加的な 연결 리스트 저장 공간 필요


  2. 개방 주소법 (Open Addressing)
  ─────────────────────────────────────
  충돌 시 다른 빈 버킷을 탐색하여 삽입

  ┌─────────────────────────────┐
  │  탐색 방법                  │
  │  ─────────────────────────  │
  │  선형 탐사: h(k)+i         │
  │  이차 탐사: h(k)+i제곱│
  │  이중 해시: h1(k)+i*h2(k)  │
  └─────────────────────────────┘

  예시 (선형 탐사):
  해시 함수: h(key) = key mod 7

  삽입 과정:
  - key=15 → h(15)=1 → 버킷 1이 비어있음 → 삽입
  - key=22 → h(22)=1 → 버킷 1 사용중 → 버킷 2 탐색 → 빈 버킷 발견 → 삽입
  - key=8  → h(8)=1 → 버킷 1 사용중 → 2 사용중 → 3 탐색 → 빈 버킷 발견 → 삽입

[다이어그램 해설] 분리 연결법은 각 버킷을 연결 리스트로 관리하여 충돌을 처리한다. 삽입은 O(1)이고, 탐색은链表 길이에 따라 다르다. 평균적으로链表 길이가 알파=n/m(적재 밀도)일 때 탐색은 O(1+알파)이다. 개방 주소법은 충돌 시 다른 버킷을 탐색하므로追加的な配列空間이 필요하지만, 연결 리스트가 없어 메모리 효율적이다. 그러나 적재 밀도가 높으면 탐색 비용이 급격히 증가하므로, 일반적으로 적재 밀도가 0.7을 넘으면 리해싱이 필요하다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: 균형 이진 탐색 트리 비교 (AVL vs 레드-블랙)

비교 항목AVL 트리레드-블랙 트리
균형 조건左右 높이의 차이가 1 이하경로의 블랙 노드 수가 같음
삽입/삭제 비용회전 많아서 비쌈회전 적어서 쌈
탐색 성능더 균형 → 더 빠름AVL보다 약간 느림
활용场景탐색 위주삽입/삭제 빈번
예시데이터베이스 인덱스C++ STL map, Java TreeMap

비교 2: 힙 vs 이진 탐색 트리

┌────────────────────────────────────────────────────────────────┐
│                 힙 vs 이진 탐색 트리 비교                        │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  [최대 힙]              [이진 탐색 트리 (오름차순)]             │
│                                                                │
│          9                       5                              │
│        /    \                   /   \                          │
│       7      8                 3     7                          │
│      /  \   /  \             /  \    \                         │
│     5    6 4    3           1    4    9                         │
│                                                                │
│  힙 특성:                  BST 특성:                          │
│  - 부모 ≥ 자식 (최대 힙)   - 왼쪽 ≤ 부모 ≤ 오른쪽               │
│  - 완전 이진 트리           - 반드시 이진 트리 아님               │
│  - 배열로 효율적 표현        - 인오더 순회하면 정렬됨            │
│                                                                │
│  연산 복잡도:                                                │
│  ────────────────────────────────                              │
│              │ 힙       │ BST (균형)   │ BST (비균형)          │
│  탐색        │ O(n)     │ O(log n)    │ O(n)                 │
│  삽입       │ O(log n) │ O(log n)    │ O(n)                 │
│  삭제 (최대값)│ O(log n) │ O(log n)    │ O(n)                 │
│  최소/최대값  │ O(1)      │ O(log n)    │ O(n)                 │
│                                                                │
│  활용场景:                                                  │
│  - 힙: 우선순위 큐, 힙 정렬, 최단 경로 (다익스트라)                │
│  - BST: 정렬된 데이터 관리, 범위 질의, 사전 구조                  │
│                                                                │
└────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 힙과 BST는 비슷해 보이지만根本적으로 다른 자료구조다. 힙은 "부모가 항상 크다(또는 작다)"는 속성만 유지하면 되므로 삽입과 삭제 모두 O(log n)으로 유지보수가 쉽고, 특히 최댓값 또는 최솟값 접근이 O(1)이다. 그러나 탐색은 O(n)이므로 특정 값 찾기에는 부적합하다. 반면 BST는 왼쪽 하위 트리의 모든 값이 부모보다 작고, 오른쪽 하위 트리의 모든 값이 부모보다 크다는 이진 탐색 속성을 유지하므로 탐색, 삽입, 삭제 모두 O(log n)(균형 상태)에서 가능하다.

운영체제와의 융합

운영체제에서 프로세스 관리를 위해 다양한 자료구조가 활용된다. 우선순위 큐는 프로세스 스케줄링에, 연결 리스트는 프로세스 제어 블록 관리에, 해시 테이블은 열린 파일 관리에 사용된다.

[운영체제에서의 자료구조 활용]

  프로세스 스케줄링 (우선순위 큐 / 힙)
  ─────────────────────────────────────
  운영체제 커널
       │
       ▼
  [실행 대기 큐: 최소 힙]
  ┌────────────────────────────────┐
  │ 우선순위  │ 프로세스  │ 도착 시간 │
  ├───────────┼──────────┼──────────┤
  │    1     │  P1     │   T1    │
  │    3     │  P2     │   T2    │
  │    5     │  P3     │   T3    │
  └───────────┴──────────┴──────────┘
  → 항상 가장 높은 우선순위 프로세스가 선택됨

  파일 디스크립터 관리 (해시 테이블)
  ─────────────────────────────────────
  fd 0 ──→ 표준 입력
  fd 1 ──→ 표준 출력
  fd 2 ──→ 표준 오류
  fd 3 ──→ "file.txt" 파일
  → 해시 테이블로 O(1) 접근

[다이어그램 해설] 운영체제의 프로세스 스케줄러는 실행 대기 중인 프로세스 중 가장 높은優先순위 프로세스를 선택해야 한다. 최소 힙을 사용하면優先순위 추출이 O(1), 새 프로세스 삽입이 O(log n)이라 매우 효율적이다. 리눅스의 CFS(완전 공정 스케줄러)에서는 레드-블랙 트리를 사용하여 공정 스케줄링을 구현한다.

Ⅳ. 실무 적용 및 기술사적 판단

실무 시나리오

시나리오 1: 데이터베이스 인덱스와 B+ 트리

관계형 데이터베이스에서 인덱스는 B+ 트리 자료구조로 구현되는 것이 표준이다. B+ 트리는 디스크 기반 저장소에 최적화된 자료구조로, 대량 데이터에서 O(log n) 탐색을 보장한다.

[B+ 트리 구조]

        [ 50 | 100 ]
           /    \
      [20|30]    [70|80|90|110]
        /\          /|\
      ...  ...    ... ...

  B+ 트리 특징:
  ─────────────────────────────
  1. 모든 리프 노드가同一深度에 존재
  2. 리프 노드는연결 리스트로 연결 (순차 접근 용이)
  3. 내부 노드는인덱스만 저장 (리프에 대한 포인터)
  4. 디스크 블록 크기에 최적화된 높이다.

  예: 100만 레코드, 블록 크기 4KB, 요소 크기 10바이트
  → 각 노드에 약 400개 포인터
  → 트리 높이: 약 log_400(1,000,000) ≈ 3
  → 최대 3번의 디스크 접근으로任意 레코드 탐색 가능

[다이어그램 해설] B+ 트리가 데이터베이스 인덱스로 사용되는 이유는 디스크 접근 횟수를 최소화할 수 있기 때문이다. 각 노드의 크기가 디스크 블록 크기에 맞춰져 있어, 한 번의 디스크 읽기로 여러 포인터를 읽을 수 있다. 또한 리프 노드들이 연결 리스트로 연결되어 있어 범위 질의(100번부터 200번 사이 찾기)가 매우 효율적이다.

시나리오 2: 캐시 구현과 LRU (가장 오래 전에 사용된 것 제거)

컴퓨터 구조의 캐시 메모리 관리를 위해 LRU 알고리즘이 사용된다. 해시 테이블과 이중 연결 리스트를 조합하여 O(1) 시간에 LRU 캐시 연산을 구현할 수 있다.

[LRU 캐시 구현]

  ┌─────────────────────────────────────────────┐
  │            LRU 캐시 구조                      │
  ├─────────────────────────────────────────────┤
  │                                              │
  │  [해시 테이블]        [이중 연결 리스트]       │
  │  ────────        ────────────────────        │
  │  key → node      HEAD ↔ [A] ↔ [B] ↔ [C] ↔ TAIL
  │                      newest      oldest      │
  │                                              │
  │  접근/삽입 시:                                │
  │  1. 해시 테이블에서 노드 탐색: O(1)               │
  │  2. 연결 리스트에서 노드 이동: O(1)          │
  │  3. 캐시 용량 초과 시 TAIL에서 제거: O(1)    │
  │                                              │
  └─────────────────────────────────────────────┘

[다이어그램 해설] LRU 캐시에서 가장 중요한 것은 "최근 사용 여부"를 추적하는 것이다. 해시 테이블만 있으면 탐색은 O(1)지만, "가장 오래 사용되지 않은 것"을 찾는 작업이 O(n)이 된다. 반면 해시 테이블과 이중 연결 리스트를组合하면, 해시 테이블로 O(1) 탐색하고 연결 리스트로 O(1) 이동/삽입/삭제가 가능하다. 이것은 웹 캐시, CPU 캐시, CDN 캐시 등 다양한 곳에서 활용된다.

도입 체크리스트

  • 주요 작업(탐색, 삽입, 삭제)의 빈도수를 분석했는가?
  • 데이터 크기와 메모리 제약을 파악했는가?
  • 순서 보존이 필요한가?
  • 동시 접근(멀티 스레드)이 있는가?
  • 키의 분포에偏りがあるか?

안티패턴

  • 비균형 BST: 입력 데이터가 정렬된 상태에서 BST에 삽입하면 모든 노드가 한쪽으로偏って 성능이 O(n)으로 저하된다.
  • 적재 밀도 무시: 해시 테이블의 적재 밀도가 0.9를 넘어서면 충돌이 급격히 증가한다.
  • 불필요한 균형: 데이터가 거의 변경되지 않는다면 균형 유지 비용이 불필요할 수 있다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분내용비고
정량배열에서 해시 테이블로 (키당 탐색)O(n)에서 O(1)로
정량비균형 BST에서 AVL 트리로O(n)에서 O(log n)로
정성자료구조 선택으로 캐시 적중률 향상시스템 성능 개선

미래 전망

자료구조 연구는 세 가지 방향으로 발전하고 있다. 첫째, 지속적 자료구조(변경 사항이 원본에 영향을 주지 않는 자료구조)가 함수형 프로그래밍에서 중요하다. 둘째, 외부 메모리 자료구조가 대규모 데이터 처리의 필수 요소가 되고 있다. 셋째, 임베디드 시스템을 위한 저전력 자료구조가 연구되고 있다.

관련 표준

  • STL (표준 템플릿 라이브러리): C++의 표준 자료구조库
  • Java Collections Framework: Java의 표준 자료구조 및 알고리즘
  • Python 내장 타입: list, dict, set, tuple 등

📌 관련 개념 맵

개념 명칭관계 및 시너지 설명
해시 함수해시 테이블의核心으로, 좋은 해시 함수는 충돌을最少化する。
균형 트리AVL, 레드-블랙 트리 등 높이를 유지하여 O(log n) 성능을 보장하는 트리
우선순위 큐힙으로 구현되며, 다익스트라, 프라임 등 그래프 알고리즘의核心 구성요소이다
Trie문자열 접두사 탐색에 최적화된 트리 자료구조, IP 라우팅 표에 활용된다
블룸 필터확률적 자료구조로, 원소 존재 여부를 확률적으로 판단하며 메모리를 절약한다

👶 어린이를 위한 3줄 비유 설명

  1. 자료구조는 장난감 상자를 정리하는 방법과 같아요. 크기순으로 정리하면 큰 장난감을 찾기 쉽고, 색깔별로 정리하면 같은 색 찾기 쉬워요. 컴퓨터도 데이터를 어떻게 정리하느냐에 따라 찾는 속도가 달라져요!

  2. 해시 테이블은 마치 학번으로 학생을 찾는 것과 같아요. "203번 학생"하면 바로 행으로 가면 되지만, "이름이 김철수인 학생"하면 하나하나 찾아봐야 해요.

  3. 그런데 가장 좋은 정리법은 없어요. 새로 넣을 때는 아무렇게나 쌓아두는 게 빠르지만, 찾을 때는 분류가 필요하거든요. 그래서場合마다 다른 자료구조를 써야 해요!

📈 관련 키워드 및 발전 흐름도

선형 자료구조
    ├─► 배열 (Array) — O(1) 접근, O(n) 삽입/삭제
    ├─► 연결 리스트 (Linked List) — O(n) 접근, O(1) 삽입/삭제
    ├─► 스택 (Stack) — LIFO
    └─► 큐 (Queue) — FIFO; 덱(Deque) 포함
    │
    ▼
비선형 자료구조
    ├─► 트리 (BST → AVL → Red-Black Tree → B-Tree)
    ├─► 힙 (Heap) — 우선순위 큐
    └─► 해시 테이블 (Hash Table) — O(1) 평균
    │
    ▼
고급 자료구조
    ├─► 트라이 (Trie) — 문자열 검색
    ├─► 세그먼트 트리 — 구간 질의
    └─► 유니온-파인드 (Union-Find) — 분리 집합