CodingTest/algorithm

자료구조와 알고리즘의 시간복잡도 완벽 정리: 이진트리부터 해시 테이블까지

사족보행 개발자 2024. 10. 17. 23:39
728x90

 

자료구조와 알고리즘을 이해하는 것은 효율적인 프로그래밍을 작성하는 데 중요한 요소이다.

자료구조의 선택에 따라 성능이 크게 달라질 수 있기 때문에,

각 자료구조와 알고리즘의 시간복잡도를 잘 파악하는 것이 필요하다.

 

이 글에서는 파이썬을 기반으로 다양한 자료구조와 알고리즘의 시간복잡도를 코드와 함께 설명하고,

삽입, 탐색, 제거와 같은 주요 연산의 시간복잡도를 비교해보고자 한다.

 

1. 배열 (Array)

배열

 

배열은 파이썬의 list와 유사하다. 파이썬 리스트는 동적 배열로 구현되어 있으며, 

여러 요소를 연속된 메모리 공간에 저장한다.

  • 삽입: 끝에 삽입은 O(1)이다. 중간에 삽입은 O(n)이다.
  • 탐색: 특정 인덱스를 통해 접근하는 것은 O(1)이다.
  • 제거: 특정 인덱스의 요소를 제거하는 경우 O(n)이 걸린다.

 

arr = [1, 2, 3, 4]
arr.append(5)  # O(1)
arr.insert(2, 10)  # O(n)
arr.pop(3)  # O(n)

 

 

2. 연결 리스트 (Linked List)

연결 리스트

 

연결 리스트는 각 노드가 다음 노드를 가리키는 방식으로 이루어져 있다. 

파이썬에는 내장 연결 리스트 자료구조가 없으므로 사용자 정의 클래스를 사용해야 한다.

  • 삽입: 특정 위치에 삽입 시 O(n)이 걸린다. 하지만 처음이나 끝에 삽입하는 경우는 O(1)이다.
  • 탐색: 원하는 요소를 찾기 위해 순회해야 하므로 O(n)이다.
  • 제거: 특정 위치의 요소를 제거하는 데 O(n)이 소요된다.
 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):  # O(1)
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def find(self, key):  # O(n)
        current = self.head
        while current:
            if current.data == key:
                return current
            current = current.next
        return None

 

3. 이진 탐색 트리 (Binary Search Tree, BST)

이진탐색트리

 

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 

왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.

 

일반적으로 이진 탐색 트리는 O(log n)의 시간복잡도를 갖는데,

한쪽 자식으로만 계속 연결되어 있는 경우에, 편향되었다고 하며 이 때 시간복잡도는 O(n) 이다.

 

  • 삽입: 평균 O(log n), 최악 O(n) (트리가 편향된 경우).
  • 탐색: 평균 O(log n), 최악 O(n).
  • 제거: 평균 O(log n), 최악 O(n).

 

 

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):  # 평균 O(log n)
    if root is None:
        return TreeNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):  # 평균 O(log n)
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

 

4. 해시 테이블 (Hash Table)

해시 테이블

 

해시 테이블은 데이터를 키-값 쌍으로 저장하며, 파이썬의 dict가 대표적인 예이다.

해시 함수를 이용해 데이터를 빠르게 접근할 수 있다.

  • 삽입: 평균 O(1).
  • 탐색: 평균 O(1).
  • 제거: 평균 O(1).

 

hash_table = {}
hash_table['name'] = 'Alice'  # O(1)
value = hash_table.get('name')  # O(1)
del hash_table['name']  # O(1)

 

5. 힙 (Heap)

힙

 

힙은 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조로, 우선순위 큐를 구현하는 데 사용된다.

파이썬에서는 heapq 모듈을 통해 최소 힙을 사용할 수 있다.

  • 삽입: O(log n).
  • 최솟값 추출: O(log n).
  • 탐색: O(n) (특정 값을 찾는 경우).
 
import heapq
heap = []
heapq.heappush(heap, 3)  # O(log n)
heapq.heappush(heap, 1)  # O(log n)
min_value = heapq.heappop(heap)  # O(log n)

 

6. 그래프 (Graph)

그래프

 

그래프는 정점과 간선으로 이루어진 자료구조로, 다양한 방식으로 구현된다.

파이썬에서는 인접 리스트나 인접 행렬을 통해 그래프를 표현할 수 있다.

  • DFS/BFS 탐색: O(V + E) (V는 정점의 개수, E는 간선의 개수).
  • 삽입 (정점 추가): O(1).
  • 제거 (정점/간선 제거): O(V + E).

 

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

def bfs(graph, start):  # O(V + E)
    visited = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue.extend(set(graph[node]) - set(visited))
    return visited

 

7. 자료구조와 알고리즘의 시간복잡도 비교

 

자료구조/알고리즘 삽입 탐색 제거
배열
(Array)		 O(1) (끝에 삽입) /
O(n) (중간 삽입)		 O(1) (인덱스 접근) O(n)
연결 리스트
(Linked List)		 O(1) (끝에 삽입) /
O(n) (중간 삽입) 		O(n) O(n)
이진 탐색 트리
(Binary Seach Tree)		 평균 O(log n),
최악 O(n)		 평균 O(log n),
최악 O(n) 		평균 O(log n),
최악 O(n)
해시 테이블
(Hash Table)		 O(1) O(1) O(1)
힙
(heap) 		 O(log n) O(n) (특정 값 탐색) O(log n) (최댓값/최솟값 추출)
그래프
(graph)		 O(1) (정점 추가) O(V + E) (DFS, BFS) O(V + E)
728x90