밤톨

밤톨의 작업 공간입니다.

[자료구조] 5.큐와 덱

큐에 대한 정의

큐

큐(Queue)는 선입선출(FIFO, First-In-First-Out) 구조를 가지고 있습니다. 즉, 먼저 들어온 데이터가 먼저 나가게 되는 자료구조입니다. 이러한 특성 때문에, 큐는 많은 분야에서 활용됩니다.

큐는 자체적으로 하나의 추상 자료형(Abstract Data Type)으로 정의됩니다. 추상 자료형은 데이터와 그 데이터에 대한 연산을 결합한 자료형으로, 구현 방법에 따라서 리스트, 배열, 집합 등 다양한 형태로 구현될 수 있습니다.

운영체제의 프로세스 스케줄링
- 운영체제에서는 프로세스를 스케줄링할 때, 큐를 이용하여 프로세스들을 순서대로 처리합니다.
네트워크 패킷 처리
- 네트워크에서 패킷은 큐를 이용하여 전송됩니다. 패킷은 먼저 도착한 순서대로 큐에 삽입되어, 먼저 전송되게 됩니다.
자원 할당
- CPU나 I/O 장치 등의 자원은 큐를 이용하여 할당됩니다. CPU를 할당받기 위해 프로세스는 큐에 들어가게 되며, 할당된 CPU는 자원을 반환하기 전까지 사용 가능한 큐에 들어가게 됩니다.
버퍼(Buffer)
- 버퍼(Buffer)는 데이터를 일시적으로 저장하는 메모리 영역을 말합니다. 버퍼에서는 데이터가 먼저 들어온 순서대로 처리되어야 합니다. 따라서, 버퍼는 큐를 이용하여 구현됩니다.

선형 큐의 문제와 원형 큐의 구조와 동작 원리

선형 큐

선형 큐(Linear Queue)는 배열을 이용하여 구현된 큐입니다. 선형 큐에서는 큐의 front와 rear를 각각 배열의 인덱스로 나타내고, 데이터가 들어올 때마다 rear 인덱스를 증가시키고, 데이터가 나갈 때마다 front 인덱스를 증가시킵니다. 선형 큐는 간단하고 구현하기 쉽기 때문에 많이 사용되지만, 몇 가지 문제점이 있습니다.

큐의 크기 제한

선형 큐에서는 배열의 크기를 미리 정해야 합니다. 큐의 크기를 초과하면, 새로운 데이터를 삽입할 수 없게 됩니다.

큐의 비효율적인 메모리 사용

선형 큐에서는 rear 인덱스가 배열의 끝에 도달하면, 새로운 데이터를 삽입할 수 없게 됩니다. 하지만, front 인덱스가 배열의 처음에 위치해 있을 때, 큐의 앞부분에 빈 공간이 있어도 이를 활용할 수 없습니다. 이러한 경우에는, 큐의 크기가 크더라도 실제로 저장 가능한 데이터의 수가 제한됩니다.

큐의 빈 공간 문제

선형 큐에서는 front와 rear 인덱스를 이용하여 큐의 빈 공간과 꽉 찬 상태를 구분합니다. 하지만, front와 rear 인덱스가 같은 경우, 큐가 비어있는지 꽉 찬 상태인지 구분할 수 없습니다.

위와 같은 문제점을 해결하기 위해, 원형 큐(Circular Queue)와 연결 큐(Linked Queue)가 개발되었습니다. 여기서는 원형 큐에 대해 다루겠습니다.

원형 큐

원형 큐(Circular Queue)는 배열을 이용하여 구현된 큐의 한 종류로, 큐의 처음과 끝이 연결된 형태로 구현됩니다. 따라서, rear 인덱스가 배열의 끝에 도달하면, 다시 배열의 처음으로 돌아가서 데이터를 삽입할 수 있습니다. 이를 통해, 큐의 크기를 미리 정해놓지 않아도 되고, 빈 공간을 활용할 수 있습니다.

원형 큐에서는 front와 rear 인덱스를 이용하여 큐의 빈 공간과 꽉 찬 상태를 구분합니다. front와 rear 인덱스가 같은 경우, 큐가 비어있는지 꽉 찬 상태인지 구분할 수 없습니다. 따라서, 큐가 비어있는지 구분하기 위해서는, front와 rear 인덱스를 같은 값으로 설정하지 않고, front 인덱스와 rear 인덱스 사이에 최소한 한 개의 빈 공간을 유지해야 합니다.

원형 큐에서는 삽입 연산과 삭제 연산을 수행할 때, front와 rear 인덱스를 적절하게 조절해주어야 합니다. 데이터를 삽입할 때는, rear 인덱스를 증가시키고, 데이터를 삭제할 때는, front 인덱스를 증가시킵니다.

원형 큐는 선형 큐에 비해 데이터를 더 효율적으로 활용할 수 있으며, 큐의 크기를 동적으로 조절할 수 있는 장점이 있습니다. 하지만, front와 rear 인덱스를 적절하게 조절해주어야 하기 때문에 구현이 복잡해질 수 있습니다.

덱과 우선순위 큐의 개념과 동작 원리

덱

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 따라서, 덱은 큐와 스택의 특성을 모두 가지고 있습니다. 덱은 선형 구조를 가지고 있으며, 데이터를 한쪽에서 삽입하고, 다른 한쪽에서 삭제할 수 있습니다.

덱의 가장 큰 단점은 데이터를 삽입하거나 삭제할 때, 덱의 양쪽 모두에서 이를 수행할 수 있기 때문에, 덱에 데이터가 충분히 많은 경우에는 데이터를 찾아내는 것이 어려울 수 있다는 점입니다. 이를 해결하기 위해서는 이중 연결 리스트(Double-Linked List)를 이용하여 덱을 구현할 수 있습니다.

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조로, 덱의 양쪽 끝을 가리키는 front와 rear 포인터를 이용하여 덱을 구현합니다. 이를 통해, 덱의 양쪽에서 삽입과 삭제를 수행할 때도, 해당 위치를 빠르게 찾아내어 삽입과 삭제를 수행할 수 있습니다.

하지만, 이중 연결 리스트를 이용하여 덱을 구현하는 경우에는 추가적인 메모리 공간이 필요하고, 덱의 구현이 복잡해지기 때문에, 사용하는 상황에 따라 적합한 자료구조를 선택해야 합니다.

우선순위 큐

우선순위 큐(Priority Queue)는 큐(Queue)의 일종으로, 각각의 요소(Element)가 우선순위를 가지고 있어, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다. 즉, 큐의 요소가 정렬되어 있는 상태로 삽입되고, 가장 우선순위가 높은 요소가 먼저 삭제됩니다.

우선순위 큐는 다음과 같은 기본 연산을 가지고 있습니다.

insert(item, priority): item을 우선순위(priority)에 따라 적절한 위치에 삽입합니다.
delete_max(): 가장 높은 우선순위를 가진 item을 삭제하고, 삭제된 item을 반환합니다.
find_max(): 가장 높은 우선순위를 가진 item을 반환합니다.

우선순위 큐는 여러 분야에서 활용되며, 힙(Heap) 자료구조를 이용하여 구현됩니다. 힙은 이진 트리(Binary Tree)의 일종으로, 부모 노드의 우선순위가 항상 자식 노드의 우선순위보다 높은 구조를 가지고 있습니다.

우선순위 큐는 다익스트라 알고리즘(Dijkstra Algorithm), 허프만 코딩(Huffman Coding), 우선순위 스케줄링(Priority Scheduling) 등에서 사용됩니다.

파이썬 리스트를 이용한 큐, 덱, 우선순위 큐의 구현 방법

원형 큐

MAX_QSIZE = 10
class CircularQueue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX_QSIZE
    def isEmpty(self): return self.front == self.rear
	def isFull(self): 
        return self.front == (self.rear+1)%MAX_QSIZE
    def clear(self):
        self.front = self.rear
    
    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear+1)%MAX_QSIZE
            return self.items[self.rear] = item
    
    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1)%MAX_QSIZE
            return self.items[self.front]
        
    def peek(self):
		if not self.isEmpty():
            return self.items[(self.front + 1)%MAX_QSIZE]
    def size(self):
        return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
    
    def display(self):
        out = []
        if self.front < self.rear:
            out = self.items[self.front+1:self.rear+1]
        else:
            out = self.items[self.front+1:MAX_QSIZE] + self.items[0:self.rear+1]
            print(out)

덱

class CircularDeque(CircularQueue):
    def __init__(self):
		# front, rear, items와 같은 멤버 변수는 추가로 선언하지 않음
        super().__init__()
        
    # 기존 메소드 재활용
    def addRear(self, item):
        self.enqueue(item)
    def deleteFront(self):
        return self.dequeue()
    def getFront(self):
        return self.peek()
    
    # 추가 구현 메소드
    def addFront(self, item):
		if not self.isFull():
            self.front = (self.front - 1 + MAX_QSIZE) % MAX_QSIZE
            self.items[self.front] = item

    def deleteRear(self):
        if not self.isEmpty():
            item = self.items[self.rear]
            self.rear = (self.rear - 1 + MAX_QSIZE) % MAX_QSIZE
            return item
        
    def getRear(self):
        return self.items[self.rear]

우선순위 큐

# python list를 이용한 구현
class PriorityQueue:
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return len(self.items) == 0
    def size(self):
        return len(self.items)
    def clear(self):
        self.items = []
        
    def enque(self, item):
        self.items.append(item)
        
    def findMaxIndex(self):
        if self.isEmpty():
            return None
        else:
            highest = 0
            for i in range(1, self.size()):
                if self.items[i] > self.items[highest]:
                    highest = i
            return highest
        
    def dequeue(self):
        highest = self.findMaxIndex()
        if highest is not None:
            return self.items.pop(highest)
        
    def peek(self):
        highest = self.findMaxIndex()
        if highest is not None:
            return self.items[highest]

상속을 이용하여 새로운 클래스를 만들고 사용하는 방법

파이썬에서는 상속을 이용하여 새로운 클래스를 만들 수 있습니다. 상속은 기존 클래스의 모든 속성을 새로운 클래스에게 상속받아 사용할 수 있는 방법입니다. 이를 통해, 코드의 중복을 줄일 수 있고, 기존 클래스의 기능을 유지하면서 새로운 기능을 추가할 수 있습니다.

상속을 이용하여 새로운 클래스를 만들 때는 다음과 같은 형식을 따릅니다.

class NewClass(BaseClass):
    def __init__(self, arg1, arg2, ...):
        #super() 함수는 부모 클래스(BaseClass)의 메서드를 호출하기 위한 함수입니다.
        super().__init__(arg1, arg2, ...)
        # 새로운 클래스에서 추가적으로 정의할 속성과 메서드들을 작성합니다.

super().__init__() 함수를 호출하면, BaseClass의 __init__() 메서드를 먼저 실행한 후, 새로운 클래스(NewClass)에서 추가적으로 정의한 속성과 메서드들을 실행합니다.

예를 들어, 기존 클래스인 Person 클래스에서 이름(name)과 나이(age) 속성을 가지고, say_hello() 메서드를 정의한 후, 상속을 이용하여 새로운 클래스인 Student 클래스를 만드는 경우, 다음과 같은 코드를 작성할 수 있습니다.

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def say_hello(self):
        print("Hello, my name is", self.name, "and I am", self.age, "years old.")

class Student(Person):
    def __init__(self, name, age, grade):
        super().__init__(name, age)
        self.grade = grade
    
    def say_hello(self):
        super().say_hello()
        print("I am a student in grade", self.grade)

이제 Student 클래스의 객체를 생성하여 say_hello() 메서드를 실행하면, 다음과 같은 결과를 얻을 수 있습니다.

s = Student("Alice", 20, 3)
s.say_hello() # "Hello, my name is Alice and I am 20 years old."
# "I am a student in grade 3"

우선순위 큐를 이용한 전략적 미로 탐색 방법

우선순위 큐를 이용한 전략적 미로 탐색 방법은 A* 알고리즘이라고도 불리며, 지정된 출발점에서 목표지점까지의 최단경로를 탐색하는 알고리즘입니다. 이 알고리즘은 다음과 같은 방식으로 작동합니다.

출발점에서 시작하여, 현재 위치와 그 위치까지의 비용을 우선순위 큐에 넣습니다.
우선순위 큐에서 비용이 가장 적게 드는 위치를 꺼내어 방문합니다.
방문한 위치에서 이동 가능한 모든 위치와 그 위치까지의 비용을 계산합니다.
이동 가능한 위치를 우선순위 큐에 넣습니다.
우선순위 큐에서 다시 비용이 가장 적게 드는 위치를 꺼내어 방문합니다.
위의 과정을 목표지점에 도착할 때까지 반복합니다.

이 알고리즘에서는 현재 위치에서 목표지점까지의 예상 비용을 계산하는 휴리스틱 함수(Heuristic Function)를 사용하여, 비용을 계산합니다. 이 휴리스틱 함수는 현재 위치에서 목표지점까지 직선거리 등의 예상 비용을 계산합니다.

예를 들어, 10x10 크기의 미로에서 출발점(0, 0)에서 목표지점(9, 9)까지의 최단 경로를 탐색하는 경우, 다음과 같은 코드를 작성할 수 있습니다.

from queue import PriorityQueue

def heuristic(node, goal):
    # 현재 위치('node')에서 목표지점('goal')까지의 직선거리를 계산합니다.
    dx = abs(node[0] - goal[0])
    dy = abs(node[1] - goal[1])
    return dx + dy

def astar(maze, start, goal):
    # 최소 비용으로 이동할 수 있는 경로를 탐색
    frontier = PriorityQueue()
    frontier.put(start, 0)
    # 현재 노드의 이전 노드를 저장하는 딕셔너리
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break

        for next_node in neighbors(maze, current):
            new_cost = cost_so_far[current] + cost(maze, current, next_node)
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost + heuristic(next_node, goal)
                frontier.put(next_node, priority)
                came_from[next_node] = current

    return came_from, cost_so_far

astar() 함수는 frontier에서 비용이 가장 적게 드는 위치(current)를 꺼내어 방문합니다. 그리고 해당 위치에서 이동 가능한 모든 위치를 계산하고, 이동 가능한 위치를 frontier에 넣습니다. 이때, cost_so_far 딕셔너리를 이용하여 각 위치까지의 비용을 계산합니다.

이후, frontier에서 다시 비용이 가장 적게 드는 위치를 꺼내어 방문합니다. 이 과정을 반복하여 목표지점에 도착하면 탐색을 종료합니다.

위의 코드에서 neighbors() 함수와 cost() 함수는 각각 현재 위치에서 이동 가능한 위치와 현재 위치와 이동 가능한 위치까지의 비용을 계산하는 함수입니다. 이 함수들은 각각 미로의 구조에 따라 다르게 작성될 수 있습니다.

이처럼 우선순위 큐를 이용한 전략적 미로 탐색 방법은 A* 알고리즘을 이용하여 최단 경로를 탐색하는 것이 가능합니다.