자료구조 기초 — 데이터를 담는 그릇들

자료구조란

자료구조(Data Structure)는 데이터를 효율적으로 저장·관리하는 방법입니다. 알고리즘 성능은 자료구조 선택에 따라 결정됩니다.

시간 복잡도 표기 (Big-O):
O(1): 상수 시간 — 크기 무관 즉시 처리
O(log n): 로그 시간 — 이진 탐색
O(n): 선형 시간 — 한 번 순회
O(n²): 제곱 시간 — 버블 정렬

→ 데이터가 1,000개 → 100만 개로 증가할 때:
O(1): 여전히 즉시
O(n): 1,000배 느려짐
O(n²): 100만 배 느려짐

---

배열 (Array)

특성:
→ 연속된 메모리 공간에 데이터 저장
→ 인덱스로 O(1) 랜덤 접근
→ 고정 크기 (정적 배열) or 가변 크기 (동적 배열)

시간 복잡도:
접근: O(1)
탐색: O(n)
삽입(끝): O(1) 평균
삽입(중간): O(n) — 뒤 원소 모두 이동
삭제: O(n) — 이동 필요

사용 시점: 순서 있는 데이터, 인덱스 접근 많을 때

---

연결 리스트 (Linked List)

특성:
→ 노드 = 데이터 + 다음 노드 포인터
→ 메모리 비연속 (동적 할당)

시간 복잡도:
접근: O(n) — 처음부터 순회
삽입/삭제 (알고 있는 위치): O(1)
탐색: O(n)

단순 연결 리스트: 한 방향만 연결
이중 연결 리스트: 앞뒤 모두 연결

사용 시점: 삽입·삭제 빈번, 크기 예측 불가

---

스택 (Stack) & 큐 (Queue)

스택 (LIFO — Last In First Out):
→ 후입선출 — 마지막에 넣은 것이 먼저 나옴
연산: push(넣기), pop(빼기), peek(확인)
시간 복잡도: 모든 연산 O(1)

사용 예:
→ 브라우저 뒤로가기 (방문 기록 스택)
→ 함수 호출 스택 (재귀)
→ 괄호 유효성 검사

큐 (FIFO — First In First Out):
→ 선입선출 — 먼저 넣은 것이 먼저 나옴
연산: enqueue(넣기), dequeue(빼기)
시간 복잡도: O(1)

사용 예:
→ 프린터 작업 대기열
→ 너비 우선 탐색(BFS)
→ CPU 프로세스 스케줄링

---

해시 테이블 (Hash Table)

원리:
키(Key) → 해시 함수 → 인덱스 → 값(Value) 저장

시간 복잡도:
삽입·삭제·탐색: 평균 O(1) ← 가장 큰 장점
최악 (충돌 많을 때): O(n)

해시 충돌 해결:
체이닝: 같은 인덱스에 연결 리스트
개방 주소법: 빈 슬롯 찾아서 이동

사용 예:
→ 언어별 딕셔너리/맵 (Python: dict, JS: Object/Map)
→ 캐시 (브라우저 캐시, Redis)
→ 데이터베이스 인덱스

---

트리 (Tree)

구조:
루트(Root) → 부모-자식 계층 관계
노드: 데이터 + 자식 포인터
리프(Leaf): 자식 없는 말단 노드

이진 트리: 자식이 최대 2개
이진 탐색 트리(BST):
→ 왼쪽 자식 < 부모 < 오른쪽 자식
→ 탐색·삽입·삭제: O(log n) 평균

균형 잡힌 트리 (AVL, Red-Black):
→ O(log n) 보장
→ 데이터베이스 인덱스에 활용

힙(Heap):
→ 완전 이진 트리
→ 최대 힙: 부모 ≥ 자식 (루트 = 최댓값)
→ 우선순위 큐, 힙 정렬에 활용

---

자료구조 선택 가이드

상황	최적 자료구조
빠른 인덱스 접근	배열
빈번한 삽입·삭제	연결 리스트
후입선출 (되돌리기)	스택
선입선출 (대기열)	큐
키-값 빠른 조회	해시 테이블
정렬된 데이터 탐색	BST / 균형 트리
최솟값·최댓값 빠른 접근	힙

---

핵심 암기 포인트

배열: O(1) 접근, 삽입·삭제 O(n) / 연결리스트: 접근 O(n), 삽입·삭제 O(1) 스택 LIFO (뒤로가기) / 큐 FIFO (대기열) 해시 테이블: 평균 O(1) 탐색 — 캐시, 딕셔너리의 핵심 BST: 왼쪽<부모<오른쪽 → 탐색 O(log n)