[알고리즘 공부] #5 큐 알고리즘(Queue) 알고리즘 with Python

큐 알고리즘(Queue)

어떤 알고리즘일까?

큐 알고리즘은 자료구조 알고리즘으로 먼저 들어간 값이 먼저 나온다고 해서 First In First Out 즉 FIFO또는 나중에 들어간 값이 나중에 나온다고 해서 Last In Last Out 즉 LILO 구조를 가지고 있다고 말한다.

출처 : [알고리즘] Queue(큐 알고리즘)_JAVA[자바] 백준-18258번 풀이 — A steady developer (tistory.com)

큐 알고리즘은 위에 사진으로 이해하는 것이 쉽다. 사진을 보면 알 수 있듯이 젤 먼저 1이 들어오고 그 다음으로 3과 21이 들어온다. 그리고 나서 값이 나오는 걸 볼 수 있는데 가장 먼저 들어온 1이 나오고 그 다음으로 3이 나오고 마지막으로 21이 나오는 것을 알 수 있다. 이런식으로 큐는 아까 말한 FIFO(LILO) 구조를 가지고 있다.

 

장점과 단점

• 장점
  큐는 데이터가 입력된 순서대로 처리되므로, 순서가 중요한 작업에서 유용한다.
  또 큐 자료구조는 직관적이고 단순해서 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있다.
  큐에서의 삽입과 삭제는 O(1) 시간 복잡도를 가지기 때문에 효율적인 연산이 가능하다.
  연결 리스트를 사용하면 크기가 가변적이기 때문에, 크기에 제한 없이 연산을 수행할 수 있다.
• 단점
  큐는 나가는 데이터와 들어오는 데이터만 접근할 수 있기 때문에, 중간에 있는 데이터에 접근하는 것은 비효율 적이다. 따라서 중간에 있는 특정 요소를 찾거나 삭제해야 하는 경우, 전체를 탐색해야 할 수도 있다.
  또한 그냥 리스트를 이용해 큐를 구현한다고 했을 때, 새로운 값이 들어오거나 이미 있던 값을 삭제해야 할 경우, 이미 있던 모든 값의 인덱스를 수정해줘야 하기 때문에 효율성이 떨어진다.

 

언제 사용하는가?

• 데이터 스트림 처림
  실시간 데이터 스트림을 처리할 때, 데이터가 도착한 순서대로 처리할 수 있다.
• 작업 대기열
  프린터, CPU 작업 스케줄링 등에서 작업을 순서대로 처리할 때 사용한다.
• 그래프 탐색
  BFS알고리즘에서 큐를 사용하여 시작 지점에서 가장 가까운 지점부터 차례대로 탐색한다.
• 캐시 시스템
  FIFO 캐시 알고리즘에서는 캐시가 가득 찬 경우 가장 오래된 캐시를 먼저 삭제한다.
• 전체적으로
  전체적으로 큐 알고리즘은 데이터의 입력 순서가 중요할 때 사용한다.

알고리즘 사용 예제

식당 대기줄 관리 시스템

• 문제설명
  먼저 입력된 고객의 데이터를 앞에 두고 그 이후에 입력된 데이터들은 순차적으로 뒤로 배치한다. 그 후 고객이 앉을 자리가 생기면 가장 앞에 있는 고객을 대기줄에서 제거한다.
  
  한 식당에서는 고객들이 대기줄에 서서 자리를 기다리고 있다. 식당에는 좌석이 한정되어 있어, 고객들은 입장 순서대로 자리에 앉을 수 있다. 이 문제는 고객이라는 데이터의 입장 순서가 중요한 문제이므로, 큐 알고리즘을 사용하여 해결할 수 있다.

 

• 각 줄마다 하나의 명령어가 입력됩니다.
• ENQUEUE 고객이름: 고객이름이 대기줄에 줄을 섭니다.
• DEQUEUE: 대기줄에서 가장 앞에 있는 고객이 자리에 앉습니다.
• PRINT: 현재 대기줄에 있는 모든 고객의 이름을 순서대로 출력합니다.

위 입력 조건에 맞춰 코드를 작성한다.

• CODE

def enqueue(queue, item):
    queue.append(item)
 
def dequeue(queue):
    if queue:
        return queue.pop(0)
    else:
        return "EMPTY"
 
def print_queue(queue):
    if queue:
        print(" ".join(queue))
    else:
        print("EMPTY")
 
queue = []
 
while True:
    command = input().strip()
    if command.startswith("ENQUEUE"):
        _, name = command.split()
        enqueue(queue, name)
    elif command == "DEQUEUE":
        result = dequeue(queue)
        if result != "EMPTY":
            print(result)
    elif command == "PRINT":
        print_queue(queue)
    elif command == "EXIT":
        break

위에 코드는 입력 조건에 맞춰 큐를 구현하여 식당 대기줄 관리 시스템을 만든 것이다.

---