![[자료구조] 큐 (Queue) - 피보나치 수열 계산, BFS](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FEBG3O%2FbtqSa9Rzma4%2FJBkfkDjbH8N5rAa9AK55y0%2Fimg.png)
1. 큐 (Queue)
1.1 큐?
큐(Queue)란 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
놀이동산의 놀이기구를 타기 위해 줄을 서있는 모습을 생각하면 이해하기 편할 것이다.
1.2 큐 ADT
객체
- FIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음
연산
- enqueue(x) : 요소 x를 큐의 맨 뒤에 추가
- dequeue() : 큐의 맨 앞의 요소를 삭제하고 반환
- peek() : 큐의 맨 앞의 요소를 삭제하지 않고 반환
- isEmpty() : 큐가 비어있으면 true 아니면 false 반환
- isFull() : 큐가 가득 차 있으면 true 아니면 false 반환
- size() : 큐 내의 모든 요소 개수를 반환
- display() : 큐 내의 모든 요소 출력
1.3 큐의 구조 및 연산
큐 또한 스택과 동일하게 순서대로 연결된 선형구조 형태의 자료구조이며, 배열(Array)과 연결 리스트(Linked List)를 이용하여 구현할 수 있다.
스택에서는 top을 이용하여 마지막 요소의 위치를 알 수 있었다.
하지만 큐에서는 삽입과 삭제가 양쪽에서 이뤄지므로, 삽입 연산이 이루어지는 곳을 rear 삭제 연산이 이루어지는 곳을 front라고 정의한다.
이번에도 이해를 위해 배열로 큐를 구현해보자.
큐에서 front 변수는 첫 번째 요소를 가리키며, rear 변수는 큐의 마지막 요소를 가르킨다.
큐를 최초로 생성하여 아무런 데이터가 없는 상태에서의 front와 rear는 둘 다 -1이다.
Enqueue는 큐에 데이터를 추가하는 연산이다.
큐에 데이터가 삽입되면 rear가 증가하며 해당 위치에 데이터가 삽입된다.
Enqueue의 시간복잡도는 O(1)이다.
Dequeue은 큐에서 가장 앞에 있는 데이터를 삭제하는 연산이다.
큐의 첫 번째 요소를 가리키는 front를 증가시키는 방법으로 삭제 연산을 구현할 수 있다.
물론 삭제하면서 해당 값을 반환하므로, 이를 사용할 수 있다.
Dequeue의 시간복잡도 또한 O(1)이다.
1.4 Array로 Linear Queue 구현 (C++)
간단하게 int 형을 담을 수 있는 queue를 배열을 이용하여 구현해보았다.
배열의 index 내에서 front와 rear의 이동을 표현하기 위해 최초 생성 시 0으로 초기화하였다.
/*
* array를 이용하여 Linear Queue 구현
*/
#include <iostream>
using namespace std;
#define MAX_QUEUE_SIZE 20
class Queue {
private:
int front; // 첫번째 요소 앞의 index
int rear; // 마지막 요소 index
int data[MAX_QUEUE_SIZE];
public:
Queue(){
front = 0;
rear = 0;
}
~Queue(){}
void enqueue(int n){
if(isFull()){
cout << "Queue Full Error" << endl;
exit(1);
}
data[++rear] = n;
}
int dequeue(){
if(isEmpty()){
cout << "Queue Empty Error" << endl;
exit(1);
}
return data[++front];
}
int size(){
return rear - front;
}
void display(){
for(int i=front+1; i<=rear; i++){
cout << "[" << data[i] << "]";
}
cout << endl;
}
bool isEmpty(){
return front == rear;
}
bool isFull() {
return rear == MAX_QUEUE_SIZE - 1;
}
};
int main() {
Queue queue;
for(int i=0; i<10; i++){
queue.enqueue(i);
}
cout << "size : " << queue.size() << endl;
queue.display();
queue.dequeue();
queue.dequeue();
queue.dequeue();
cout << "size : " << queue.size() << endl;
queue.display();
}
1차원 array를 이용하여 Linear 형태의 Queue를 구현해보았다.
Queue로 활용할 array의 최대 크기를 정해놓고 push와 pop이 이루어질 때마다 front와 rear값만 1씩 올려주면 되지만, 여기에는 문제가 있다.
- push 횟수가 array의 최대 크기를 넘어가는 경우 더 이상 요소를 추가할 수 없다.
- 또한 pop을 수행하면 front만 증가시키므로 front 이전의 index를 가지는 array 메모리 공간이 낭비된다.
우리는 이를 해결하기 위해 선형 구조로 array Queue를 구현할 수 있다.
1.5 Circular Queue란?
단순하게 원형 형태의 배열이라고 생각하면 쉽다.
front 또는 rear 값이 배열의 끝에 도달하면 다음에 증가 시 다시 0으로 순환되는 구조이다.
1.6 Array로 Circular Queue 구현 (C++)
array size를 10으로 설정 후 enqueue와 dequeue를 반복적으로 수행하여 front와 rear의 이동을 눈여겨보자.
/*
* array를 이용하여 Circular Queue 구현
*/
#include <iostream>
using namespace std;
#define MAX_QUEUE_SIZE 10
class Queue {
private:
int front; // 첫번째 요소 앞의 index
int rear; // 마지막 요소 index
int data[MAX_QUEUE_SIZE];
public:
Queue(){
front = 0;
rear = 0;
}
~Queue(){}
void enqueue(int n){
if(isFull()){
cout << "Queue Full Error" << endl;
exit(1);
}
rear = (rear+1)%MAX_QUEUE_SIZE; // rear가 max를 넘어가는 경우 다시 0번째 index로 순회
data[rear] = n;
}
int dequeue(){
if(isEmpty()){
cout << "Queue Empty Error" << endl;
exit(1);
}
front = (front+1)%MAX_QUEUE_SIZE; // front가 max를 넘어가는 경우 다시 0번째 index로 순회
return data[front];
}
int peek(){
if(isEmpty()){
cout << "Queue Empty Error" << endl;
exit(1);
}
return data[(front+1)%MAX_QUEUE_SIZE];
}
int size(){
return front<=rear ? rear-front : (rear+MAX_QUEUE_SIZE)-front;
}
void display(){
for(int i=front+1; i<=front+size(); i++){
cout << "[" << data[i%MAX_QUEUE_SIZE] << "]";
}
cout << endl;
}
// circular array의 front와 rear 정보를 보기위한 메소드
void displayDetail(){
cout << "QUEUE :";
for(int i=front+1; i<=front+size(); i++){
cout << "[" << data[i%MAX_QUEUE_SIZE] << "]";
}
cout << endl;
cout << "index :";
for(int i=front+1; i<=front+size(); i++){
cout << " " << i%MAX_QUEUE_SIZE << " ";
}
cout << endl;
cout << "front : " << front << ", rear : " << rear << endl;
cout << endl;
}
bool isEmpty(){
return front == rear;
}
bool isFull() {
return front == (rear+1)%MAX_QUEUE_SIZE;
}
};
int main() {
Queue queue;
cout << "===== enqueue x9 =====" << endl;
for(int i=0; i<9; i++){
queue.enqueue(i);
}
cout << " size : " << queue.size() << endl;
queue.displayDetail();
cout << "===== dequeue x3 ======" << endl;
queue.dequeue();
queue.dequeue();
queue.dequeue();
cout << " size : " << queue.size() << endl;
queue.displayDetail();
cout << "===== enqueue x2 ======" << endl;
queue.enqueue(9);
queue.enqueue(10);
cout << " size : " << queue.size() << endl;
queue.displayDetail();
}
Circular Queue를 사용하여 enqueue횟수가 array의 최대 크기를 넘어가는 경우 0번째 index로 순환하는 모습을 확인할 수 있다.
2. 큐 사용해보기
2.1 피보나치 수열 계산
-
피보나치 수열
수학에서 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
편의상 0번째 항을 0으로 두기도 한다.
-
피보나치 수열 계산 알고리즘
-
먼저 0, 1을 Queue에
enqueue한다. -
다음 수 계산을 위해 Queue의 첫 번째 수를
dequeue한 후 첫 번째 수와 두 번째 수를 합하여 다시 Queue에enqueue한다. -
n번째 피보나치 수를 계산하기 위해 2번을 n-1번 반복한다.
(첫 번째 수는 최초에 Queue에 초기값으로 넣어놨기 때문)
-
- C++ 구현
/*
* Queue를 이용하여 피보나치 수열 계산
*/
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> queue;
int cnt = 7;
queue.push(0);
queue.push(1);
cout << queue.front() << " " << queue.back() << " ";
for(int i=0; i<cnt-1; i++){
int num1 = queue.front();
queue.pop();
int num2 = queue.front();
queue.push(num1+num2);
cout << queue.back() << " ";
}
cout << '\n' << "fibo(" << cnt << ") : " << queue.back() << endl;
}
2.2 미로 탐색 알고리즘 (BFS)
-
너비 우선 탐색(BFS) 알고리즘
- 시작 노드로부터 가까운 노드를 먼저 탐색하고 멀리 떨어져 있는 노드를 나중에 탐색하는 방법
- 출발 노드에서 목표 노드까지 최단 길이 경로를 보장하므로, 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 주로 사용
- 시간복잡도 O(N)
-
BFS 과정
- 시작 노드를 큐에
enqueue한다. - 큐의 첫 번째 노드를
dequeue하고 해당 노드는 방문했다고 표시한다.
해당 노드로부터 인접한 노드 중 방문하지 않은 노드가 있다면 큐에enqueue한다. - 만약 인접한 노드 중 방문하지 않은 노드가 없다면 2번을 반복한다.
- 스택이
empty될 때까지 반복한다.
- 시작 노드를 큐에
-
미로탐색 알고리즘
- BFS 알고리즘 이용
- 노드를 탐색하는 과정에서 해당 노드가 출구(x)인 경우 SUCCESS!!
- C++ 구현
#include <iostream>
#include <queue>
using namespace std;
struct Location2D{
int row; // 현재 위치의 행
int col; // 현재 위치의 열
Location2D(int r, int c){
row = r;
col = c;
}
};
const int MAX_SIZE = 6;
char map[MAX_SIZE][MAX_SIZE] ={
{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'}
};
// (row, col) 위치에 갈 수 있는지 검사
bool isValidLoc(int row, int col){
if(row<0 || col<0 || row>MAX_SIZE || col>MAX_SIZE){
return false;
}else{
return map[row][col] == '0' || map[row][col] == 'x' ? true : false;
}
}
// 시각적으로 Map 보여주기
void printMap(int row, int col){
cout << '\n' << "======= [" << row << ", " << col << "] =======" << endl;
for(int i=0; i<MAX_SIZE; i++){
for(int j=0; j<MAX_SIZE; j++){
if(i==row && j==col){ // 현재 위치
cout << " ❌️ ";
}else{
if(map[i][j] == '1') cout << " ⬛️ ";
if(map[i][j] == 'x') cout << " 🚩️ ";
if(map[i][j] == '0') cout << " ◻️ ";
if(map[i][j] == '.') cout << " 👣️ ";
}
}
cout << endl;
}
}
int main() {
queue<Location2D> locQueue;
locQueue.push(Location2D(1,0)); // start 좌표
while(!locQueue.empty()){
// 현재 위치를 구하고 stack에서 삭제
Location2D here = locQueue.front();
locQueue.pop();
int row = here.row;
int col = here.col;
printMap(row, col);
if(map[row][col] == 'x'){
cout << "SUCCESS!!" << endl;
return 0;
}else{
map[row][col] = '.';
if(isValidLoc(row, col-1)) // 좌
locQueue.push(Location2D(row, col-1));
if(isValidLoc(row, col+1)) // 우
locQueue.push(Location2D(row, col+1));
if(isValidLoc(row-1, col)) // 상
locQueue.push(Location2D(row-1, col));
if(isValidLoc(row+1, col)) // 하
locQueue.push(Location2D(row+1, col));
}
}
cout << "FAILED!!" << endl;
return 0;
}
