[자료구조] 큐 (Queue) - 피보나치 수열 계산, BFS
IT/Data Structure

[자료구조] 큐 (Queue) - 피보나치 수열 계산, BFS

728x90
반응형

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 변수는 큐의 마지막 요소를 가르킨다.

큐를 최초로 생성하여 아무런 데이터가 없는 상태에서의 frontrear는 둘 다 -1이다.

 

Enqueue는 큐에 데이터를 추가하는 연산이다.

큐에 데이터가 삽입되면 rear가 증가하며 해당 위치에 데이터가 삽입된다.

Enqueue의 시간복잡도는 O(1)이다.

 

Dequeue은 큐에서 가장 앞에 있는 데이터를 삭제하는 연산이다.

큐의 첫 번째 요소를 가리키는 front를 증가시키는 방법으로 삭제 연산을 구현할 수 있다.

물론 삭제하면서 해당 값을 반환하므로, 이를 사용할 수 있다.

Dequeue의 시간복잡도 또한 O(1)이다.

 

1.4 Array로 Linear Queue 구현 (C++)

간단하게 int 형을 담을 수 있는 queue를 배열을 이용하여 구현해보았다.

배열의 index 내에서 frontrear의 이동을 표현하기 위해 최초 생성 시 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으로 두기도 한다.

  • 피보나치 수열 계산 알고리즘

    1. 먼저 0, 1을 Queue에 enqueue 한다.

    2. 다음 수 계산을 위해 Queue의 첫 번째 수를 dequeue한 후 첫 번째 수와 두 번째 수를 합하여 다시 Queue에 enqueue한다.

    3. 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 과정

    1. 시작 노드를 큐에 enqueue한다.
    2. 큐의 첫 번째 노드를 dequeue하고 해당 노드는 방문했다고 표시한다.
      해당 노드로부터 인접한 노드 중 방문하지 않은 노드가 있다면 큐에 enqueue한다.
    3. 만약 인접한 노드 중 방문하지 않은 노드가 없다면 2번을 반복한다.
    4. 스택이 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;
}

 

 

 

728x90
반응형