Post

자료구조

자료구조 개요

자료구조(Data Structures)는 데이터를 효율적으로 저장하고 관리하는 방법을 정의하는 논리적, 수학적 개념입니다. 자료구조는 프로그램의 성능과 효율성에 큰 영향을 미치며, 다양한 유형의 자료구조가 존재합니다. 이 문서에서는 주요 자료구조의 개념과 특징을 설명합니다.

1. 배열 (Array)

  • 설명: 동일한 타입의 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다.
  • 특징:
    • 고정된 크기
    • 인덱스를 통해 빠른 접근이 가능
    • 삽입 및 삭제가 비효율적
  • 예시:
    1
    2
    
      arr = [1, 2, 3, 4, 5]
      print(arr[2])  # 출력: 3
    

2. 연결 리스트 (Linked List)

  • 설명: 각 요소가 데이터와 다음 요소를 가리키는 포인터를 포함하는 노드로 구성된 자료구조입니다.
  • 특징:
    • 크기가 동적
    • 삽입 및 삭제가 효율적
    • 인덱스를 통한 접근이 비효율적
  • 종류:
    • 단일 연결 리스트 (Singly Linked List)
    • 이중 연결 리스트 (Doubly Linked List)
    • 원형 연결 리스트 (Circular Linked List)
  • 예시:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
      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
              else:
                  current = self.head
                  while current.next:
                      current = current.next
                  current.next = new_node
    

3. 스택 (Stack)

  • 설명: 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.
  • 특징:
    • 요소의 삽입과 삭제가 한쪽 끝에서만 발생
    • 주요 연산: 푸시(Push), 팝(Pop), 피크(Peek)
  • 예시:
    1
    2
    3
    4
    
      stack = []
      stack.append(1)  # 푸시
      stack.append(2)
      print(stack.pop())  # 팝, 출력: 2
    

4. 큐 (Queue)

  • 설명: 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조입니다.
  • 특징:
    • 요소의 삽입은 뒤에서, 삭제는 앞에서 발생
    • 주요 연산: 인큐(Enqueue), 디큐(Dequeue)
  • 종류:
    • 일반 큐
    • 원형 큐 (Circular Queue)
    • 우선순위 큐 (Priority Queue)
  • 예시:
    1
    2
    3
    4
    5
    
      from collections import deque
      queue = deque()
      queue.append(1)  # 인큐
      queue.append(2)
      print(queue.popleft())  # 디큐, 출력: 1
    

5. 트리 (Tree)

  • 설명: 계층적인 구조를 가지며, 노드와 에지로 구성된 자료구조입니다.
  • 특징:
    • 루트 노드에서 시작하여 자식 노드로 확장
    • 이진 트리, AVL 트리, 힙 등 다양한 종류가 있음
  • 종류:
    • 이진 트리 (Binary Tree)
    • 이진 탐색 트리 (Binary Search Tree)
    • AVL 트리 (AVL Tree)
    • 힙 (Heap)
  • 예시:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
      class TreeNode:
          def __init__(self, value):
              self.value = value
              self.left = None
              self.right = None
    
      def insert(root, value):
          if root is None:
              return TreeNode(value)
          if value < root.value:
              root.left = insert(root.left, value)
          else:
              root.right = insert(root.right, value)
          return root
    

6. 그래프 (Graph)

  • 설명: 노드(정점)와 에지(간선)로 구성된 자료구조로, 복잡한 관계를 나타내는 데 사용됩니다.
  • 특징:
    • 방향 그래프와 무방향 그래프가 있음
    • 순환 그래프와 비순환 그래프가 있음
  • 종류:
    • 인접 행렬 (Adjacency Matrix)
    • 인접 리스트 (Adjacency List)
  • 예시:
    1
    2
    3
    4
    5
    6
    7
    8
    
      graph = {
          'A': ['B', 'C'],
          'B': ['A', 'D', 'E'],
          'C': ['A', 'F'],
          'D': ['B'],
          'E': ['B', 'F'],
          'F': ['C', 'E']
      }
    

결론

자료구조는 데이터의 효율적인 저장과 관리를 위한 기본적인 개념입니다. 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등 다양한 자료구조가 있으며, 각각의 특성과 용도에 맞게 선택하여 사용해야 합니다. 올바른 자료구조의 선택은 프로그램의 성능과 효율성에 큰 영향을 미칩니다.

This post is licensed under CC BY 4.0 by the author.