[자료구조] Stack & Queue

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

Stack

• Insert/Delete만 제공
• Push/Pop이라고 부름
• Last in, First Out
• 성능 : Push O(1), Pop O(1)
• Stack Pointer(SP) : 스택의 최상위 부분. 주로 다음 저장될 위치, 즉 빈 공간을 지칭한다.

Stack의 구현

int Stack[N];
int SP;

int init() {
    SP = 0;
}

int isEmpty() {
    return SP == 0;
}

int Push(int x) {
    Stack[SP] = x;
    SP++;
}

int Pop() {
    SP--;
    return Stack[SP];
}

• SP의 범위에 관련된 코드는 적혀있지 않다. (이를 방지하지 않으면 오류가 날 수 있지만, 현 상황에선 제외했다.)

Queue

• Insert/Delete만 제공
• First in, First Out
• 성능 : Insert O(1), Pop O(1)
• Head & Tail : Queue의 제일 앞 부분을 Head, 제일 뒷 부분을 Tail이라한다.
• Head와 Tail을 이용하기 때문에 자료의 끝부분에 공간이 없어도 앞부분에 공간이 있다면 해당 공간을 활용하고 Head와 Tail만 잘 표시해주면 된다. 만약 Head와 Tail이 겹치면 비어있거나, 꽉 찬 것이다.

Queue의 구현

int Queue[N];
int Head, Tail;

int init() {
    Head = 0;
    Tail = 0;
}

int isEmpty() {
    return Head == Tail;
}

int insert() {
    Queue[Tail] = x;
    Tail++;
    Tail = Tail % N; // Tail이 돌아오는 경우
}

int delete() {
    int oldHead = Head;
    Head++;
    Head = Head % N;
    return Queue[oldHead]; 
}

• 최대한 간단한 핵심기능만 구현한 것이다.

미로찾기 : Stack, Queue 응용

• 0은 열린 좌표, 1은 닫힌 좌표를 뜻한다.
• 좌표를 저장할 수 있어야 한다.
• 경로를 저장해놓고 해당 경로를 활용해 다시 돌아갈 수 있어야 한다.

DFS 명시적 stack

int Map[M][N]; // 미로
int i,j; // 현재 위치

int Find() {
    i = j = 0;
    while () {
        if (i == M - 1 && j == N - 1) // 목적지 도착

        // (i, j+1) , (i, j-1), (i+1, j), (i-1, j) 중 0이 있는가?
        // 0이 있으면 전진 (아래 코드는 예제)
        Push(i); 
        Push(j); // 스택에 i,j 두 값 push
        Map[i][j] = '*';
        j++;

        // 0이 없으면 후진, 후진 시 stack empty면 실패로 처리.
        j = Pop();
        i = Pop();
    }
}

• 1. (0,0)에서 특정 위치 (s,t)로 가는 길이 있다 = (0,0) , (a1,b1), (a2,b2), ..., (s,t)인 좌표가 있다.
• 2. 인접한 쌍에서는 좌표값 둘 중 한 숫자만 1 차이가 난다.
• 3. Map의 전진 가능한 모든 좌표에 초기에 0(갈수있음)이 적혀 있다.
• 위와 같은 상황에서 알고리즘은 (s,t)를 반드시 방문한다.
• 길이 있는데 즉, 0이 존재하는데 그를 두고 가지 않는 것은 모순 => 반드시 성립됨이 증명
• 한 칸에서 사용하는 시간은 상수시간이다. (스택에 넣고, 전진 혹은 후진 작업 수행)
• 따라서 한 칸에서 일어나는 일을 모든 칸에 적용하면 시간복잡도는 O(MN), 미로의 크기만큼이 된다.

BFS 명시적 Queue

int Map[M][N];
int i, j;

int Find() {
    queueInsert(0, 0);
    while() {
        (i, j) = QueueDelete(); // Queue가 Empty이면 실패

        // Map[i][j] == 0 인 경우만
        Map[i][j] = '*'; // 목적지 확인

         // (i, j+1) , (i, j-1), (i+1, j), (i-1, j) 중 0인 좌표를 Queue에 Insert

    }    
}

• 가능한 곳을 Queue에 넣었다가 꺼냈을 때 0이면 진행하는 방식

Equivalence Relation

• 말 그대로 '동등한 관계'라는 의미로서, 당연하게 양방향이다.
• Relation : A라는 집합이 주어졌을 때, A상에서의 Relation은 AxA의 부분집합들. (갯수는 2^(N^2)개)
• Ex) A = {1,2,3,4} , Relation = { (1,3) , (3,4) , (1,1) , (2,2) }
• Equivalence Relation : Relation 중에 특수한 조건을 만족시킨 경우들 이다. 특수한 조건은 아래 세가지이다. 세가지를 모두 만족해야 한다.
• Reflexive : aRa가 성립 (모든 가능한 a에 대하여)
• Symmetric : aRb가 성립하면 bRa가 성립 (모든 가능한 a,b에 대하여)
• Transitive : aRb와 bRc가 성립하면 aRc가 성립 (모든 가능한 a,b,c에 대하여)
• 직관적으로는 키가 같다, 머리색이 같다.
• Induced Partition : Relation이 있으면 Partion은 저절로 도출된다.
• One Assumption : 입력은 최소한(Minimal)만 한다. 줄일 수 있는 한 최대한 줄인다. (유추 가능한 쌍은 주지 않음. 예를 들면 1-9가 주어지면 9-1은 필요없다. 1-1과 같은 자기자신과의 정보도 주어질 필요없다.)
• 이러한 관계를 노드와 엣지 형태로 나타내면 노드가 n개면 엣지는 최대 n - 1개 이다.

---

• 이러한 Equivalence Relation를 활용하여 미로의 연결관계를 나타낼 수 있다.
• 위 그림은 각 노드의 연결관계를 나타낸 것이고 전체적 미로의 좌표와는 다르다. (위에서 보인 그림과 의미가 다르다.) 1이면 두 노드가 연결되어 있는 것이고 0이면 연결되어 있지 않은 것이다.
• 특정 노드를 '출구'라고 가정한다면 어떤 노드에서 '입구'로 설정해야 해당 노드에 도달할 수 있는지 알 수 있을 것이다.
• Marker에서의 시간복잡도 : O(N^2) , 단 방문했던 노드 기억기능 추가시 O(N)
• Stack에서의 시간복잡도 : O(N), 전체 노드가 스택에 들어갔다 나오는 횟수는 N-1번(엣지갯수)
• Matrix에서의 시간복잡도 : O(N^2), 한 col에서 1을 전부 가지고 있다면 최대 O(N^2)의 시간 복잡도를 가질 수 있지만 한 col이 그 만큼 1을 많이 가지고 있어 다른 col에서는 시간이 소요되지 않는다. 즉, 어떤 형태를 가지더라도 결국은 전체 1의 갯수 *N 의 시간복잡도를 가진다. 따라서 전체 시간복잡도는 O(N^2)이다.

• 연결관계를 위와 같이 나타낼 수도 있다.
• 이처럼 나타낼 경우 Matrix에서의 시간복잡도가 줄어들 수도 있다. 한 row에서 지난번 탐색한 위치를 기억한다면 O(N)만으로 모든 위치 정보를 확인할 수도 있다.
• Marker나 Stack에서의 시간복잡도는 동일하다.