[자료구조 1] 큐(Queue) 활용하기

in Problem Solving on Data Structure


큐(Queue)는 무엇이고 어디에 활용되는지 알아봅니다. 그리고 큐와 관련된 문제를 풀어봅니다.

큐 (Queue)

큐(Queue)는 순서대로 처리되는 구조로 실생활에서도 많이 보입니다. 대표적인게 줄서기 거든요.

스택처럼 큐도 구조를 설명하기 보다는 어디에 활용되고 있는지를 자세히 정리해보겠습니다.

큐의 활용

큐는 특히 실생활에서 자주 보입니다. 은행에 가면 순서표를 받고 기다립니다. 은행원이 준비되면 하나씩 번호를 부르고 업무를 처리하는 방식으로 이루어지는 것도 큐입니다.

조금 더 프로그래밍 관점에서 설명을 해보겠습니다. 유튜브(YouTube)처럼 동영상 스트리밍 서비스를 하려고 합니다. 동영상 정보를 빠르게 받아서 보여주면 문제가 없지만 만약 네트워크 문제로 인해 동영상 정보를 다 가져오지 못했는데 사용자는 계속 보여달라고 요청하는 경우에는 기다려야하는 버퍼링 현상이 발생합니다.

위 그림은 유튜브에서 재생된 동영상입니다. 빨간색은 현재 재생된 위치를, 회색은 현재 버퍼에 무사히 정보를 저장하여 바로 재생할 수 있는 구간을, 짙은 회색은 아직 정보가 없는 구간을 나타냅니다.

이렇게 큐를 이용하여 영상 정보를 받은 만큼 큐에 계속 저장하고 사용자가 재생하면 조금씩 영상을 꺼내 보여주면 되는 것입니다.

이 외에도 그래프 탐색을 할 때 BFS(Breadth First Searach, 너비 우선 탐색)을 구현하려면 큐를 필요로 합니다. 그래프에 대한 이해가 필요하니 자세한 설명은 생략하겠습니다.

예제: 조세푸스 문제

이 문제는 이전 포스팅 배열과 리스트는 각각 언제 사용해야 할까?에서 다뤘던 문제입니다.

문제 링크:: 조세푸스 문제(https://www.acmicpc.net/problem/1158)

자세한 문제 설명은 위 링크로 들어가셔서 확인하시고 직접 풀어보세요!

다시 가져온 이유는 큐를 이해하는데 괜찮은 예제인 것 같습니다. 이전 포스팅에서 리스트로 접근한 방식에서는 리스트의 포인터가 움직이는 것으로 풀었습니다.

이와는 반대로 리스트의 포인터가 움직이지 않고, 큐를 이용하면 데이터의 위치를 옮겨가는 관점으로도 풀 수 있습니다.

풀이

사람을 큐에 넣고, 제거할 사람만 큐에서 빼고 나머지는 다시 넣는 방법을 생각하면 됩니다.

  • 큐의 첫번째 사람을 제거한다.
  • 큐의 맨 앞 사람을 맨 뒤로 보내는 것을 K-1번 반복한다.

코드로 보면 아래와 같습니다.

queue<int> q;
for (int i = 1; i <= N; i++) q.push(i);

printf("<");
int m = 1;
while (!q.empty())
{
   int t = q.front();
   q.pop();

   if (m != M)
   {
      q.push(t);
      m++;
   }
   else
   {
      m = 1;
      if (!q.empty()) printf("%d, ", t);
      else printf("%d",t);
   }
}

다른 문제 추천

  • 큐: (https://www.acmicpc.net/problem/10845)
  • 프린터큐: (https://www.acmicpc.net/problem/1966)

큐가 직접적인 알고리즘 문제로는 잘 나오지 않기 때문에, 큐 자체를 이해하는 것은 위의 문제들로 정리해도 충분한 것 같습니다. 다만 BFS 같은 알고리즘을 사용해야 할 때는 큐를 활용할 줄 알아야 하기 때문에 기본적인 배경지식으로 이해하고 있기를 바랍니다.