자료구조를 고른다는 건 결국 트레이드오프를 고르는 일이다. 어떤 연산을 빠르게 하고 어떤 연산을 포기할지 — 그 판단의 언어가 복잡도이고, 그 선택지가 자료구조다.
1. 복잡도(Complexity): 모든 판단의 기준
자료구조를 배울 때 "이 자료구조는 왜 좋은가"를 판단하는 유일한 잣대가 복잡도다. Big-O를 모르면 배열과 해시맵 중 무엇을 쓸지, 어떤 인덱스가 빠른지 같은 판단이 전부 감에 의존하게 된다.
Big-O는 절대 속도가 아니라 증가율이다
Big-O는 "입력이 커질 때 시간이 어떤 모양으로 늘어나는가"를 나타낸다. 핵심은 절대 속도가 아니라 증가율이라는 점이다.
입력 크기 n이 100일 때, 복잡도별 연산 횟수를 비교하면 격차가 분명해진다.
| 복잡도 | n=10 | n=100 | n=1,000,000 | 대표 예시 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 해시 테이블 조회 |
| O(log n) | ~3 | ~7 | ~20 | 이진 탐색, 균형 트리 |
| O(n) | 10 | 100 | 1,000,000 | 선형 탐색 |
| O(n log n) | ~33 | ~664 | ~2천만 | 효율적인 정렬 |
| O(n²) | 100 | 10,000 | 1조 | 중첩 반복문 |
n=100에서 O(n²)은 1만 번, O(log n)은 고작 7번이다. 이 격차가 자료구조 선택의 거의 전부다. 같은 일을 O(n)으로 하느냐 O(log n)으로 하느냐가, 데이터 100만 개에서 100만 번 대 20번의 차이가 된다.
세 가지 핵심 규칙
1) 상수는 버린다. Big-O는 3n + 5도 100n도 똑같이 O(n)으로 본다. n이 충분히 커지면 증가율만 남고 상수·계수는 무의미해지기 때문이다. 그래서 Big-O는 "알고리즘끼리의 본질적 우열"을 비교하는 도구이지, 실제 밀리초를 재는 도구가 아니다.
2) 최악·평균·최선을 구분한다. 보통 Big-O로 최악의 경우(upper bound)를 말한다. "해시맵 조회는 평균 O(1)이지만 최악 O(n)"이라는 표현이 대표적이다 — 해시 충돌이 한곳에 몰리면 한 버킷에 전부 들어가 선형 탐색이 되기 때문이다.
3) 시간만이 아니라 공간도 본다. O(n)의 추가 메모리를 쓰는 알고리즘과 제자리(in-place, O(1))로 푸는 알고리즘은 다르다. 메모리가 빠듯한 환경에서는 공간 복잡도가 시간만큼 중요하다.
2. 선형 자료구조: 배열 vs 연결 리스트
가장 근본적인 갈림길은 배열과 연결 리스트다. 둘 다 "순서 있는 데이터"를 담지만 메모리 배치가 정반대이고, 그래서 잘하는 일이 정반대다.
배열(Array): 연속된 메모리
배열은 메모리에 한 줄로 붙어 있다(연속 할당). arr[3]에 가고 싶으면 시작주소 + 3 × 원소크기를 한 번 계산하면 바로 그 자리다. 그래서 인덱스 접근이 O(1)이다.
대신 중간에 원소를 끼워 넣으려면 뒤의 모든 원소를 한 칸씩 밀어야 한다 → O(n).
연결 리스트(Linked List): 흩어진 노드
연결 리스트는 노드가 메모리 여기저기에 흩어져 있고, 각 노드가 "다음 노드의 주소(포인터)"를 들고 있다. C에 가려면 A → B → C 순서로 포인터를 따라가야 하므로 접근이 O(n)이다.
대신 삽입·삭제는 포인터 두 개만 고치면 끝난다 → O(1).
요약하면 배열은 "읽기에 강하고 수정에 약하다", 연결 리스트는 정반대다.
캐시라는 반전
이론상 연결 리스트의 O(1) 삽입이 매력적으로 보이지만, 현대 하드웨어에서는 배열이 거의 항상 이긴다. 이유는 CPU 캐시다.
배열은 메모리에 붙어 있어서 CPU가 한 덩어리를 캐시로 미리 끌어오면(cache line) 다음 원소들이 공짜로 따라온다. 연결 리스트는 노드가 흩어져 있어 매번 캐시 미스가 나서 메인 메모리까지 다녀와야 한다. 복잡도 표만으로는 보이지 않는, 자료구조 선택의 숨은 변수다.
3. 자료구조 연산별 복잡도 치트시트
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
|---|---|---|---|---|---|
| 배열 (Array) | O(1) | O(n) | O(n) | O(n) | 인덱스 접근 최강, 캐시 친화적 |
| 동적 배열 (Dynamic Array) | O(1) | O(n) | O(1)* | O(n) | *끝에 추가는 amortized O(1) |
| 연결 리스트 (Linked List) | O(n) | O(n) | O(1) | O(1) | 포인터 위치를 이미 알 때 |
| 스택 / 큐 (Stack / Queue) | O(n) | O(n) | O(1) | O(1) | 한쪽 끝만 다룸 |
| 해시 테이블 (Hash Table) | — | O(1)* | O(1)* | O(1)* | *평균. 최악 O(n) |
| 이진 탐색 트리 (BST) | O(log n)* | O(log n)* | O(log n)* | O(log n)* | *균형 잡혔을 때 |
| 힙 (Heap) | — | O(n) | O(log n) | O(log n) | 최댓값/최솟값 꺼내기 O(1) |
4. 자료구조별 개념 정리
스택(Stack) — LIFO
"마지막에 넣은 걸 먼저 꺼낸다"(Last In First Out). 접시를 쌓았다가 위에서부터 빼는 구조다. 넣기(push)와 빼기(pop)가 한쪽 끝에서만 일어나 둘 다 O(1).
대표 활용: 함수 호출 스택(call stack), 되돌리기(Undo), 괄호 짝 검사, 깊이 우선 탐색(DFS).
큐(Queue) — FIFO
"먼저 넣은 걸 먼저 꺼낸다"(First In First Out). 줄 서기와 같다. 뒤로 들어와서(enqueue) 앞으로 나간다(dequeue).
대표 활용: 메시지 큐, 작업 대기열(job queue), 네트워크 패킷 버퍼, 너비 우선 탐색(BFS).
스택과 큐는 "어느 끝에서 넣고 빼느냐"만 다른 쌍둥이다.
해시 테이블(Hash Table) — 평균 O(1)
키를 해시 함수에 넣어 "배열의 몇 번 칸에 저장할지"를 즉시 계산하는 구조. (자세한 내용은 5장.)
트리(Tree) — 계층 구조
부모-자식 관계로 가지를 뻗는 구조. 특히 이진 탐색 트리(BST)는 "왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 크다"는 규칙을 지켜, 찾을 때마다 후보를 절반씩 버린다 → O(log n).
단, 트리가 한쪽으로 치우치면(unbalanced) O(n)으로 퇴화한다. 그래서 실무에서는 AVL·Red-Black 트리처럼 균형을 강제로 맞추는 변종을 쓴다. 데이터베이스 인덱스에 쓰이는 B-tree/B+tree도 트리의 변형이다.
힙(Heap) — 우선순위 특화
"항상 최댓값(또는 최솟값)이 꼭대기에 오도록" 느슨하게 정렬된 트리. 전체를 정렬하진 않고 "1등만 빠르게 꺼내기"에 특화됐다. 최댓값 꺼내기가 O(1)에 가깝고, 삽입·삭제는 O(log n).
대표 활용: 우선순위 큐(priority queue), 작업 스케줄러, 다익스트라 최단경로 알고리즘.
그래프(Graph) — 가장 일반적인 연결
노드(정점)들이 간선으로 자유롭게 연결된 구조. 트리는 "사이클이 없고 부모가 하나뿐인 특수한 그래프"이고, 그래프는 그 제약이 풀린 일반형이다.
대표 활용: 네트워크 토폴로지, 의존성 그래프, 작업 DAG(방향성 비순환 그래프), 최단 경로·사이클 탐지 문제.
계보 요약: 배열·리스트(선형) → 스택·큐(접근 제한된 선형) → 트리(계층) → 힙(우선순위 특화 트리) → 그래프(일반적 연결). 뒤로 갈수록 표현력이 커지지만 다루기는 복잡해진다.
5. 해시 테이블 심화: O(1)의 비밀
표에서 가장 마법처럼 보이는 줄은 해시 테이블이다 — 탐색·삽입·삭제가 전부 평균 O(1). 데이터가 100만 개든 1억 개든 거의 같은 속도로 찾아낸다.
기본 원리
해시 테이블은 사실 배열이다. 단지 "어느 칸에 넣을지"를 해시 함수로 계산한다는 점이 다르다.
키를 해시 함수에 넣으면 숫자가 나오고, 그 숫자를 배열 크기 N으로 나눈 나머지가 저장 위치(버킷 인덱스)가 된다. 찾을 때도 같은 계산을 하면 단번에 그 칸으로 가므로, 비교 한 번 없이 도착한다.
충돌(Collision)은 반드시 생긴다
해시 함수가 아무리 좋아도, 무한한 키를 유한한 칸에 욱여넣으니 서로 다른 키가 같은 버킷으로 계산되는 일이 반드시 생긴다(비둘기집 원리). 이것이 충돌이다. 처리 방법은 두 가지다.
체이닝(Chaining) — 같은 버킷에 떨어진 키들을 연결 리스트로 매달아 둔다. 찾을 때는 해당 버킷으로 점프한 뒤 그 짧은 리스트만 훑는다. 구현이 단순하고, 충돌이 적으면 리스트가 짧아 여전히 빠르다.
개방 주소법(Open Addressing) — 리스트를 매달지 않고, 충돌이 나면 "옆 칸이 비었나?" 하며 빈 칸을 찾아 들어간다(probing). 모든 데이터가 배열 안에만 있어 캐시 친화적이고 메모리 오버헤드가 적다. 단, 배열이 차오를수록 빈 칸 찾기가 느려진다. 현대 언어들이 성능을 이유로 많이 채택하는 방식이다.
부하율(Load Factor)과 리사이징
부하율 = 저장된 항목 수 ÷ 버킷 수. 이 값이 높아질수록(배열이 꽉 찰수록) 충돌이 급증해 O(1)이 무너진다.
그래서 해시 테이블은 부하율이 임계값(보통 0.7~0.75)을 넘으면 리사이징(rehashing) 을 한다 — 배열을 보통 2배로 늘리고 모든 키를 새 크기로 다시 해시한다. 이 순간만 O(n)이 들지만, 평소의 O(1)을 유지하기 위해 가끔 치르는 비용이다. 동적 배열이 amortized O(1)을 얻는 트릭과 동일한 발상이다.
보안: 해시 충돌 공격(HashDoS)
공격자가 일부러 같은 버킷으로 몰리는 키들을 대량으로 보내, 해시 테이블을 O(n) 리스트로 퇴화시켜 서버를 마비시키는 공격이 있다. 이를 막기 위해 현대 언어들은 매 실행마다 해시 함수에 무작위 시드를 섞는다(예: SipHash). 외부 입력을 받는 시스템이라면 알아둘 가치가 있는 지점이다.
마치며
자료구조는 "데이터를 메모리에 어떻게 배치하느냐"의 서로 다른 선택지다. 그리고 그 선택의 결과는 항상 복잡도라는 공통 언어로 측정된다.
- 배열: 읽기 강함, 수정 약함, 캐시 친화적
- 연결 리스트: 수정 강함, 읽기 약함
- 스택·큐: 접근을 한쪽 끝으로 제한해 단순함과 O(1)을 얻음
- 해시 테이블: 위치를 계산해 평균 O(1), 대가는 충돌 관리와 리사이징
- 트리·힙·그래프: 계층·우선순위·연결이라는 더 복잡한 관계를 표현
다음 글에서는 이 자료구조들 위에서 동작하는 알고리즘 — 정렬은 왜 O(n log n)이 한계인지, 이진 탐색은 어떻게 O(log n)을 얻는지, 그리고 트리·그래프 탐색 — 을 다룬다.
