📌 자료구조 치트시트: 시간복잡도와 공간복잡도 완벽 정리

📌 자료구조 치트시트: 시간복잡도와 공간복잡도 완벽 정리

서론

자료구조는 알고리즘의 성능을 좌우하는 핵심 요소입니다. 같은 문제라도 어떤 자료구조를 선택하느냐에 따라 시간 복잡도와 공간 복잡도가 크게 달라집니다.
이번 글에서는 배열, 연결 리스트, 해시 테이블, 스택, 큐, 데크, 트리, 이진 트리, 힙, 그래프를 중심으로, 각 자료구조의 특성과 시간·공간 복잡도를 한눈에 볼 수 있는 치트시트를 제공합니다.
이 글을 읽고 나면 코딩 테스트뿐 아니라 실무 프로젝트에서도 최적의 자료구조를 선택할 수 있는 기준을 갖추게 될 것입니다.

---

본론

1. 주요 자료구조 개요 및 시간·공간 복잡도

다음 표는 각 자료구조의 평균적인 연산 복잡도를 요약한 것입니다.

자료구조	접근(Access)	검색(Search)	삽입(Insert)	삭제(Delete)	공간복잡도
배열(Array)	O(1)	O(n)	O(n)	O(n)	O(n)
연결 리스트(Linked List)	O(n)	O(n)	O(1) (head/tail 기준)	O(1) (head/tail 기준)	O(n)
해시 테이블(Hash Table)	N/A	O(1) (평균) / O(n) (최악)	O(1) / O(n)	O(1) / O(n)	O(n)
스택(Stack)	O(n)	O(n)	O(1)	O(1)	O(n)
큐(Queue)	O(n)	O(n)	O(1)	O(1)	O(n)
데크(Deque)	O(n)	O(n)	O(1)	O(1)	O(n)
트리(Tree)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
이진 탐색 트리(BST, Balanced)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
힙(Heap)	O(n)	O(n)	O(log n)	O(log n)	O(n)
그래프(Graph)	O(1)~O(n)	O(1)~O(n)	O(1)~O(n)	O(1)~O(n)	O(V+E)

---

2. 자료구조별 특징과 예제 코드

📌 배열 (Array)

• 특징: 인덱스를 통한 빠른 접근 가능, 크기 고정(언어에 따라 동적 배열 지원).
• 사용 예시: 데이터 크기가 고정적이고 빠른 랜덤 접근이 필요한 경우.

# 파이썬 배열(리스트) 예제
arr = [1, 2, 3]
arr.append(4)   # O(1) 평균
arr.insert(1, 5)  # O(n)
print(arr[2])   # O(1)

📌 연결 리스트 (Linked List)

• 특징: 노드 기반으로 동적 크기 조절 가능, 삽입/삭제 O(1) (위치 알고 있을 경우), 랜덤 접근 불가.
• 사용 예시: 삽입/삭제가 빈번한 경우.

// Java LinkedList 예제
import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // O(1)
list.addLast(2);  // O(1)
list.removeFirst(); // O(1)

📌 해시 테이블 (Hash Table)

• 특징: 평균적으로 O(1) 검색·삽입·삭제, 해시 충돌 시 성능 저하 가능.
• 사용 예시: 키-값 매핑 필요 시.

// JavaScript Map 예제
const map = new Map();
map.set('apple', 3); // O(1)
console.log(map.get('apple')); // O(1)

📌 스택 (Stack)

• 특징: LIFO 구조, 함수 호출 스택, Undo 기능 구현 등에 활용.
• 사용 예시: DFS, 괄호 유효성 검사.

stack = []
stack.append(1)  # push O(1)
stack.append(2)
print(stack.pop()) # pop O(1)

📌 큐 (Queue)

• 특징: FIFO 구조, 순차 처리 작업에 활용.
• 사용 예시: BFS, 대기열 시스템.

from collections import deque
queue = deque()
queue.append(1)   # enqueue O(1)
queue.append(2)
print(queue.popleft())  # dequeue O(1)

📌 데크 (Deque)

• 특징: 양쪽 끝에서 삽입/삭제 가능.
• 사용 예시: 슬라이딩 윈도우, 양방향 탐색.

dq = deque()
dq.appendleft(1) # O(1)
dq.append(2)     # O(1)
dq.pop()         # O(1)

📌 트리 (Tree) & 이진 탐색 트리 (BST)

• 특징: 계층적 데이터 구조, 이진 탐색 트리는 정렬 데이터 관리에 유리.
• 사용 예시: DB 인덱스, 계층적 구조 표현.

// 간단한 BST 삽입 예제
class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

Node insert(Node root, int value) {
    if (root == null) return new Node(value);
    if (value < root.value) root.left = insert(root.left, value);
    else root.right = insert(root.right, value);
    return root;
}

📌 힙 (Heap)

• 특징: 최대값 또는 최소값을 빠르게 꺼낼 수 있는 자료구조.
• 사용 예시: 우선순위 큐 구현.

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
print(heapq.heappop(heap)) # 1

📌 그래프 (Graph)

• 특징: 정점(Vertex)과 간선(Edge)으로 구성, 네트워크 및 경로 탐색에 사용.
• 사용 예시: SNS 관계, 경로 탐색 알고리즘.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

---

결론

이 글에서는 자료구조의 핵심 개념과 시간·공간 복잡도를 한눈에 볼 수 있도록 정리했습니다.
자료구조 선택은 성능 최적화의 첫걸음이며, 이를 정확히 이해하면 문제 해결 능력이 크게 향상됩니다.

💡 당신이 올바른 자료구조를 선택하는 순간, 성능 최적화의 절반은 이미 끝난 것입니다.