Abstract
자료 구조란?
대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조를 의미
데이터 특성에 따라서, 체계적인 데이터 구조화가 필요하며, 이러한 데이터 구조는 코드의 효율성, 성능을 결정함.
대표적인 자료구조로는 배열(Array), 스택(Stack), 큐(Queue), 링크드 리스트(Linked List), 해쉬 테이블(Hash Table), 힙(Heap) 등이 존재하고
Python에서는 대표적으로 List, tuple, set, dictionary가 존재하며, 위의 자료구조 대부분을 모두 구현이 가능함.
1. Array(배열)
- 배열은 같은 종류의 데이터를 순차적으로 저장하는 자료구조임
python에서 List와 같은 개념 - index를 통해 직접 접근이 가능하다는 점.
장점 : index를 통한 빠른 접근이 가능하다는 점.
단점 : 데이터 추가와 삭제에 비용이 많이 사용된다는 점. 데이터 추가시, 공간이 많이 필요하며, 삭제 시 빈 공간이 생겨 이를 관리해주어야 함. 길이 조절이 어렵다는 점
파이썬 구현코드
# 1차원 배열 = 리스트
data = [1, 2, 3, 4, 5]
string1 = 'Hello World'
print(data[3]) # 4 출력
print(string1[3]) # l 출력
# 2차원 배열
data2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(data[1][0]) # 4 출력1-1. Linked List(연결리스트)
📌 Linked list의 특징
대조적으로, 연결 리스트라고도 불리는 Linked List는 배열과 달리 연결되지 않고, 떨어진 곳에 존재하는 데이터를 경로로 지정하여 관리하는 데이터 구조임. 파이썬에서는 List가 Linked List 기능까지 지원
Node: 데이터 저장 단위로, 데이터 값 + 포인터로 구성
Pointer: 각 노드 안에서, 다음이나 이전의 노드의 주소를 가지는 값을 의미함.
📌 Linked list의 장단점
장점 : 미리 데이터 공간을 미리 할당할 필요가 없음.
단점 : 연결을 위한 별도 데이터 공간 (아래 예제에서는 next 변수)가 필요하므로 효율이 낮고 데이터를 찾는데 접근성이 낮아 처리속도가 느림. 중간 데이터 삭제시, 앞 뒤를 모두 고려하여 재구성하는 코드를 작성해야 되는 소요 있음.
📌 파이썬 구현코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
#노드는 data를 저장하는 변수와 다음 노드를 가리키는 포인터가 있음. 해당 코드에서는 next라는 변수
class LinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
node = self.head
while node.next:
node = node.next
node.next = new_node
def delete(self, data):
node = self.head
if node.data == data:
self.head = node.next
del node
else:
while node.next:
next_node = node.next
if next_node.data == data:
node.next = next_node.next
del next_node
else:
node = node.next
def find(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
def print(self):
node = self.head
while node:
print(node.data)
node = node.next2. Stack(스택)
스택(stack)이란 쌓아 올린다는 것을 의미함.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말함.
📌 스택의 특징
스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며,
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.
이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.
그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다. (그 유명한 사이트 "stack overflow " 의 이름이 여기서 유래 된 것!)
📌 스택의 활용 예시
스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
📌 스택의 장단점
장점 : 구조가 단순하고, 구현이 쉬움, 데이터 저장 / 불러오는 속도가 빠릅니다.
단점 : 데이터 최대 갯수를 사전에 정해주어야 함. (python 재귀 함수는 1000번까지 가능), 저장 공간 낭비가 발생할 수 있음. (미리 최대 갯수를 넣을 공간을 확보하기 때문)
📌 파이썬 구현코드
<class ListStack:
def __init__(self):
self.my_list = list()
def push(self, data):
self.my_list.append(data)
def pop(self):
return self.my_list.pop()
3. Queue(큐)
Queue 의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것을 의미한다.
따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이
선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.
📌 큐의 특징
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.
이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.
큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
접근방법은 가장 첫 원소와 끝 원소로만 가능
가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.
📌 큐의 활용 예시
큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
📌 파이썬 구현코드
import queue
# queue() 일반적인 큐 자료구조
data_queue = queue.Queue()
data_queue.put(1) # 1
data_queue.put(2) # 1 - 2
data_queue.put(3) # 1 - 2 - 3
data_queue.get() # 1 출력
data_queue.get() # 2 출력
# LifoQueue() 나중에 입력된 데이터가 먼저 출력되는 구조(Stack과 동일)
data_queue = queue.LifoQueue()
data_queue.put(1) # 1
data_queue.put(2) # 2 - 1
data_queue.put(3) # 3 - 2 - 1
data_queue.get() # 3 출력
data_queue.get() # 2 출력
#PriorityQueue() 데이터마다 우선순위를 지정하여, 정렬된 큐로, 우선순위 높은 순으로 출력하는 자료 구조
data_queue = queue.PriorityQueue()
data_queue.put((10, 1)) # (10,1)
data_queue.put((5, 2)) # (5, 2) - (10,1)
data_queue.put((15, 3)) # (5, 2) - (10, 1) - (15,3)
data_queue.get() # (5,2) 출력
data_queue.get() # (10, 1) 출력
References
