0. 자료구조란?
자료구조는 데이터를 저장하고 접근하는 방식을 정의한 구조이다. 같은 데이터라도 어떻게 배치하고 연결하느냐에 따라 조회/삽입/삭제/정렬의 비용이 달라진다.
- 선형 자료구조: 배열, 연결 리스트처럼 데이터가 순차적인 관계를 가진다.
- 비선형 자료구조: 트리처럼 데이터가 계층적인 관계를 가진다.
- 추상 자료형 ADT: 무엇을 할 수 있는지를 정의한다. 예를 들어 List, Map, Set, Queue가 있다.
- 자료구조: ADT를 실제로 구현하는 방법이다. 같은 List도 배열이나 연결 리스트로 구현할 수 있다.
시간 복잡도
- O(1): 데이터 개수와 무관하게 일정한 횟수의 연산이 필요하다.
- O(log n): 탐색 범위가 단계마다 일정 비율로 줄어든다.
- O(n): 데이터 개수에 비례해 확인해야 한다.
- 평균 복잡도: 일반적인 입력 분포를 가정했을 때의 비용이다.
- 최악 복잡도: 가장 불리한 입력에서의 비용이다.
- 분할 상환 복잡도: 여러 연산의 총비용을 연산 수로 나눈 장기적인 평균 비용이다.
공간 복잡도
공간 복잡도는 입력 크기 n이 증가할 때 프로그램이나 자료구조가 필요로 하는 메모리의 증가량을 나타낸다.
그림: 전체 공간과 보조 공간의 포함 관계
전체 공간과 보조 공간
- 전체 공간 복잡도: 입력 데이터 자체를 저장하는 공간과 실행 중 추가로 사용하는 공간을 모두 포함한다.
- 보조 공간 복잡도 Auxiliary Space: 입력 데이터 저장 공간을 제외하고 알고리즘이 추가로 사용하는 메모리만 계산한다. 예를 들어 길이 n인 배열을 새 배열에 복사하는 알고리즘은 입력과 결과를 포함하면 O(n)의 공간을 사용하며, 새 배열을 추가 공간으로 본다면 보조 공간도 O(n)이다. 반면 같은 배열 안에서 두 원소의 위치만 바꾸는 알고리즘은 몇 개의 임시 변수만 필요하므로 보조 공간은 O(1)이다.
“공간 복잡도 O(1)”이라고 할 때는 자료 전체가 메모리를 사용하지 않는다는 뜻이 아니라 입력 크기가 커져도 추가 메모리가 일정하다는 뜻인 경우가 많다. 전체 공간인지 보조 공간인지 구분해 말해야 한다.
연산 과정에서 필요한 보조 공간
- 배열 조회·수정: 인덱스와 임시 변수만 사용하므로 보조 공간 O(1)
- 배열 리사이징: 새 배열을 만들어 복사하므로 해당 순간 보조 공간 O(n)
- 연결 리스트 삽입·삭제: 반복 방식이고 위치를 알고 있다면 보조 공간 O(1)
- 해시 조회·삽입·삭제: 일반적인 한 번의 연산은 보조 공간 O(1)이지만, 재해싱 시 새 버킷 배열 때문에 O(n)
- BST 반복 탐색: 현재 노드 참조만 저장하면 보조 공간 O(1)
- BST 재귀 탐색: 호출 스택이 트리 높이만큼 쌓여 보조 공간 O(h). 균형 트리는 O(log n), 편향 트리는 O(n)
- DFS 순회: 재귀 호출 스택 또는 명시적 스택이 필요해 O(h). 최악에는 O(n)
- BFS·레벨 순회: 한 레벨의 노드를 큐에 저장하며 O(w). w는 트리의 최대 너비이고 최악에는 O(n)
- 힙 삽입·삭제: 배열 안에서 원소를 교환하는 반복 구현은 보조 공간 O(1)
자료구조별 저장 공간
| 자료구조 | 저장 공간 | 추가 비용과 특징 |
| 정적 배열 | O(n) | n개의 원소가 연속된 공간을 사용한다. |
| 동적 배열 | O(n) | 실제 원소 수보다 큰 용량을 확보할 수 있다. 리사이징 순간에는 기존 배열과 새 배열이 동시에 존재해 일시적으로 O(n)의 추가 공간이 필요하다. |
| 단일 연결 리스트 | O(n) | 각 노드가 값과 다음 노드 참조 하나를 저장한다. |
| 이중 연결 리스트 | O(n) | 각 노드가 이전·다음 참조를 모두 저장해 단일 연결 리스트보다 상수 배의 메모리를 더 사용한다. |
| 해시 테이블 | O(n + m) | n개의 엔트리와 m개의 버킷이 필요하다. 적재율을 일정하게 유지하면 m도 n에 비례하므로 일반적으로 O(n)으로 표현한다. |
| 트리 | O(n) | n개의 노드와 노드별 자식 참조가 필요하다. |
| 배열 기반 힙 | O(n) | 완전 이진 트리를 배열에 저장하므로 노드별 포인터가 필요하지 않다. |
1. 배열 Array
1.1 정의와 구조
배열은 같은 종류의 원소를 연속된 메모리 공간에 저장하는 자료구조이다. 배열의 시작 주소와 원소의 크기를 알고 있으면 원하는 위치의 주소를 바로 계산할 수 있다.
원소 주소 = 시작 주소 + 인덱스 × 원소 크기 따라서 배열은 첫 번째 원소부터 순서대로 탐색하지 않아도 인덱스로 원하는 원소에 즉시 접근할 수 있다.
Java나 Python 같은 고수준 언어의 배열·리스트가 객체를 저장할 때는 객체 자체가 아니라 객체를 가리키는 참조가 연속으로 저장될 수 있다. 그래도 인덱스에 해당하는 참조 위치는 바로 계산할 수 있다.
1.2 정적 배열과 동적 배열
정적 배열
- 생성할 때 길이가 결정된다.
- 이후 크기를 직접 늘리거나 줄일 수 없다.
- 필요한 크기가 명확할 때 단순하고 효율적이다.
동적 배열
- 내부적으로는 고정 크기 배열을 사용하지만, 공간이 부족하면 더 큰 배열을 만든다.
- 기존 원소를 새 배열에 복사한 뒤 새 원소를 추가한다.
- Java의 ArrayList, Python의 list 등이 대표적이다.
1.3 주요 연산
인덱스 조회 - O(1)
주소를 계산해 바로 접근한다. 데이터가 10개인지 100만 개인지와 관계없이 계산 과정은 동일하다.
값 탐색 - O(n)
정렬되지 않은 배열에서 특정 값을 찾으려면 최악의 경우 모든 원소를 확인해야 한다. 정렬된 배열이라면 이진 탐색을 사용해 O(log n)에 찾을 수 있지만, 배열을 정렬된 상태로 유지하는 비용이 추가된다.
마지막 삽입 - 일반적으로 O(1), 분할 상환 O(1)
남는 용량이 있으면 마지막 위치에 바로 저장한다. 용량이 부족한 순간에는 더 큰 배열을 만들고 n개의 원소를 복사하므로 O(n)이 필요하다. 하지만 보통 용량을 일정 배수로 확장하기 때문에 비싼 복사는 매번 발생하지 않는다. 여러 번의 추가 연산을 전체적으로 보면 원소 하나를 추가하는 평균 비용은 O(1)이다.
중간 삽입·삭제 - O(n)
중간에 값을 넣으려면 뒤쪽 원소를 한 칸씩 밀어야 한다. 삭제할 때도 빈자리를 없애기 위해 뒤쪽 원소를 앞으로 이동시켜야 한다.
1.4 장점
- 인덱스 기반 임의 접근이 빠르다.
- 원소가 가까이 배치되어 CPU 캐시를 효율적으로 활용한다.
- 원소별 포인터가 필요 없어 연결 리스트보다 추가 메모리 비용이 적다.
- 순차 순회가 빠르다.
1.5 단점
- 중간 삽입·삭제 시 많은 원소를 이동해야 한다.
- 정적 배열은 크기를 변경할 수 없다.
- 동적 배열은 실제 원소 수보다 큰 용량을 확보해 사용하지 않는 공간이 생길 수 있다.
- 확장 순간에는 새 배열 할당과 전체 복사가 필요하다.
1.6 적합한 상황
- 인덱스로 자주 조회할 때
- 데이터 순회가 많을 때
- 중간 삽입·삭제보다 끝에 추가하는 일이 많을 때
- 메모리 지역성이 중요한 수치 계산이나 반복 처리
1.7 핵심 정리
배열의 강점은 연속된 메모리와 O(1) 임의 접근, 약점은 중간 삽입·삭제 시 원소 이동이다.
2. 연결 리스트 Linked List
2.1 정의와 구조
연결 리스트는 데이터를 노드 단위로 저장하고, 각 노드가 다음 노드의 위치를 참조하도록 연결한 자료구조이다. 노드들은 메모리에 연속적으로 배치될 필요가 없다.
단일 연결 리스트
각 노드는 값과 다음 노드 참조를 가진다.
Head → [값 | Next] → [값 | Next] → [값 | Null]
이중 연결 리스트
각 노드는 값, 이전 노드 참조, 다음 노드 참조를 가진다.
Null ← [Prev | 값 | Next] ⇄ [Prev | 값 | Next] → Null
2.2 주요 연산
인덱스 조회·값 탐색 - O(n)
배열처럼 주소를 계산할 수 없다. Head부터 Next를 따라가며 원하는 위치 또는 값을 찾아야 한다.
맨 앞 삽입 - O(1)
새 노드의 Next가 기존 Head를 가리키게 한 뒤 Head를 새 노드로 바꾸면 된다.
맨 뒤 삽입
- Tail을 관리하면 O(1)
- Tail이 없으면 마지막 노드를 찾는 데 O(n)
중간 삽입 - 위치를 이미 알면 O(1)
새 노드와 앞뒤 노드의 참조만 변경하면 된다. 원소를 밀 필요가 없다. 단 삽입할 위치를 먼저 찾아야 한다면 탐색 비용 O(n)이 추가된다.
삭제 - 노드와 필요한 인접 정보를 알면 O(1)
- 이중 연결 리스트는 삭제할 노드의 Prev와 Next를 이용해 연결을 복구할 수 있다.
- 단일 연결 리스트는 보통 삭제할 노드의 이전 노드를 알아야 한다.
- 삭제할 값을 먼저 찾아야 한다면 전체 연산은 O(n)이다.
“연결 리스트의 삽입·삭제는 O(1)”은 수정할 위치를 이미 알고 있다는 조건에서만 맞는다. 위치 탐색까지 포함하면 O(n)일 수 있다.
2.3 장점
- 중간 원소를 이동하지 않고 연결만 변경해 삽입·삭제할 수 있다.
- 필요한 만큼 노드를 하나씩 할당할 수 있다.
- 이중 연결 리스트는 양방향 이동이 가능하다.
2.4 단점
- 인덱스 임의 접근이 불가능하다.
- 노드마다 참조를 저장하므로 추가 메모리가 필요하다.
- 노드가 메모리 곳곳에 흩어질 수 있어 캐시 효율이 낮다.
- 포인터를 잘못 갱신하면 연결이 끊기거나 순환이 생길 수 있다.
2.5 적합한 상황
- 위치를 알고 있는 노드의 삽입·삭제가 빈번할 때
- 앞뒤 원소를 빠르게 연결하거나 분리해야 할 때
- 이중 연결 리스트 기반의 덱이나 LRU Cache를 구현할 때
2.6 배열과 연결 리스트 비교
| 기준 | 배열 | 연결 리스트 |
| 메모리 배치 | 연속적 | 비연속적일 수 있음 |
| 인덱스 접근 | O(1) | O(n) |
| 중간 삽입·삭제 | 원소 이동 O(n) | 위치 탐색 O(n), 연결 변경 O(1) |
| 추가 메모리 | 미사용 용량이 생길 수 있음 | 노드별 참조가 필요함 |
| 캐시 효율 | 좋음 | 상대적으로 낮음 |
3. 해시 테이블 Hash Table
3.1 정의와 동작 과정
해시 테이블은 키를 해시 함수에 넣어 얻은 값을 이용해 저장 위치인 버킷을 결정하는 자료구조이다.
- 키를 해시 함수에 입력한다.
- 해시값을 얻는다.
- 해시값을 배열 크기에 맞는 버킷 인덱스로 변환한다.
- 해당 버킷에서 키와 값을 저장하거나 찾는다.
Key → Hash Function → Hash Value → Bucket Index → Entry 해시 함수는 같은 키에 대해 항상 같은 결과를 내야 하며, 키들이 여러 버킷에 고르게 분포하도록 설계하는 것이 좋다.
3.2 충돌 Collision
서로 다른 키가 같은 버킷 인덱스를 얻는 현상을 충돌이라고 한다. 가능한 키의 수가 버킷 수보다 많으므로 충돌을 완전히 피할 수는 없다.
체이닝 Chaining
각 버킷이 여러 엔트리를 저장할 수 있도록 리스트나 다른 구조를 둔다.
- 같은 버킷에 배정된 엔트리를 함께 보관한다.
- 구현과 삭제가 비교적 단순하다.
- 충돌이 많아지면 한 버킷을 순차 탐색해야 한다.
개방 주소법 Open Addressing
모든 엔트리를 버킷 배열 내부에 저장한다. 충돌이 발생하면 다른 빈 버킷을 탐색한다.
- 선형 조사: 다음 칸을 순서대로 확인한다.
- 제곱 조사: 이동 폭을 제곱 형태로 늘린다.
- 이중 해싱: 두 번째 해시 함수로 이동 폭을 정한다. 개방 주소법에서 원소를 단순히 비워 버리면 탐색 경로가 끊길 수 있으므로 삭제 표시인 Tombstone을 사용하기도 한다.
3.3 적재율과 리사이징
적재율은 저장된 엔트리 수를 버킷 수로 나눈 값이다.
적재율 α = 엔트리 수 n ÷ 버킷 수 m 적재율이 높아지면 충돌 가능성이 커지고 탐색 성능이 저하된다. 일정 기준을 넘으면 더 큰 버킷 배열을 만들고 기존 엔트리들의 위치를 다시 계산하는 리사이징·재해싱을 수행한다. 재해싱 한 번은 O(n)이지만 자주 발생하지 않도록 크기를 크게 확장하므로, 삽입의 장기 평균 비용은 일반적으로 O(1)로 본다.
3.4 시간 복잡도
| 연산 | 평균 | 최악 |
| 조회 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
4. 트리 Tree
4.1 정의와 기본 용어
트리는 노드들이 부모-자식 관계로 연결된 계층형 자료구조이다.
- Root: 부모가 없는 최상위 노드
- Parent / Child: 직접 연결된 상위·하위 노드
- Sibling: 같은 부모를 가진 노드
- Leaf: 자식이 없는 노드
- Edge: 두 노드의 연결
- Depth: 루트에서 특정 노드까지의 간선 수
- Height: 특정 노드에서 가장 먼 리프까지의 간선 수
- Subtree: 한 노드와 그 아래의 자손으로 이루어진 트리
교재에 따라 깊이와 높이를 노드 수로 세어 1부터 시작하기도 한다. 이 문서에서는 간선 수 기준으로 루트의 깊이를 0으로 둔다.
4.2 이진 트리의 종류
이진 트리는 각 노드가 최대 두 자식을 가지는 트리다.
- 정 이진 트리 Full Binary Tree: 모든 노드의 자식 수가 0개 또는 2개다.
- 포화 이진 트리 Perfect Binary Tree: 모든 내부 노드가 두 자식을 갖고 모든 리프의 깊이가 같다.
- 완전 이진 트리 Complete Binary Tree: 마지막 레벨을 제외한 레벨이 모두 차 있고, 마지막 레벨은 왼쪽부터 채워진다.
용어의 한국어 번역은 교재마다 다를 수 있으므로 Full, Perfect, Complete라는 영문 조건도 함께 확인하는 것이 안전하다.
그림: Full·Perfect·Complete 이진 트리의 조건 비교
4.3 트리 순회
다음 트리를 예로 든다.
루트 8 / 왼쪽 3, 오른쪽 10 / 3의 자식 1과 6 / 6의 자식 4와 7 / 10의 오른쪽 14 / 14의 왼쪽 13
전위 순회 Preorder — Root → Left → Right
결과: 8, 3, 1, 6, 4, 7, 10, 14, 13
- 부모를 먼저 처리해야 할 때 사용한다.
- 트리 복사, 디렉터리 구조 출력 등에 활용할 수 있다.
중위 순회 Inorder — Left → Root → Right
결과: 1, 3, 4, 6, 7, 8, 10, 13, 14
- 이진 탐색 트리를 중위 순회하면 값이 정렬된 순서로 나온다.
후위 순회 Postorder — Left → Right → Root
결과: 1, 4, 7, 6, 3, 13, 14, 10, 8
- 자식을 먼저 처리한 뒤 부모를 처리해야 할 때 사용한다.
- 디렉터리 삭제, 수식 트리 계산 등에 활용할 수 있다.
레벨 순회 Level Order
결과: 8, 3, 10, 1, 6, 14, 4, 7, 13
- 루트에서 가까운 레벨부터 방문한다.
- 큐를 사용하는 BFS 방식이다.
그림: 동일한 트리의 전위·중위·후위·레벨 순회 결과
4.4 이진 탐색 트리 BST
이진 탐색 트리는 각 노드에 대해 다음 규칙을 만족하는 이진 트리다.
- 왼쪽 서브트리의 값은 현재 노드보다 작다.
- 오른쪽 서브트리의 값은 현재 노드보다 크다.
- 중복 값을 허용한다면 어느 쪽에 둘지 일관된 정책이 필요하다.
탐색
- 찾는 값과 현재 노드를 비교한다.
- 값이 작으면 왼쪽, 크면 오른쪽으로 이동한다.
- 값을 찾거나 빈 위치에 도달할 때까지 반복한다.
삽입
탐색과 같은 비교를 반복해 빈 자식 위치를 찾은 뒤 새 노드를 연결한다.
삭제
- 자식이 없는 노드: 해당 노드를 제거한다.
- 자식이 하나인 노드: 부모가 삭제 노드의 유일한 자식을 가리키게 한다.
- 자식이 둘인 노드: 오른쪽 서브트리의 최솟값인 중위 후속자 또는 왼쪽 서브트리의 최댓값인 중위 선행자로 값을 대체한 뒤, 대체에 사용한 노드를 삭제한다.
4.5 BST의 복잡도와 균형
BST의 탐색·삽입·삭제 복잡도는 트리 높이 h에 비례해 O(h)이다.
- 균형이 잡힌 경우 높이는 O(log n)이므로 연산도 O(log n)이다.
- 정렬된 값이 차례로 삽입되어 한쪽으로 치우치면 높이가 O(n)이 되고, 연결 리스트처럼 동작한다.
균형 이진 탐색 트리
- AVL Tree: 좌우 높이 차이를 엄격하게 관리해 탐색 성능이 안정적이다.
- Red-Black Tree: 색상 규칙과 회전을 이용해 대략적인 균형을 유지한다. AVL보다 균형 조건은 느슨하지만 삽입·삭제 시 회전 부담이 상대적으로 적다.
두 구조 모두 핵심 목적은 트리 높이를 O(log n) 수준으로 제한하는 것이다.
4.6 힙 Heap
힙은 우선순위가 가장 높은 원소를 빠르게 꺼내기 위한 완전 이진 트리 기반 자료구조이다.
- 최소 힙: 부모 값이 자식 값보다 작거나 같다.
- 최대 힙: 부모 값이 자식 값보다 크거나 같다. 완전 이진 트리이므로 배열로 효율적으로 표현할 수 있다. 인덱스 i를 기준으로:
- 부모: (i - 1) ÷ 2의 내림
- 왼쪽 자식: 2i + 1
- 오른쪽 자식: 2i + 2
그림: 최소 힙의 트리 구조와 배열 인덱스 대응
| 힙 연산 | 복잡도 | 이유 |
| 최솟값·최댓값 확인 | O(1) | 루트에 있음 |
| 삽입 | O(log n) | 위로 이동하며 힙 속성 복구 |
| 루트 삭제 | O(log n) | 아래로 이동하며 힙 속성 복구 |
| 임의 값 탐색 | O(n) | 전체 정렬 관계가 없기 때문 |
힙은 BST가 아니다. 힙은 부모와 자식 사이의 우선순위만 보장하며, 왼쪽 서브트리가 모두 작고 오른쪽 서브트리가 모두 크다는 규칙은 없다.
4.7 트리의 활용
- 파일 시스템과 조직도 같은 계층 구조
- HTML DOM
- 데이터베이스 인덱스의 B-Tree·B+Tree 계열
- 자동 완성의 Trie
- 우선순위 큐의 Heap
- 정렬된 Map과 Set의 균형 BST
4.8 핵심 정리
트리는 계층 관계를 표현한다. BST는 정렬된 탐색, Heap은 최우선 원소 접근에 목적이 있으며 서로 다른 규칙을 가진다.
5. 네 자료구조 종합 비교
| 자료구조 | 조회·탐색 | 삽입·삭제 | 대표 강점 |
| 동적 배열 | 인덱스 O(1), 값 O(n) | 끝 분할 상환 O(1), 중간 O(n) | 임의 접근과 순회 |
| 연결 리스트 | O(n) | 위치를 알면 O(1) | 연결 변경 |
| 해시 테이블 | 평균 O(1), 최악 O(n) | 평균 O(1), 최악 O(n) | 키 기반 접근 |
| 균형 BST | O(log n) | O(log n) | 정렬 유지와 범위 탐색 |
| 힙 | 루트 O(1), 임의 값 O(n) | O(log n) | 최우선 원소 처리 |
