2025. 3. 18. 15:30ㆍ자료구조
안녕하세요! 오늘은 파이썬에서 자주 쓰이는 자료구조들의 시간복잡도를 한눈에 정리해보려고 합니다.
어떤 자료구조를 선택해야 더 빠르고 효율적일지 고민된다면? 이 글을 참고하세요! 😊
📌 파이썬 자료구조 시간복잡도 한눈에 보기
자료구조마다 시간복잡도가 다르기 때문에, 어떤 상황에서 어떤 자료구조를 써야 할지 아는 것이 중요합니다.
아래 표는 탐색, 추가, 삭제 연산에 대한 시간복잡도를 정리한 것입니다.
| 리스트 (list) | O(n) | O(1) (끝) / O(n) (중간) | O(1) (끝) / O(n) (중간) |
| 딕셔너리 (dict) | O(1) | O(1) | O(1) |
| 셋 (set) | O(1) | O(1) | O(1) |
| 덱 (deque) | O(n) | O(1) (양쪽) | O(1) (양쪽) |
| 힙 (heapq) | O(n) | O(log n) | O(log n) |
✅ 결론:
- 탐색이 많다면? 👉 dict or set (O(1)이라 빠름)
- 순서가 중요하다면? 👉 list or deque
- FIFO 큐가 필요하다면? 👉 deque
- 우선순위 처리(최솟값 유지)? 👉 heapq
- 중복 제거? 👉 set
📌 1. 리스트 (list)
파이썬의 리스트는 동적 배열 (Dynamic Array) 구조로 되어 있습니다.
즉, 배열처럼 동작하지만 크기가 자동으로 확장되는 구조입니다.
🔹 리스트 연산 시간복잡도
| list.append(x) | O(1) | 맨 끝에 추가 |
| list.insert(i, x) | O(n) | 중간에 삽입 시 밀어야 함 |
| list.pop() | O(1) | 끝에서 제거 |
| list.pop(i) | O(n) | 중간에서 제거 |
| x in list | O(n) | 리스트에서 값 찾기 |
| list.sort() | O(n log n) | TimSort 알고리즘 사용 |
📌 리스트는 언제 쓰면 좋을까?
✅ 순서가 중요한 데이터
✅ 인덱스를 이용해 빠르게 접근할 때
❌ 탐색/삭제가 많다면 비효율적! (O(n))
📌 2. 딕셔너리 (dict)
파이썬의 dict는 해시 테이블 기반으로 동작합니다.
즉, 키-값을 저장할 때 해시 함수를 사용하여 탐색, 삽입, 삭제 모두 O(1) 이라는 강력한 성능을 제공합니다!
🔹 딕셔너리 연산 시간복잡도
| dict[key] = value | O(1) | 키-값 추가 |
| dict[key] | O(1) | 키로 값 조회 |
| del dict[key] | O(1) | 키-값 삭제 |
| key in dict | O(1) | 키 존재 여부 확인 |
📌 딕셔너리는 언제 쓰면 좋을까?
✅ 키-값을 빠르게 조회해야 할 때
✅ 중복 없는 데이터를 저장해야 할 때
❌ 순서가 중요하다면 리스트를 고려 (단, Python 3.6+에서는 dict도 삽입 순서를 유지)
📌 3. 셋 (set)
파이썬의 set은 해시 테이블 기반의 집합 자료구조입니다.
리스트와 다르게 중복을 자동으로 제거하며, 탐색 속도가 O(1) 입니다.
🔹 셋 연산 시간복잡도
| set.add(x) | O(1) | 값 추가 |
| set.remove(x) | O(1) | 값 삭제 |
| x in set | O(1) | 값 존재 여부 확인 |
📌 셋은 언제 쓰면 좋을까?
✅ 중복 없는 데이터를 저장해야 할 때
✅ 리스트보다 빠른 탐색이 필요할 때
❌ 순서가 필요하면 리스트 사용
📌 4. 덱 (collections.deque)
deque는 양쪽 끝에서 빠르게 삽입/삭제가 가능한 자료구조입니다.
리스트로 큐를 구현하면 pop(0)이 O(n)인데, deque.popleft()는 O(1)입니다.
🔹 덱 연산 시간복잡도
| deque.append(x) | O(1) | 뒤에 추가 |
| deque.appendleft(x) | O(1) | 앞에 추가 |
| deque.pop() | O(1) | 뒤에서 제거 |
| deque.popleft() | O(1) | 앞에서 제거 |
📌 덱은 언제 쓰면 좋을까?
✅ 큐 또는 스택을 구현할 때
✅ 앞뒤로 빠르게 삽입/삭제가 필요할 때
❌ 임의의 인덱스에 접근해야 하면 리스트가 더 적합
📌 5. 힙 (heapq)
파이썬의 heapq는 최소 힙 (Min Heap) 기반으로 동작합니다.
우선순위 큐를 구현할 때 사용되며, 항상 가장 작은 값이 빠르게 검색 가능합니다.
🔹 힙 연산 시간복잡도
| heapq.heappush(heap, x) | O(log n) | 요소 추가 |
| heapq.heappop(heap) | O(log n) | 최소값 제거 |
| heapq.heapify(list) | O(n) | 리스트를 힙으로 변환 |
📌 힙은 언제 쓰면 좋을까?
✅ 최솟값을 빠르게 찾을 때
✅ 우선순위 큐가 필요할 때
❌ 일반적인 리스트 연산이 많다면 비효율적
'자료구조' 카테고리의 다른 글
| [자료구조] B-Tree와 B+Tree 비교(탐색, 삽입, 삭제) (0) | 2025.03.22 |
|---|