기본 자료구조 안내서 · 1/6
자료구조는 데이터를 메모리에 배치하는 방식과, 그 배치에서 싸게 할 수 있는 연산을 함께 묶은 것입니다. 자료구조를 고르는 일은 언제나 맞바꿈입니다. 위치로 찾는 일이 즉시 끝나는 배치는 가운데 삽입이 느릴 수 있고, 삽입이 싼 배치는 찾기가 느릴 수 있습니다. 이 안내서는 거의 모든 프로그램에서 만나는 다섯 가지 구조, 즉 배열과 동적 배열, 연결 리스트, 스택, 큐와 덱, 해시 테이블을 다룹니다.
구조가 약속하는 것과 그 약속을 지키는 방법을 나눠 생각하면 이해가 쉬워집니다.
push, pop, peek 를 제공하고, 마지막에 넣은 것이 먼저 나온다고 약속합니다.면접 질문이나 라이브러리 문서는 이 둘을 섞어 말하는 경우가 많습니다. "어떤 클래스를 쓸까?"보다 "어떤 연산이 얼마나 자주 필요한가?"를 먼저 묻는 습관을 들이면 좋습니다.
여기서 다루는 구조는 모두 두 가지 생각 중 하나에서 출발합니다.
| 방식 | 저장 방법 | 장점 | 단점 |
|---|---|---|---|
| 연속 | 한 덩어리 메모리에 나란히 저장 | 위치로 O(1) 접근, 캐시 친화적 | 가운데에 넣으면 뒤쪽을 모두 밀어야 함 |
| 연결 | 따로 떨어진 노드를 포인터로 연결 | 쥐고 있는 노드 옆이라면 O(1) 삽입·삭제 | k번째 항목까지 O(n), 캐시 효율이 낮음 |
요즘 CPU는 메모리를 캐시 라인 단위로 읽기 때문에, 빅오가 같더라도 연속 배열을 훑는 쪽이 연결 리스트를 훑는 쪽보다 몇 배 빠른 경우가 흔합니다.
list, C++ std::vector, Java ArrayList, JavaScript 배열)은 여유 용량을 두었다가 가득 차면 더 큰 블록을 잡아 복사하므로, 끝에 추가하는 비용이 분할 상환 O(1)입니다.실무 코드에서 이 구조를 직접 짜는 일은 드물지만, 어떤 내장 타입이 어떤 생각에 해당하는지는 알아야 합니다.
| 개념 | Python | C++ | Java | TypeScript |
|---|---|---|---|---|
| 동적 배열 | list | std::vector | ArrayList | Array |
| 스택 | list (append / pop) | std::vector 또는 std::stack | ArrayDeque | Array (push / pop) |
| 큐 / 덱 | collections.deque | std::deque, std::queue | ArrayDeque | 원형 버퍼를 직접 작성 |
| 해시 맵 | dict | std::unordered_map | HashMap | Map |
| 해시 집합 | set | std::unordered_set | HashSet | Set |
리스트를 스택으로 쓸 때는 끝에서만 넣고 뺍니다.
stack = []
stack.append("a") # push
stack.append("b")
print(stack[-1]) # peek -> b
print(stack.pop()) # pop -> b
print(stack) # ['a']큐가 필요하면 list.pop(0) 대신 deque 를 씁니다. pop(0) 은 남은 원소를 전부 한 칸씩 당기기 때문입니다.
from collections import deque
queue = deque()
queue.append("job-1") # 오른쪽 끝에 넣기(enqueue)
queue.append("job-2")
print(queue.popleft()) # 왼쪽 끝에서 꺼내기(dequeue) -> job-1
queue.appendleft("urgent") # 덱은 앞쪽에도 넣을 수 있습니다
print(list(queue)) # ['urgent', 'job-2']딕셔너리와 집합은 해시 테이블입니다. 키는 해시할 수 있어야 하며, 실제로는 변경 불가능한 값이어야 한다는 뜻입니다.
stock = {"apple": 3, "pear": 0}
stock["kiwi"] = 7 # 삽입
stock["apple"] += 1 # 갱신
print(stock.get("plum", 0)) # 없는 키는 기본값 -> 0
seen = {"apple", "kiwi"}
print("pear" in seen) # 평균 O(1) 포함 검사 -> False
# stock[["a", "b"]] = 1 은 TypeError: 리스트는 해시할 수 없습니다다음 질문을 차례로 던져 봅니다.
| 용어 | 뜻 |
|---|---|
| 용량(capacity) | 동적 배열이 확보한 칸 수(비어 있는 칸 포함) |
| 분할 상환 비용 | 긴 연산 열에서 연산 하나당 평균 비용 |
| 해시 함수 | 키를 정수로 바꾸는 함수 |
| 버킷 | 해시 테이블 배열의 한 칸 |
| 충돌 | 서로 다른 두 키가 같은 버킷에 들어가는 일 |
| 적재율(load factor) | 저장한 항목 수를 버킷 수로 나눈 값 |
자료구조는 접근 방식 사이의 맞바꿈입니다. 연속 배열은 빠른 인덱싱과 좋은 캐시 효율을, 연결 노드는 국소적인 끼워 넣기를, 스택과 큐는 끝에서만 다루는 단순함을, 해시 테이블은 키로 찾는 평균 O(1)을 줍니다. 필요한 연산에서 출발해, 그 연산을 싸게 만들어 주는 내장 타입을 고르면 됩니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.