[코딩 테스트 합격자 되기 - 4주차] 큐(Queue)

큐(Queue)는 데이터를 저장하는 자료구조 중 하나로, 데이터를 일렬로 나열한 선형구조입니다. 큐는 데이터를 넣는 Enqueue(인큐)와 데이터를 빼내는 Dequeue(디큐) 연산을 지원하며, 데이터는 First in First Out (FIFO)의 원칙을 따릅니다. 즉, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다.

큐의 주요 특징과 용어 :

1. Push : 큐에 새로운 데이터를 추가하는 작업입니다. 새로운 데이터는 큐의 뒤쪽(Rear)에 추가됩니다.
2. Pop : 큐의 가장 앞쪽(Front)에 있는 데이터를 제거하고 반환하는 작업입니다. 가장 먼저 추가된 데이터가 먼저 제거됩니다.
3. Front : 큐의 가장 앞쪽에 있는 데이터를 조회하는 작업입니다.
4. Rear : 큐의 가장 뒤쪽에 있는 데이터를 조회하는 작업입니다.
5. IsEmpty : 큐가 비어 있는지 여부를 확인하는 작업입니다.
6. Size : 큐에 현재 저장된 데이터의 개수를 반환하는 작업입니다.

큐는 주로 작업이나 데이터를 일시적으로 저장하고 나중에 처리할 때 사용됩니다. 예를 들어, 프로세스 스케줄링, 대기열 관리, 네트워크 데이터 전송 등의 상황에서 큐가 유용하게 활용됩니다.

큐는 배열(Array)이나 연결리스트(Linked List)를 사용하여 구현될 수 있습니다. 배열을 사용하면 큐의 크기가 고정되어 있을 때 효율적으로 구현될 수 있고, 연결리스트를 사용하면 크기를 동적으로 조절할 수 있습니다.

큐(Queue)는 다양한 종류가 있으며, 각각의 종류는 특정한 상황이나 문제에 대한 해결책으로 사용됩니다. 몇 가지 주요한 큐의 종류를 살펴보겠습니다.

각 종류의 큐는 특정한 사용 사례에 맞게 선택되며, 알고리즘 및 시스템 구현에서 필요에 따라 적절한 큐를 선택하는 것이 중요합니다.

큐는 여러 분야에서 다양하게 활용되며, 컴퓨터 과학에서는 다양한 알고리즘과 자료구조에 쓰입니다.

큐는 주로 데이터를 임시로 저장하거나, 작업을 순차적으로 처리해야 하는 상황에서 활용됩니다. 예를 들어 프로세스 스케줄링, 너비 우선 탐색(BFS), 대기열 관리 등에서 큐가 사용됩니다.

from collections import deque

class Queue :
    def __init__(self):
        self.queue = deque()

    def is_empty(self):
        return len(self.queue) == 0

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty() :
            return self.queue.popleft()
        else :
            raise IndexError("dequeue from an empty queue")

    def front(self):
        if not self.is_empty() :
            return self.queue[0]
        else :
            raise IndexError("front from an empty queue")

    def rear(self):
        if not self.is_empty() :
            return self.queue[-1]
        else :
            raise IndexError("rear from an empty queue")

    def size(self):
        return len(self.queue)

# 큐 생성
my_queue = Queue()

# 데이터 추가
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)

# 큐 크기 확인
print("큐 크기 : ", my_queue.size())

# 큐의 앞 데이터 확인
print("앞 데이터 : ", my_queue.front())

# 큐의 뒷 데이터 확인
print("뒷 데이터 : ", my_queue.rear())

# 큐에서 데이터 제거
dequeued_item = my_queue.dequeue()
print("제거된 데이터 : ", dequeued_item)

# 큐가 비어있는지 확인
print("큐가 비어있는지 확인 : ", my_queue.is_empty())

몸풀기 문제

요세푸스 문제

# from collections import deque

# def solution(n, k) :
#     q = deque(range(1, n + 1))
#     while len(q) > 1 :
#         for _ in range(k - 1) :
#             q.append(q.popleft())

#             q.popleft()
#     return q[0]

def solution(n, k) :
    q = [i for i in range(1, n + 1)]
    while len(q) > 1 :
        for _ in range(k - 1) :
            q.append(q.pop(0))

            q.pop(0)

    return q[0]

합격자가 되는 모의 테스트

카드 뭉치

from collections import deque

def solution(cards1, cards2, goal):
    # cards와 goal을 deque로 변환
    card1 = deque(cards1)
    card2 = deque(cards2)
    goal = deque(goal)

    while goal :
        if card1 and card1[0] == goal[0] :
            card1.popleft()
            goal.popleft()
        elif card2 and card2[0] == goal[0] :
            card2.popleft()
            goal.popleft()
        else :
            return 'No'
    return 'Yes'