자료구조

자료구조(Data Structure)란 데이터를 구성하고, 저장하고, 관리하며, 이를 효율적으로 사용하기 위한 방법론이다. 데이터를 어떤 방식으로 저장하고 조작할 것인가에 따라 알고리즘의 성능이 크게 달라지므로, 자료구조는 알고리즘 설계의 중요한 부분이다.

대표적인 자료구조로는 배열, 연결리스트, 스택, 큐, 트리, 그래프, 해시 테이블 등이 있다. 이 중에서도 각각의 자료구조는 특정한 목적을 가지고 있으며, 특정한 알고리즘을 적용하기 위해서는 적합한 자료구조를 선택해야 한다.

예를 들어, 검색 연산을 수행할 때는 이진 탐색 트리나 해시 테이블과 같은 자료구조를 사용하며, 스택과 큐는 프로그램의 흐름을 제어하기 위해 사용된다. 또한, 그래프와 트리 자료구조는 다양한 문제를 해결하는 데에 활용된다.

자료구조를 잘 활용하면, 불필요한 메모리 사용을 줄이고, 연산 속도를 향상시킬 수 있다. 또한, 프로그램의 가독성과 유지보수성을 향상시키는 데에도 큰 도움을 준다.

스택 (Stack)

데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 원칙에 따라 동작한다.

스택은 보통 배열이나 연결 리스트를 이용하여 구현되며, 데이터를 삽입하는 연산을 push, 데이터를 꺼내는 연산을 pop이라고 부른다.

스택은 함수 호출 시에 사용되는 호출 스택(Call Stack)이나, 수식 계산 등에 활용된다. 함수 호출 시에는 함수가 호출되면 호출 스택에 함수의 정보를 저장하고, 함수 실행이 끝나면 스택에서 함수의 정보를 꺼내어 반환값을 반환한다. 수식 계산에는 후위 표기법(Postfix Notation)을 이용하여 수식을 스택에 저장한 후, 스택에서 연산을 수행하면서 결과를 계산한다.

스택은 자료를 저장할 수 있는 공간이 제한적이기 때문에, 스택이 가득 차서 더 이상 자료를 저장할 수 없는 경우에는 스택 오버플로(Stack Overflow)가 발생한다. 반대로, 스택이 비어있는 상태에서 데이터를 꺼내려는 경우에는 스택 언더플로(Stack Underflow)가 발생한다.

스택은 삽입과 삭제 연산이 모두 상수 시간( O(1) )에 이루어지기 때문에, 자료를 저장하고 꺼내는 작업이 빈번한 경우에 유용하게 사용될 수 있다.

# ex) 

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, data):            # 데이터를 삽입
        self.stack.append(data)
    
    def pop(self):                   # 데이터를 삭제
        if self.is_empty():
            return None
        else:
            return self.stack.pop()
    
    def is_empty(self):              # 스택이 비어있는지 여부를 반환
        return len(self.stack) == 0
    
    def peek(self):                  # 스택의 최상단 데이터를 반환
        if self.is_empty(): 
            return None
        else:
            return self.stack[-1]

큐 (Queue)

스택과 같이 데이터를 임시로 저장하는 자료구조, 선입선출(First-In-First-Out, FIFO)의 구조를 가지고 있다. 큐는 말 그대로 일렬로 늘어선 사람들이 대기줄을 서는 것과 같은 구조다.

예를 들어, 새로운 자료가 큐에 들어가면, 큐의 가장 마지막에 저장됩니다. 그리고 자료를 꺼낼 때는 가장 먼저 저장된 자료부터 꺼내어져 나온다. 이러한 특성 때문에, 먼저 들어간 자료가 먼저 나오는 일이 발생할 때 유용하게 사용된다.

큐는 컴퓨터의 운영체제나 프로그래밍에서 많이 사용된다. 예를 들면, 시스템 자원을 공유하는 다중 프로세스 환경에서, 여러 개의 프로세스가 자원에 접근하게 될 때, 자원에 대한 요청을 처리하는 순서가 중요하다. 이때 요청을 처리하는 순서는 큐의 구조를 활용하여 결정된다.

스택과 마찬가지로, 큐 역시 연결리스트(linked list)나 배열(array)로 구현될 수 있다. 각각의 방식에 따라, 연산에 소요되는 시간복잡도가 다르기 때문에, 상황에 따라 적절한 자료구조를 선택하여 사용해야 한다.

# ex)

class Queue:
    def __init__(self):
        self.items = []
        
    def enqueue(self, item):     # enqueue 메소드는 리스트의 append 메소드를 이용하여 요소를 큐의 맨 뒤에 추가
        self.items.append(item)
        
    def dequeue(self):           # dequeue 메소드는 리스트의 pop 메소드를 이용하여 큐의 맨 앞 요소를 삭제하고 리턴
        if self.is_empty():
            return None
        return self.items.pop(0)
    
    def is_empty(self):          # is_empty 메소드는 큐가 비어있는지 여부를 체크
        return len(self.items) == 0
    
    def size(self):              # size 메소드는 큐의 크기를 반환
        return len(self.items)

우선순위 큐

우선순위 큐는 데이터를 저장하는 자료구조 중 하나로, 각각의 데이터에 우선순위를 부여하여 데이터를 삽입하거나 삭제할 때 우선순위가 높은 데이터부터 처리하는 자료구조이다. 우선순위 큐는 일반적으로 힙(heap)을 이용해서 구현된다.

힙(heap)은 완전 이진트리(Complete Binary Tree)를 기반으로한 자료구조로, 최대값이나 최소값을 빠르게 찾아내기 위한 연산을 제공하는 이진 트리이다. 이진 트리는 부모 노드와 자식 노드 간의 크기나 우선순위를 비교해서 정렬되는 자료구조인데, 힙에서는 루트 노드가 최대값 또는 최소값이 된다. 따라서, 힙에서 데이터를 삽입하거나 삭제할 때는 이진트리의 규칙을 지키면서 최대값이나 최소값을 찾아내도록 구현된다. 이를 위해 힙은 일반적으로 배열을 사용하여 구현되며, 부모와 자식간의 관계를 쉽게 유지할 수 있다.

파이썬에서는 heapq 라이브러리를 사용하여 간단하게 우선순위 큐와 힙을 구현할 수 있다. 이 라이브러리에서는 최소 힙(Min Heap)만을 지원하며, 우선순위 큐는 리스트와 힙(heap)을 활용하여 구현된다. 리스트를 이용하여 우선순위 큐를 구현할 경우, 데이터의 추가 및 삭제 연산에 O(n)의 시간 복잡도가 소요되지만, heapq 라이브러리를 이용하면 O(log n)의 시간 복잡도로 구현할 수 있다.