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

자료구조란

자료구조(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)