소개
- 정의 및 중요성: 자료구조는 효율적으로 액세스, 수정 및 처리할 수 있도록 컴퓨터에서 데이터를 구성하고 저장하는 방법입니다. 자료구조는 알고리즘과 프로그램의 성능과 효율성에 상당한 영향을 미칠 수 있으므로 컴퓨터 프로그래밍에서 중요한 역할을 합니다. 특정 작업에 대한 자료구조의 선택은 프로그램의 속도, 메모리 사용량 및 전반적인 효율성에 큰 영향을 미칠 수 있습니다.
- 자료구조의 종류: 다양한 유형의 자료구조가 있으며 각각 고유한 강점과 약점이 있습니다. 가장 일반적인 자료구조에는 arrays, linked lists, stacks, queues, trees, and graphs, hash tables, bloom filters 등이 있습니다
- 시간복잡도와 공간복잡도: 데이터 구조를 선택할 때 데이터 구조의 시간 및 공간 복잡도를 고려하는 것이 중요합니다. 시간 복잡도는 특정 작업을 수행하는 데 걸리는 시간을 나타내고 공간 복잡도는 데이터 구조에서 사용하는 메모리 양을 나타냅니다. 이러한 복잡성을 이해하면 특정 작업에 가장 적합한 데이터 구조에 대한 정보에 입각한 결정을 내리는 데 도움이 될 수 있습니다.
자료구조의 종류
1. Arrays 와 Lists
Array와 List 는 가장 기본적인 자료구조입니다. 둘 다 데이터 요소들의 묶음을 저장하고 액세스하는 방법을 제공합니다.
- Arrays: 인접한 메모리 위치에 저장된 요소의 모음입니다. 각 요소는 Array 내에서 해당 위치를 나타내는 정수 값인 인덱스를 사용하여 액세스할 수 있습니다. Array의 크기는 고정되어 있습니다. 즉, Array이 생성되면 크기를 변경할 수 없습니다.Array은 인접한 메모리 위치에 저장된 요소의 모음입니다. 각 요소는 Array 내에서 해당 위치를 나타내는 정수 값인 인덱스를 사용하여 액세스할 수 있습니다. Array의 크기는 고정되어 있습니다. 즉, Array가 생성되면 크기를 변경할 수 없습니다.
- Dynamic Arrays: Dynamic Array은 런타임에 동적으로 크기를 조정할 수 있는 Array의 변형입니다. Dynamic Array가 최대 용량에 도달하면 더 큰 메모리 블록을 자동으로 할당하고 해당 요소를 새 메모리 위치에 복사할 수 있습니다. 따라서 Dynamic Array는 크기가 변경될 수 있는 많은 양의 데이터를 저장해야 하는 응용 프로그램에 적합합니다.
- Linked List는 각 요소가 List의 다음 요소를 가리키는 요소 모음입니다. Linked List는 비연속 메모리 위치에 저장되므로 요소에 고정 인덱스가 없습니다. 다른 요소를 이동할 필요 없이 연결된 목록에서 요소를 추가하거나 제거할 수 있으므로 Linked List이 Array보다 더 유연해집니다.
- Doubly Linked Lists : Doubly Linked Lists는 각 요소가 List의 다음 요소와 이전 요소를 모두 가리키는 Linked List의 변형입니다. 이렇게 하면 List의 양쪽 끝에서 요소를 추가하거나 제거할 수 있으므로 일반 Linked List보다 Doubly Linked Lists이 더 유연해집니다.
Arrays 와 Lists 는 서로 다른 사용 사례에 유용한 데이터 구조입니다. Arrays 는 인덱스를 사용하여 요소에 대한 빠른 액세스를 제공하는 반면 Linked List는 요소를 저장하고 조작하는 보다 유연한 방법을 제공합니다. 특정 작업에 적합한 데이터 구조를 선택하려면 Arrays 와 Lists 간의 유사점과 차이점을 이해하는 것이 중요합니다.
2. Stacks & Queues
Stacks 과 Queues는 요소 컬렉션을 저장하는 데 사용되며 요소에 액세스하고 제거하는 동작이 다릅니다.
Stacks (이하 스택)
스택은 LIFO(후입선출) 데이터 구조로, 스택의 맨 위에서 요소가 추가되고 제거됩니다. 다음은 Python에서 스택을 사용하는 방법입니다.
# Creating a stack
stack = []
# Adding elements to the stack
stack.append(1)
stack.append(2)
stack.append(3)
# Accessing the top element in the stack
print("The top element in the stack is:", stack[-1])
# Removing elements from the stack (LIFO)
print("The removed element from the stack is:", stack.pop())
# Printing the updated stack after removing an element
print("The updated stack is:", stack)output:
The top element in the stack is: 3
The removed element from the stack is: 3
The updated stack is: [1, 2]
Queues(이하 큐)
큐는 FIFO(선입선출) 데이터 구조로, 요소는 큐의 뒤에 추가되고 큐의 앞에서 제거됩니다. 다음은 Python에서 큐를 사용하는 방법입니다.
# Creating a queue
queue = []
# Adding elements to the queue
queue.append(1)
queue.append(2)
queue.append(3)
# Removing elements from the queue (FIFO)
print("The removed element from the queue is:", queue.pop(0))
# Printing the updated queue after removing an element
print("The updated queue is:", queue)output:
The removed element from the queue is: 1
The updated queue is: [2, 3]정리하면, 스택과 큐는 요소에 액세스하고 제거하는 동작이 다른 두 가지 기본 데이터 구조입니다. 스택은 LIFO 동작을 구현하고 큐는 FIFO 동작을 구현합니다.
Deque
Deque는 큐의 양쪽 끝에서 요소를 추가하고 제거할 수 있는 데이터 구조입니다. 이는 큐의 앞과 뒤 모두에서 요소에 액세스하고 제거할 수 있는 유연성을 제공합니다.
# Importing deque from collections module
from collections import deque
# Creating a deque
dq = deque()
# Adding elements to the deque
dq.append(1)
dq.appendleft(2)
dq.append(3)
dq.appendleft(4)
# Removing elements from the deque
print("The removed element from the right side of the deque is:", dq.pop())
print("The removed element from the left side of the deque is:", dq.popleft())
# Printing the updated deque after removing elements
print("The updated deque is:", dq)output:
The removed element from the right side of the deque is: 3
The removed element from the left side of the deque is: 4
The updated deque is: deque([2, 1])
3. Trees
그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다.
- Binary Trees: 이진 트리는 각 노드가 왼쪽 자식과 오른쪽 자식이라고 하는 최대 두 개의 자식을 갖는 트리 데이터 구조입니다.
- Binary Search Trees(BST): 모든 노드가 왼쪽 자손의 값보다 크거나 같고 오른쪽 자손의 값보다 작거나 같은 값을 갖는 이진 트리입니다. 이 속성은 BST에서 값을 검색하는 데 트리 높이에 비례하는 시간이 걸리므로 BST를 검색에 적합하게 만듭니다.
- Heap: 힙은 힙 속성을 충족하는 특수 트리 기반 데이터 구조입니다. B가 A의 자식 노드인 경우 키(A)는 키(B)에 대해 정렬되며 동일한 순서가 힙에 적용됩니다. 힙에는 두 가지 유형이 있습니다.
- Max Heap: Max Heap에서 상위 노드의 값은 하위 노드보다 크거나 같습니다.
- Min Heap: Min Heap에서 상위 노드는 하위 노드보다 작거나 같은 값을 가집니다.
- 힙은 일반적으로 우선 순위가 높은 요소가 낮은 우선 순위 요소보다 먼저 제공되는 우선 순위 대기열을 구현하는 데 사용됩니다
4. Tries
prefix tree라고도 하는 Trie는 큰 문자열 데이터 세트에서 키를 효율적으로 검색하는 데 사용되는 트리 기반 데이터 구조입니다. trie에서 각 노드는 문자열의 단일 문자를 나타내고 가장자리는 루트에서 노드까지의 문자 시퀀스를 나타냅니다. 단어의 끝은 특수 노드로 표시되거나 단어의 마지막 문자를 나타내는 노드에 부울 플래그를 설정하여 표시됩니다.
Trie는 맞춤법 검사기, 자동 완성 제안, IP 라우팅 등과 같은 다양한 애플리케이션에서 널리 사용됩니다. Trie는 동일한 접두사를 가진 많은 수의 문자열을 효율적으로 저장할 수 있다는 점에서 해시 테이블보다 이점이 있습니다.
5. Hash Tables(이하 해시 테이블)
해시 테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 데이터 유형을 구현하는 데이터 구조입니다. 해시 테이블은 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯 배열에 대한 인덱스를 계산합니다. 해시 테이블은 맵, 집합 및 사전을 포함하여 다른 많은 데이터 구조를 구현하는 데 사용됩니다. 또한 캐싱, 압축 등과 같은 다양한 알고리즘에도 사용됩니다. Python에서는 dict 가 해시 테이블을 구현합니다. Python의 dict 는 해당 값을 찾을 수 있는 배열의 인덱스에 키를 매핑하는 해시 함수를 사용하여 작동합니다.
6. Graphs(이하 그래프)
그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미합니다.. vertex는 정점, edge는 정점과 정점을 연결하는 간선이을 뜻합니다. 그래프는 두 정점 사이의 최단 경로 찾기, 그래프 연결 여부 확인, 최소 스패닝 트리 찾기 및 네트워크 흐름 문제 해결과 같은 많은 실제 문제를 나타내고 해결하는 데 사용할 수 있습니다.(DFS, BFS ,Dijkstra 등)
7. Bloom filters(블룸 필터)
블룸 필터는 요소가 집합의 구성원인지 여부를 테스트하는 데 사용되는 확률적 데이터 구조입니다. 맞춤법 검사기, 중복 감지, 데이터베이스 인덱싱과 같은 다양한 응용 프로그램에 사용됩니다.
결론
자료구조는 프로그래밍을 하는데 있어서 필수적인 부분은 아니라고 생각합니다. 다만, 평소에 자료구조에는 어떤 종류가 있으며 각각의 상황에 맞는 자료구조가 무엇인지 파악하고 있다면, 특정 상황에 맞는 자료구조를 선택하여 코드를 작성할 수 있을 것입니다. 효율적인 비즈니스 로직을 구현하거나 업무를 함에 있어서 리소스가 부족한 상황에서 문제상황을 해결하는데 있어 큰 도움이 되리라 생각합니다.
댓글