자료구조 (Data Structures)
자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 연구하는 컴퓨터 과학의 한 분야입니다. 주요 자료구조는 데이터의 성격과 문제 해결에 필요한 연산의 종류에 따라 선택됩니다. 자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있습니다.
선형 구조 (Linear Structure)
선형 구조는 데이터 요소들이 일직선으로 나열되어 있으며, 각 요소가 바로 다음 요소와 1:1 관계를 맺고 있는 구조입니다. 주요 선형 구조는 다음과 같습니다:
- 배열 (Array):
- 정의: 동일한 타입의 데이터를 연속적으로 저장하는 자료구조.
- 특징: 인덱스를 사용하여 접근 시간은 O(1)이지만, 크기 변경이 어렵고, 삽입 및 삭제 연산이 비효율적일 수 있음.
- 예시: [10, 20, 30, 40, 50]
- 연결 리스트 (List):
- 정의: 각 요소가 데이터와 다음 요소에 대한 참조(포인터)를 가지는 노드들로 이루어진 선형 자료구조.
- 특징: 크기 변경이 용이하고, 삽입 및 삭제 연산이 효율적이지만, 임의 접근 시간이 O(n)임.
- 예시: 10 -> 20 -> 30 -> 40 -> 50
- 스택 (Stack):
- 정의: 후입선출(LIFO, Last In First Out) 원칙에 따라 작동하는 자료구조.
- 특징: 삽입(push)과 삭제(pop) 연산이 O(1)로 빠르며, 주로 함수 호출 시 사용됨.
- 예시: [10, 20, 30] (Top이 30)
- 큐 (Queue):
- 정의: 선입선출(FIFO, First In First Out) 원칙에 따라 작동하는 자료구조.
- 특징: 삽입(enqueue)과 삭제(dequeue) 연산이 O(1)로 빠르며, 주로 작업 대기열에서 사용됨.
- 예시: [10, 20, 30] (10이 가장 먼저 나감)
- 데크 (Deque):
- 정의: 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조.
- 특징: 양쪽 끝에서 삽입과 삭제가 O(1) 시간에 가능하며, 스택과 큐의 기능을 모두 포함하고 있어 매우 유연함.
- 예시: [10, 20, 30] (양 끝에서 삽입/삭제 가능)
비선형 구조 (Non-linear Structure)
비선형 구조는 데이터 요소들이 계층적이거나 네트워크 형태로 배열되어 있으며, 각 요소가 여러 요소와 1:N를 관계를 맺을 수 있는 구조입니다. 주요 비선형 구조는 다음과 같습니다:
1. 트리 (Tree):
- 정의: 계층 구조를 가지는 자료구조로, 루트 노드와 자식 노드들로 구성됨.
- 특징: 이진 트리, 이진 탐색 트리(BST), AVL 트리, 힙(Heap) 등 다양한 형태가 있으며, 각 형태마다 삽입, 삭제, 탐색의 시간 복잡도가 다름.
2. 그래프 (Graph):
- 정의: 정점(vertices)과 정점들을 연결하는 간선(edges)으로 구성된 자료구조.
- 특징: 방향 그래프, 무방향 그래프, 가중치 그래프 등 여러 종류가 있으며, 네트워크 모델링 등 다양한 분야에서 사용됨.
선형 구조와 비선형 구조의 주요 차이점
- 구조적 차이:
- 선형 구조: 데이터가 일직선으로 배치되며, 각 요소는 정확히 하나의 다음 요소와 연결됩니다.
- 비선형 구조: 데이터가 계층적이거나 네트워크 형태로 배치되며, 각 요소는 여러 요소와 연결될 수 있습니다.
- 접근 방식:
- 선형 구조: 순차적으로 접근하며, 인덱스를 사용하거나 다음 요소를 참조하여 이동합니다.
- 비선형 구조: 계층적 또는 연결된 요소들 간의 관계를 따라 접근합니다.
- 연산 복잡도:
- 선형 구조: 주로 O(1) 또는 O(n)의 시간 복잡도를 가집니다.
- 비선형 구조: 삽입, 삭제, 탐색 등의 연산이 구조의 종류에 따라 O(log n), O(n), O(E+V) 등 다양합니다.
- 사용 용도:
- 선형 구조: 데이터가 순차적으로 처리되거나, 순서가 중요한 경우에 사용됩니다.
- 비선형 구조: 데이터 간의 복잡한 관계를 모델링하거나, 계층적 데이터 처리에 사용됩니다.
