[실전 알고리즘] 0x06강 - 큐

 

안녕하세요, 바킹독입니다. 이번 시간에는 큐를 배워보겠습니다.

 

저번 단원에서 배운 스택이랑 이번에 배울 큐랑은 좀 비슷한게 많습니다. 그래서 전 단원을 잘 이해하고 왔다면 이번 단원도 수월할 것입니다.

 

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 됩니다. 공항에서 입국수속을 하는 줄과 같은 상황이라고 볼 수도 있습니다.

 

스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 합니다.

 

큐에서 연산의 시간복잡도를 보면 스택처럼 원소의 추가와 제거가 모두 O(1)입니다. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 합니다. 아무튼 가장 앞쪽에 위치해있거나 가장 뒤쪽에 위치한 원소의 확인도 O(1)입니다.

 

4번 성질에 대한 얘기는 이미 스택 단원에서 충분히 언급을 했기 때문에 여기서는 설명을 깊게 하지는 않을 것입니다. 요약해서 다시 말을 해보면 스택과 비슷한 맥락으로 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만, 배열을 가지고 직접 만들 땐 해당 기능이 가능하도록 구현을 할 수 있다 정도로 요약이 가능합니다. 단, STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없습니다.

 

큐도 스택처럼 배열 혹은 연결 리스트 둘 중 어느 것을 이용해도 구현을 하는데 문제가 없지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열로 어떻게 구현하면 될지만 짚고 넘어가겠습니다. 큐를 구현할 때는 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개가 필요합니다. 이 head와 tail을 어떻게 두는지는 예시를 보고 이해해보겠습니다.

 

{21, 30}이 들어있는 큐를 나타내보면 오른쪽과 같습니다. head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 + 1입니다. 꼭 이렇게 안두고 tail을 가장 뒤에 있는 원소의 인덱스로 두어도 괜찮지만 저는 지금 보시는 것 처럼 두겠습니다.

지금 왜 0번지는 비어있고 1, 2번지에 차있는지 잘 이해가 가지 않을 수 있습니다. 그래서 큐를 배열로 표현하는 방법이 이해가도록 예시를 한 번 보여드리겠습니다.

 

일단 시작할 땐 head와 tail이 모두 0번지를 가리키고 있습니다. 이 상황에서 55를 추가하면 큐는 두 번째 그림과 같이 head는 변함이 없고 tail은 한 칸 올라가게 됩니다.

 

그 다음에는 17을 추가하겠습니다. 17을 추가할 때에도 마찬가지로 head는 그대로고 tail은 1 증가합니다.

 

다음으로는 제일 앞의 원소를 없애보겠습니다.이번에는 head가 1칸 올라갔습니다. 0번지에 있는 55는 굳이 다른 값으로 덮을 필요는 없습니다.

 

이런 식으로 head와 tail은 0번지에서 시작해 계속 증가하게 됩니다. 쭉 보셔서 알겠지만 dat 배열에서 dat[head]부터 dat[tail-1]번지가 바로 큐의 원소들이 들어있는 자리입니다. 그리고 큐의 크기는 tail - head로 쉽게 계산할 수 있습니다.

 

앞의 과정을 보면 push를 할 땐 tail이 증가하고, pop을 할 땐 head가 증가합니다. 그렇기 때문에 dat 배열에서 큐의 원소들이 들어있는 장소는 점점 오른쪽으로 밀립니다.

 

head가 5를 가리키고 있고 tail이 8을 가리키고 있어 dat의 5번지, 6번지, 7번지를 사용하고 있는 상황을 보면 앞쪽에 사용하지 않고 있는 공간이 많음에도 불구하고 더 이상 삽입을 할 수가 없습니다. 삽입을 하려면 dat[8]에 값을 써야 하는데 배열이 8칸이니 그럴 수가 없기 때문입니다.

 

이와 같이 스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생기게 됩니다. 이 문제를 해결하는 방법은 의외로 간단한데 큐의 원소가 들어갈 배열을 원형으로 만드는 것입니다. 관념적으로는 배열이 원형인거고, 실제 구현을 할 땐 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만들면 됩니다.

 

즉, dat의 5, 6, 7번지를 사용하는 상황에서 원소 1개가 추가되면 0번지를 점유하는 것입니다. 이렇게 원형의 배열을 가정하고 구현한 큐를 원형 큐(Circular Queue)라고 부릅니다.

 

그냥 선형 배열에서 만든 큐는 삭제가 될 때 마다 쓸모없는 공간이 계속 생겨서 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 생길 수 있는데, 원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제가 없습니다. 그래서 실무에서 굳이 STL 말고 큐를 직접 구현해서 쓰겠다고 하면 원형 큐로 만드는게 좋습니다.

 

하지만 우리가 연결 리스트에서 생각한 것과 비슷하게, 코딩테스트에서는 어차피 push의 최대 횟수가 정해져 있습니다. 그러면 배열의 크기를 push의 최대 횟수보다 크게 둬서 굳이 원형 큐를 만들지 않아도 되게끔 할 수 있습니다.

 

사실 원형 큐의 구현이라고 해봐야 head, tail이 MX가 될 경우 0으로 만드는 것만 달라지기 때문에 어려운 것은 아닌데, 그래도 강의에서는 일단 원형 큐가 아니라 선형 배열에서의 큐를 다루겠습니다. push, pop은 각각 삽입과 삭제를 하는 함수이고 front, back은 각각 제일 앞쪽의 원소 확인과 제일 뒷쪽의 원소를 반환하는 함수입니다. (템플릿 링크)

 

이제 각 함수들을 구현하겠습니다. 스택을 잘 해내셨다면 큐도 크게 어렵지 않을 것입니다.

 

일단 push 함수부터 해보겠습니다. 지금 52와 15가 있는 큐에 22를 넣고 싶다고 하면 tail이 가리키는 자리에 22를 추가하고 pos를 1 증가시키면 됩니다. 스택에서도 그랬지만 이건 코드 한 줄로 표현할 수 있습니다.

 

pop은 더 날먹인데 그냥 head를 1 증가시키면 됩니다. 코드도 아주 간단합니다.

 

front 함수는 큐에서 제일 앞에 위치한 원소를 반환하는 함수이고 back 함수는 큐에서 제일 뒤에 위치한 원소를 반환하는 함수이니까 지금 저 큐를 보면 front 함수는 52를 반환하고 tail 함수는 22를 반환해야 합니다.

 

옆에 head랑 tail이 인덱스를 잘 가리키고 있으니까 큰 어려움 없이 해결할 수 있을 것 같습니다. 각각 dat[head]랑 dat[tail-1]을 반환하면 됩니다. 코드도 같이 확인해보세요.

전체 코드는 깃헙에 올려뒀으니 직접 짠거랑 비교를 해보셔도 좋습니다.

 

물론 STL에 큐도 있습니다.(레퍼런스 링크, 예제 링크) 보통 큐는 BFS랑 Flood Fill를 할 때 쓰게 되는데 둘 다 코딩테스트 단골 문제여서 문제를 풀 때 STL queue를 쓸 일이 아주 많을 것입니다. 그래서 나중 가면 적어도 STL queue 만큼은 외우기 싫어도 외워질 것입니다.

 

그리고 큐가 비어있는데 front나 back이나 pop을 호출하면 런타임에러가 발생할 수 있다는 점은 주의를 하셔야 합니다.

 

이제 큐의 구현을 연습해볼 수 있는 연습문제를 풀어보겠습니다.(BOJ 10845번: 큐) 먼저 STL을 써서 풀어본 코드입니다. pop, front, back 명령에 대해서는 STL의 해당 멤버 함수를 실행하기 전에 먼저 큐가 비었는지를 확인해줄 필요가 있습니다.

 

그 다음으로는 직접 구현한 큐를 이용한 코드입니다.(클릭) 이것도 예외처리만 좀 신경써주고 크기를 tail-head로 계산할 수 있다는 점만 좀 신경쓰면 크게 어려울 건 없을 것입니다.

 

이번 단원에서는 큐를 배웠습니다. 크게 어렵지는 않았을 것 같은데 맞죠? 다음 시간에 배울 덱(Deque)까지는 좀 힐링이 되는 쉬운 난이도였다가 DFS, BFS를 들어가면 이제 헬게이트가 열립니다. 그래서 마음의 준비 단단히 해두시고, 연습문제들 풀어보시고 이번 강의는 여기서 마치겠습니다. 배경에 바다가 되게 예쁜데 보니까 놀러가고 싶습니다. 나중에 취업 성공하시고 저런데 놀러가세요. 그럼 안녕~~