[실압코] 스택 (stack)

stack<int>

서론

 오늘은 자료구조 스택(stack)에 대해 알아보겠습니다. 스택은 팬케이크를 쌓듯이 한쪽 방향으로 들어가고 나갈 수 있는 배열을 의미합니다. 때문에 나중에 들어간 원소가 먼저 나오게 되어 Last-In First-Out(LIFO) 구조라고 부릅니다. 오늘은 코딩테스트를 볼 때 자주 활용하는 스택의 메서드를 알아보고, 스택을 활용한 문제도 하나 풀어보겠습니다.

스택

#include <stack>

using namespace std;

int main()
{
    stack<int> stk; // int형 변수를 담는 스택을 선언
    stk.empty();    // 스택이 비어있으면 true를 반환
    stk.size();     // 스택에 쌓여있는 원소의 개수를 반환

    stk.pop();      // 스택의 최상단 원소를 제거
    stk.push(10);   // 스택의 최상단에 10을 삽입
    stk.top();      // 스택의 최상단 원소를 반환

    return 0;
}

 

 위에 있는 메서드가 스택을 사용할 때 주로 사용하는 메서드의 전부입니다. 스택의 원리는 매우 간단하기 때문에 복잡한 메서드가 필요 없습니다.

모노토닉 스택

 스택의 활용인 모노토닉(monotonic stack) 스택을 알아보겠습니다. 모노토닉 스택은 내부의 원소들이 오름차순/내림차순으로 정렬되어 있는 스택을 말합니다. 중간에 오름차순/내림차순이 바뀌지 않기 때문에 모노토닉(단조) 스택이라고 불리는 것입니다. 모노토닉 스택만 봤을 땐 그냥 정렬되어 있는 스택이지만 이를 문제에 활용한다면 O(n) 시간에 히스토그램의 가장 큰 직사각형을 찾을 수 있습니다. 그림으로 보겠습니다.

 차트의 숫자는 각 값의 크기를 나타내는 것입니다. 이런식의 정렬되지 않은 숫자들의 배열이 있을 때 모노토닉 스택을 사용하면 특정 원소를 최솟값/최댓값으로 가지는 구간을 쉽게 구할 수 있습니다. 예를 들어 해당 차트에서 가장 넓은 직사각형을 구하는 문제를 생각해 보겠습니다. 특정 구간의 직사각형의 넓이는 (구간의 가로길이 * 구간의 최솟값)으로 구할 수 있습니다. 이때 단순히 모든 경우의 수에 대하여 탐색한다면 구간의 시작, 구간의 끝의 조합이 n * n개이고, 직사각형의 넓이를 구하는데 O(n)이 걸리기 때문에 O(n^3)의 시간이 걸리게 됩니다. 하지만 모노토닉 스택을 활용하면 n개의 조합만 조사하면 되고, 직사각형의 넓이 또한 O(1) 시간에 계산할 수 있기 때문에 총 O(n) 시간에 가장 넓은 직사각형을 구할 수 있습니다.

 최대값 0과 비어있는 스택과 함께 배열의 처음부터 끝까지 순회합니다. 이때 스택은 오름차순을 유지하고, 스택에 넣기 전 오름차순을 유지하기 위해 스택이 비어있거나 스택의 탑이 현재 삽입하려는 값보다 작을 때까지 팝 합니다. 또한 팝을 할 때는 팝한 후의 새로운 탑의 오른쪽 (비어 있다면배열의 시작)부터 현재 값의 왼쪽까지가 팝 하는 원소가 속하는 구간이 됩니다. 그림과 함께 보겠습니다. 이번에는 스택이 비어있기 때문에 스택에 곧바로 푸시 합니다.

 마찬가지로 현재값 3은 스택의 탑인 1보다 크기 때문에 푸시합니다.

 마찬가지로 현재값 5는 스택의 탑인 3보다 크기 때문에 푸시합니다.

 현재값 2는 스택의 탑인 5보다 작기 때문에 스택의 탑이 2보다 작거나 같아질 때까지 팝 하겠습니다.

 스택에서 원소를 꺼낼 때 해당 원소를 최솟값으로 가지는 구간의 넓이를 계산합니다. 이번에 팝한 5를 기점으로 오른쪽으로는 현재값 2의 직전(이번 경우에는 5) 왼쪽으로는 5를 팝 했을 때의 탑의 직후(이번 경우에는 5) 까지가 구간이 됩니다. 이번에는 구간의 길이가 1이므로 1 x 5를 하여 최댓값을 갱신합니다. 또한 여전히 스택의 탑이 2보다 크므로 한 번 더 팝 합니다.

 이전과 마찬가지로 스택에서 꺼낼 때 계산을 수행합니다. 이번에 팝한 3을 기점으로 오른쪽으로는 현재값 2의 직전(이번 경우에는 5) 왼쪽으로는 3을 팝 했을 때의 탑의 직후(이번 경우에는 3) 까지가 구간이 됩니다. 이번에는 구간의 길이가 2이므로 2 x 3을 하여 최댓값을 갱신합니다. 또한 이제 2는 스택의 탑보다 크므로 푸시합니다.

 6을 푸시합니다.

 현재값 4는 탑 6보다 작으므로 오름차순을 유지하기 위해 스택에서 6을 팝 하겠습니다. 

 6 또한 꺼낼 때 계산합니다. 그 후 4를 푸시합니다.

현재값 3이 4보다 작으므로 스택에서 4를 팝 합니다. 

 4를 꺼낼 때 마찬가지로 현재 탑 2의 오른쪽인 6부터 현재값 3의 왼쪽인 4까지가 구간이 됩니다. 2 x 4 = 8로 최댓값이 갱신되었습니다. 이후 3을 푸시합니다.

 7을 푸시합니다.

 8을 푸시합니다.

 현재값이 1이므로 스택의 탑이 1보다 크지 않을 때까지 팝 하겠습니다.

8을 팝 하였습니다.

7을 팝 하였습니다.

 3을 팝 하였습니다. 이때 3은 팝한 후 탑의 오른쪽인 6부터, 현재값 1의 왼쪽인 8까지를 구간으로 갖습니다. 최대갑이 갱신되었습니다.

2를 팝 합니다. 이제 1을 푸시합니다.

배열의 끝에 도달하면 스택에 남은 모든 값을 팝 하게 됩니다.

배열의 마지막 원소인 1을 팝 합니다.

 배열의 첫 번째 원소인 1을 팝 합니다. 

 모노토닉 배열을 이용하여 히스토그램에서 가장 넓은 직사각형을 O(1) 시간에 찾아보았습니다. 문제의 상황에 따라 스택의 오름차순/내림차순에서 값이 같은 경우를 팝 해야 할 수도 있고 아닐 수도 있습니다. 이번 경우는 값이 같아도 팝 하지 않고 진행하였습니다. 

추천 문제

오늘 배운 스택과 모노토닉 스택을 활용하여 풀 수 있는 문제 몇 개를 추천하겠습니다.

• BOJ 2104 부분배열 고르기
• BOJ 1725 히스토그램
• BOJ 3015 오아시스 재결합
• BOJ 6549 히스토그램에서 가장 큰 직사각형 

결론

 오늘은 ppt를 이용해 자료도 만들고 새로운 시도를 해보았는데 남들이 글을 볼 때 어떨지 잘 모르겠습니다. 아무튼 앞으로 더 좋은 방법들을 시도해 볼 생각이니 잘 부탁드립니다. 감사합니다.