[ Algorithm ] 스택

도입

이 글은 자료구조에서 가장 초반에 배우는 스택에 대한 개념을 담고 있습니다. 자료구조에 해당한다고 해서 겁먹을 필요 없이, 순서에 따라 차근차근 원리를 이해하면 쉬운 난이도를 가지고 있으니 걱정하지 않아도 됩니다. 스택의 개념을 이해하고 여러 문제에 활용하며 풀이한 뒤, 추후 적극적으로 응용이 가능하도록 능력을 기르는 것이 이 글의 목적입니다. 

본 글은 C를 기반으로 작성되었습니다.

 

접근

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

스택 자료 구조를 사용할 수 있는 문제들이 실버 문제 부근에서 모습을 드러내기 시작한다. 스택은 주로 어떤 상황에 사용할까?

 

데이터 쌓기

스택 (stack) 은 쌓다, 쌓이다, 무더기 등의 뜻을 가지고 있다. 주로 데이터를 쌓는 데에 사용되는 자료 구조가 스택이다.

다음과 같은 문제를 예시로 들어보자.

학생들의 시험 점수 정보 중 가장 높은 점수와 가장 낮은 점수를 찾기 위해서는 순차적으로 비교하면서 최고 점수와 최저 점수를 찾아야 한다.

// students[i][0] : i번째 학생의 나이 정보
// students[i][1] : i번째 학생의 시험 점수 정보
int maxScore = -1;
int minScore = 101;
for (int i = 0; i < n; i++) {
    if (maxScore < students[i][1]) maxScore = students[i][1];
    if (minScore > students[i][1]) minScore = students[i][1];
}

최고 점수와 최저 점수를 찾았다면, 그 점수에 해당하는 학생들의 나이 정보를 출력하면 된다.

// 최고 점수를 받은 학생
for (int i = 0; i < n; i++) {
    if (students[i][1] == maxScore)
        printf("%d ", students[i][0]);
}

printf("\n");

// 최저 점수를 받은 학생
for (int i = 0; i < n; i++) {
    if (students[i][1] == minScore)
        printf("%d ", students[i][0]);
}

printf("\n");

이렇게 구현을 완료할 수 있으나, 여기서 스택 자료구조를 사용하면 모든 학생들을 검사하면서 최고점을 받은 학생인지 최저점을 받은 학생인지 체크할 횟수를 줄일 수 있다. 바로 최고점이나 최저점을 받은 학생들의 번호를 스택에 쌓아두는 것이다!

미리 최고점을 받은 학생이 몇 번이고, 최저점을 받은 학생이 몇 번인지 알 수 있다면 나중에 모든 학생들을 따로 찾아볼 필요 없이 바로 나이 정보에 액세스 하는 것이 가능하다!

스택 ( Stack )

스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 자료 구조이다. 제일 마지막에 넣는 것이 먼저 나온다는 LIFO ( Last In First Out ) 특성을 가지고 있다. 데이터를 입력된 순서대로 저장하고, 이를 역순으로 뽑아내며 접근하는 구조가 필요할 때 사용한다.

스택에 데이터가 쌓이는 구조이다. 마치 셔틀콕 통과 비슷한 구조로 제일 먼저 넣은 데이터가 깊숙히 들어가고, 이후로 넣은 데이터가 밑에서부터 차곡차곡 쌓이는 구조이다. 데이터를 뺄 때는 제일 마지막에 넣은 데이터부터 뺀다.

 

Top 이라는 변수를 이용해 스택을 관리할 수 있다. Top은 스택에서 가장 높은 곳에 쌓인 (가장 마지막에 넣은) 데이터의 위치를 알려준다. 이를 이용해 스택이 비었는지 (비어있을 땐 Top 이 -1), 스택에 얼마나 많은 데이터가 쌓였는지 (Top : 2 -> 0번째 ~ 2번째 데이터가 존재 -> 스택에 3개의 데이터가 있음) 등을 알 수 있고, 스택에서 가장 높은 곳에 쌓인 데이터를 뺄 수 있다. 

 

스택 구조 이해

프로그램을 시작하고 스택을 새로 만들면 아무런 데이터도 쌓여있지 않기 때문에 스택은 비어있고 Top은 -1의 값을 가지고 있다. 비어있는 스택에 3이라는 데이터를 넣어보자.

스택에 가장 깊숙히 첫 번째 데이터가 쌓인다. Top의 값은 스택에서 가장 높은 곳의 데이터 위치를 가리키기에 0번째 데이터를 표시한다. ( Top : 0 ) 

데이터가 쌓일 수록 Top의 값은 증가한다.

반대로, 데이터가 빠질 수록 Top의 값은 감소한다. 데이터는 가장 마지막에 쌓인 데이터 먼저 뺀다.

 

스택 - Push

스택에 데이터를 넣는 것을 Push 라고 한다. 단순 데이터를 넣는 행위이기 때문에 O(1)의 시간복잡도를 가진다.

현재 스택의 Top이 1이기 때문에, 1번째 데이터보다 위인 2번째 데이터로 넣고 싶은 데이터를 Push한다.

Push를 코드로 구현하면 다음과 같다.

int stack[SIZE];
int top = -1;

void push(int x) {
    stack[++top] = x;
}

Top이 -1이면 0번째에, Top이 2이면 3번째에 데이터를 넣어야 하기 때문에 Top을 먼저 증가시키고 그 위치에 값을 넣는다.

 

스택 - Pop

스택에 데이터를 꺼내는 것을 Pop 이라고 한다. 마찬가지로 단순 데이터를 꺼내는 행위이기 때문에 O(1)의 시간복잡도를 가진다.

현재 스택의 Top이 2이기 때문에, 끝에 있는 2번째 데이터를 삭제한다. 또한 Pop에서는 꺼낸 데이터를 반환한다!

Pop을 코드로 구현하면 다음과 같다.

int stack[SIZE];
int top = -1;

int pop() {
    return stack[top--];
}

Top이 2이면 2번째 데이터를, Top이 1이면 1번째 데이터를 삭제하고 가장 마지막에 있는 데이터가 삭제되었기 때문에 Top을 감소시킨다.

 

스택 - Empty

하지만, Pop을 다음과 같은 코드 그대로 사용한다면 문제가 발생한다.

스택에 만약 데이터가 없을 경우 Top은 -1이기에, 이때 배열에 접근하는 과정에서 언더플로우를 일으킬 수 있다.

그렇기에, 만약 스택에 데이터가 존재하지 않는다면 데이터 삭제를 하지 않는 조건을 추가해야 한다.

여기서, 참과 거짓 값을 반환하는 Empty를 사용할 수 있다.

Empty는 스택에 데이터가 비어있므면 1 (참), 비어있지 않다면 0 (거짓) 값을 반환한다.

int stack[SIZE];
int top = -1;

int empty() {
    if (top == -1) return 1; 
    else return 0;
}

스택 초기 상태에 top 값이 -1 이었던 점을 생각해보면, 스택에 데이터가 비어있을 땐 제일 높이 쌓인 데이터는 없으므로 -1을 가리킨다. 따라서 다음과 같이 코드를 작성할 수 있다.

 

empty를 이용해 pop 함수를 다음과 같이 수정하면 언더플로우 걱정 없이 pop을 수행할 수 있다.

int pop() {
    if (!empty()) return stack[top--];
    else {
        printf("Stack is Empty!");
        return 0;
    }
}

스택이 비어있지 않을 때 데이터를 꺼내야 하기 때문에, empty()의 반환값이 0일때 pop을 수행하도록 코드를 수정한다.

스택 - Full

Empty에서 다루었던 것과 마찬가지로 Push 또한 해당 코드를 그대로 사용했을 때 문제가 발생한다.

스택이 가득 찼을 때를 생각해보면 배열에 접근하는 과정에서 오버플로우가 일어날 수 있다.

그렇기에, 스택에 데이터가 가득 차있다면 push를 진행하지 않는 조건을 추가해야 한다.

여기서, 참과 거짓 값을 반환하는 Full을 사용할 수 있다.

Full은 스택에 데이터가 가득 차 있므면 1 (참), 그렇지 않다면 0 (거짓) 값을 반환한다.

 

int stack[SIZE];
int top = -1;

int full() {
    if (top == /** 스택 최대 사이즈 **/) return 1;
    else return 0;
}

full 을 이용해 push 함수를 다음과 같이 수정하면 오버플로우 걱정 없이 push를 수행할 수 있다.

void push(int x) {
    if (!full()) stack[++top] = x;
    else printf("Stack is Full!");
}

스택이 가득 차 있지 않을 때 데이터를 추가해야 하기 때문에, full()의 반환값이 0일때 push를 수행하도록 코드를 수정한다.

정리

한 쪽 끝에서 데이터를 넣는 것을 Push, 한 쪽 끝에서 데이터를 꺼내는 것을 Pop 이라고 한다. 

스택에 데이터가 가득 차면 Full, 스택이 비었다면 Empty 상태이다.

 

앞에서 예시로 들었던 학생들의 나이 정보와 시험 점수 정보를 다루는 문제를 스택으로 풀이해보자.

// students[i][0] : i번째 학생의 나이 정보
// students[i][1] : i번째 학생의 시험 점수 정보
int maxScore = -1;
int maxStack[MAX];
int maxStack_Top = -1;

int minScore = 101;
int minStack[MAX];
int minStack_Top = -1;
for (int i = 0; i < n; i++) {
    if (maxScore < students[i][1]) {
        // 기존 최고점보다 더 높은 최고점 등장. 스택 초기화
        maxStack_Top = -1;
        // 최고점 학생의 번호 저장
        push(maxStack, &maxStack_Top, i); 

        maxScore = students[i][1];
    }
    else if (maxScore == students[i][1]) {
        // 동일하게 최고점을 받은 학생의 번호 저장
        push(maxStack, &maxStack_Top, i);
    }

    if (minScore > students[i][1]) {
        // 기존 최저점보다 더 낮은 최저점 등장. 스택 초기화
        minStack_Top = -1;
        // 최저점 학생의 번호 저장
        push(minStack, &minStack_Top, i);

        minScore = students[i][1];
    }
    else if (minScore == students[i][1]) {
        // 동일하게 최저점을 받은 학생의 번호 저장
        push(minStack, &minStack_Top, i);
    }
}

최고 점수나 최저 점수를 받은 학생들의 번호 정보를 스택에 담는다! 미리 스택에 번호를 담아두면 나중에 학생 번호로 바로 접근하여 나이를 출력하면 되기 때문에 시행 횟수가 줄어든다.

 

기존 최고점 or 최저점보다 더 높은 점수를 받은 학생이 등장했다면, 스택에 있는 정보를 비우고 ( Top을 -1로 초기화 ) 다시 처음부터 학생들의 번호를 저장하면 된다.

 

스택의 Top을 단순히 -1로 초기화한다고 모든 정보가 비워지나? 그것은 아니다. Top을 -1로 바꾸기만 한다면 위치 정보만 -1을 가리킬 뿐이지 배열에는 여전히 값이 남아있다.

하지만 스택의 관리를 Top으로 진행하기 때문에 ( 0 ~ Top 까지 출력, Top에 데이터 추가, Top 에 있는 데이터 삭제... ) Top을 -1로 두면 데이터가 없는 것처럼 스택을 사용할 수 있다!

pop 구현에서 Stack에 있는 데이터를 지우지 않고 top만 감소시켜도 계속 사용할 수 있지 않는가?

 

데이터를 모았다면 출력은 다음과 같이 진행하면 된다.

// 최고 점수를 받은 학생
for (int i = 0; i <= maxStack_Top; i++) {
    // [스택에 저장한 번호 정보] 번째 학생의 나이 출력
    printf("%d ", students[maxStack[i]][0]);
}

printf("\n");

// 최저 점수를 받은 학생
for (int i = 0; i <= minStack_Top; i++) {
    printf("%d ", students[minStack[i]][0]);
}

printf("\n");

 

스택 구현 코드

// C : Stack Implementation
#define SIZE 100

int stack[SIZE];
int top = -1;

int full() {
	if (top == SIZE - 1) return 1;
	else return 0;
}

int empty() {
	if (top == -1) return 1;
	else return 0;
}

void push(int x) {
	if (!full())
		stack[++top] = x;
}

int pop() {
	if (!empty())
		return stack[top--];
}

 

스택 - 연습 문제

1. 스택

https://www.acmicpc.net/problem/10828

10828번: 스택

기본적인 스택을 적용할 수 있는 문제.

https://readytojoin.tistory.com/36

[ BOJ ] 10828 : 스택 ( SILVER 4 ) / C

 

2. 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

스택을 응용하는 가장 기본적인 문제. 괄호끼리 서로 여닫기 위해 여는 괄호를 스택에 담아두고 닫는 괄호를 역순으로 연결할 수 있다.

https://readytojoin.tistory.com/37

[ BOJ ] 9012 : 괄호 ( SILVER 4 ) / C