[자료구조] 자료구조의 기본 개념 및 종류, 예제 코드

자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 뜻한다.
컴퓨터 프로그램에서 데이터를 다루기 위해서는 데이터의 크기나 성질, 처리 방식 등에 맞는 자료구조를 선택하는 것이 중요하다. 예를 들어, 데이터를 순서대로 다루어야 하는 경우와, 특정 조건에 맞는 데이터만 빠르게 검색해야 하는 경우에는 각기 다른 자료구조가 더 적합할 것이다. 이렇게 적절한 자료구조를 사용하면 코드의 성능을 높이고, 메모리 사용을 효율적으로 관리할 수 있다.

아래에서는 대표적인 자료구조와 각 자료구조의 특징, 사용법, 그리고 코드 예제를 통해 활용 방안을 설명하겠다.

1. 배열 (Array)

배열은 동일한 데이터 타입을 가진 값들이 연속된 메모리 공간에 저장된 자료구조이다. 배열은 각 요소가 고유한 인덱스를 가지기 때문에, 데이터를 빠르게 접근할 수 있다. 하지만 배열의 크기는 고정되어 있어, 데이터의 크기가 동적으로 변하는 경우는 다른 자료구조가 더 적합할 수 있다.

활용 예시: 고정된 크기의 데이터 처리, 정렬된 데이터에서의 탐색

# 배열 선언 및 초기화
array = [1, 2, 3, 4, 5]

# 요소 접근
print(array[2])  # 3

# 요소 추가 및 삭제
array.append(6)       # [1, 2, 3, 4, 5, 6]
array.remove(2)       # [1, 3, 4, 5, 6]

2. 연결 리스트 (Linked List)

연결 리스트는 각 데이터 요소가 다음 요소에 대한 참조(포인터)를 가지고 있는 자료구조이다. 요소들은 물리적으로 떨어진 메모리에 저장될 수 있으며, 새로운 데이터를 삽입하거나 삭제하는 것이 배열보다 빠르다. 다만, 인덱스를 사용하여 임의의 요소에 접근할 수 없어, 순차적으로 탐색해야 한다.

활용 예시: 데이터의 삽입과 삭제가 빈번하게 발생하는 경우

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 사용 예
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # 1 -> 2 -> 3 -> None

3. 스택 (Stack)

스택은 LIFO(Last In, First Out) 구조로, 마지막에 삽입된 데이터가 가장 먼저 제거되는 자료구조이다. 따라서, 먼저 들어간 데이터는 나중에 나오는 형태로 처리된다. 이는 함수 호출의 기록을 추적하거나 실행 취소 기능에 유용하다.

활용 예시: 함수 호출 기록, 실행 취소, 수식 계산

stack = []

# 요소 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)

# 요소 제거 (pop)
print(stack.pop())  # 3
print(stack.pop())  # 2

4. 큐 (Queue)

큐는 FIFO(First In, First Out) 구조로, 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 이는 고객 서비스 요청과 같은 순차적으로 처리해야 하는 작업에 적합하다.

활용 예시: 작업 스케줄링, 네트워크 패킷 처리

from collections import deque

queue = deque()

# 요소 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

# 요소 제거 (dequeue)
print(queue.popleft())  # 1
print(queue.popleft())  # 2

5. 해시 테이블 (Hash Table)

해시 테이블은 특정 키에 대한 데이터를 빠르게 찾을 수 있도록 해시 함수를 이용하는 자료구조이다. 평균적으로 O(1)의 시간복잡도로 데이터를 검색할 수 있다. Python의 dict가 해시 테이블로 구현되어 있다.

활용 예시: 빠른 데이터 검색, 중복 체크, 데이터베이스 인덱싱

# 해시 테이블 초기화
hash_table = {}

# 요소 추가
hash_table["apple"] = 3
hash_table["banana"] = 5

# 요소 접근
print(hash_table["apple"])  # 3

# 요소 삭제
del hash_table["banana"]
print(hash_table)  # {'apple': 3}

6. 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조로, 정렬된 데이터를 빠르게 탐색할 수 있다. 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가진다. 탐색, 삽입, 삭제 등의 연산에서 O(log n)의 시간 복잡도를 가지며, 정렬된 데이터를 효과적으로 관리할 수 있다.

활용 예시: 데이터 정렬, 데이터 검색

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = TreeNode(key)
            else:
                self._insert_recursive(node.left, key)
        else:
            if node.right is None:
                node.right = TreeNode(key)
            else:
                self._insert_recursive(node.right, key)

    def inorder_traversal(self, node):
        if node:
            self.inorder_traversal(node.left)
            print(node.key, end=" ")
            self.inorder_traversal(node.right)

# 사용 예
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.inorder_traversal(bst.root)  # 3 5 7

7. 그래프 (Graph)

그래프는 여러 개의 노드(정점)들이 간선으로 연결된 구조이다. 각 정점 간의 관계를 표현할 수 있어 네트워크, 경로 탐색, 지도 등 다양한 곳에서 활용된다. Python에서는 딕셔너리를 이용해 인접 리스트로 구현할 수 있다.

활용 예시: 경로 탐색, 네트워크 연결, 소셜 네트워크 분석

# 그래프 선언
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# 그래프 탐색 (깊이 우선 탐색)
def dfs(graph, start, visited=set()):
    if start not in visited:
        print(start, end=" ")
        visited.add(start)
        for neighbor in graph[start]:
            dfs(graph, neighbor, visited)

# DFS 사용 예
dfs(graph, 'A')  # A B D C

8. 힙 (Heap)

힙은 우선순위 큐를 구현할 때 사용하는 자료구조로, 가장 큰 값이나 작은 값을 빠르게 찾을 수 있도록 트리 구조를 이룬다. Python의 heapq 모듈을 이용하면 최소 힙을 간단히 구현할 수 있다.

활용 예시: 우선순위 작업 관리, 힙 정렬, 최단 경로 알고리즘

import heapq

heap = []

# 요소 추가
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

# 최소값 추출
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3

이와 같이, 다양한 자료구조는 각기 다른 장점과 활용 방안을 가지고 있다. 각 문제에 맞는 자료구조를 선택함으로써 프로그램의 성능과 효율성을 높일 수 있다.

저작자표시 비영리

☀️ Sunny's DataLab ☀️