Q.큐를 활용하는 실무 사례를 말해주세요
| 사례 | 왜 큐인가 |
|---|
| 주문과 결제 처리 | 먼저 온 요청을 먼저 처리해야 공정하다 |
| 알림과 메일 발송 | 순서대로 보내되 실패는 뒤로 미룬다 |
| 작업 대기열 (이미지 변환, 리포트) | 처리량을 넘는 요청을 쌓아두고 소화한다 |
| 메시지 브로커 | 생산자와 소비자의 속도를 분리한다 |
| 너비 우선 탐색 | 발견한 순서대로 방문해야 최단 거리가 나온다 |
| 프린터와 스케줄러 | 도착 순서를 지킨다 |
큐의 실무 가치는 순서만이 아닙니다. 처리 속도가 다른 두 쪽을 떼어 놓는 완충 역할이 더 큽니다. 초당 1,000건이 들어오고 200건만 처리할 수 있어도, 큐가 있으면 요청을 잃지 않고 밀린 만큼 지연으로 흡수합니다.
흔한 실수: 큐를 두면 지연이 사라진다고 답하는 것. 지연은 남고 유실이 줄어듭니다. 유입이 계속 처리량을 넘으면 큐는 무한히 자랍니다.
Q.우선순위 큐는 어떻게 구현하나요? 시간 복잡도는?
힙으로 구현합니다. 완전 이진 트리를 배열에 담아 부모가 자식보다 작다는 규칙만 유지합니다.
| 연산 | 복잡도 | 방법 |
|---|
| 최솟값 확인 | O(1) | 뿌리를 본다 |
| 삽입 | O(log n) | 맨 끝에 넣고 부모와 비교하며 올린다 |
| 최솟값 제거 | O(log n) | 뿌리에 마지막 원소를 놓고 자식과 비교하며 내린다 |
| 임의 값 탐색 | O(n) | 형제 사이 순서를 모른다 |
다른 선택과 비교하면 힙이 왜 표준인지 보입니다.
| 구현 | 삽입 | 최솟값 제거 |
|---|
| 정렬된 배열 | O(n) | O(1) |
| 정렬 안 된 배열 | O(1) | O(n) |
| 힙 | O(log n) | O(log n) |
둘 다 자주 쓰이므로 한쪽이 O(n)인 구현은 불리합니다.
흔한 실수: 우선순위 큐를 정렬된 리스트로 설명하는 것. 삽입이 O(n)이라 갱신이 잦은 스케줄러에는 맞지 않습니다.
Q.원형 큐가 일반 큐보다 유리한 경우는?
배열로 큐를 만들 때 앞쪽에 생긴 빈 공간을 재사용할 수 있습니다.
크기 5 배열에서 3개를 넣고 2개를 뺐다고 해봅시다.
| 방식 | 앞의 빈 두 칸 | 끝에 닿으면 |
|---|
| 일반 배열 큐 | 쓰지 못한다 | 더 넣을 수 없다 |
| 원형 큐 | 재사용한다 | 앞으로 돌아간다. (뒤 + 1) 나머지 크기로 위치를 계산한다 |
앞의 빈 칸을 메우려고 매번 앞으로 당기면 O(n)이 듭니다. 원형으로 쓰면 넣고 빼는 것이 모두 O(1)입니다.
그래서 크기가 정해진 버퍼에 유용합니다. 네트워크 수신 버퍼, 오디오 버퍼, 최근 로그 N건 보관이 대표적입니다.
흔한 실수: 꽉 찬 상태와 빈 상태를 구분하지 않는 것. 앞과 뒤가 같은 위치를 가리키는 상황이 둘 다에서 생기므로, 개수를 따로 세거나 한 칸을 비워두는 규칙이 필요합니다.
Q.BFS에서 큐를 쓰는 이유는?
가까운 곳을 먼저 다 보고 다음 겹으로 넘어가야 하므로, 발견한 순서대로 꺼내야 합니다.
시작점을 넣는다
꺼낸 노드의 이웃을 모두 넣는다
큐가 빌 때까지 반복한다
겹 0: 시작점
겹 1: 시작점의 이웃들
겹 2: 그 이웃들의 이웃들
먼저 넣은 것을 먼저 꺼내므로 겹 1 이 전부 나온 뒤에 겹 2 가 나옵니다. 이 성질 덕분에 간선 비용이 모두 같은 그래프에서 처음 도달한 시점이 최단 거리가 됩니다.
스택으로 바꾸면 방금 발견한 이웃부터 파고들어 깊이 우선 탐색이 됩니다. 최단 거리 보장이 사라집니다.
흔한 실수: 방문 표시를 꺼낼 때 하는 것. 넣을 때 표시해야 같은 노드가 큐에 여러 번 들어가지 않습니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.