스택

스택이란?

스택(stack) 은 나중에 넣은 것이 먼저 나오는 자료구조입니다. 이 규칙을
LIFO(Last In First Out)라고 부릅니다. 접시를 쌓아 올리고 위에서부터 꺼내는
모습을 떠올리면 정확합니다.

스택이 할 수 있는 일은 단 세 가지입니다.

• push — 맨 위에 하나 올린다.
• pop — 맨 위에서 하나 꺼낸다.
• top — 맨 위를 들여다본다(꺼내지는 않음).

세 연산 모두 \(O(1)\)입니다.

1. 왜 LIFO가 유용한가

스택은 가장 최근의 것을 먼저 처리해야 하는 상황에서 빛납니다. 대표적으로
괄호 짝 맞추기가 있습니다. 여는 괄호를 만나면 쌓아 두고, 닫는 괄호를 만나면
가장 최근에 쌓인 것과 짝지어 꺼냅니다.

( [ ] )
1) (  → 스택: (
2) [  → 스택: ( [
3) ]  → [ 와 짝 → 스택: (
4) )  → ( 와 짝 → 스택: 비었음 → 올바른 괄호!

"가장 가까운 미해결 항목"을 늘 맨 위에서 즉시 찾을 수 있다는 것이 스택의 힘입니다.

2. 함수 호출도 스택이다

프로그램이 함수를 부를 때, 컴퓨터는 호출 스택(call stack) 에 복귀 위치를
쌓습니다. 재귀가 동작하는 것도 이 스택 덕분입니다. 그래서 재귀가 너무 깊으면
스택 오버플로가 납니다 — 스택의 동작을 이해하면 재귀도 자연히 이해됩니다.

3. 대표 활용

스택이 등장하는 전형적인 문제들입니다.

4. 모노톤 스택 맛보기

"각 원소의 오른쪽에서 자기보다 큰 첫 번째 원소"를 찾는 문제는 스택으로
\(O(N)\)에 풀립니다. 핵심은 스택을 단조(monotone) 상태로 유지하는 것입니다.

새 원소가 들어올 때, 스택 맨 위가 새 원소보다 작으면 "그 작은 원소의 답은 바로
이 새 원소다"라고 확정하며 꺼냅니다. 각 원소가 한 번씩 들어가고 한 번씩 나오므로
전체 \(O(N)\)입니다. (구현은 다음 강의에서.)

5. 복잡도와 메모리

스택은 보통 배열이나 연결 리스트로 구현하며, 모든 기본 연산이 \(O(1)\)입니다.
\(N\)개의 원소를 다루는 알고리즘이라면 메모리도 \(O(N)\)입니다. "최근 것부터
처리"라는 신호가 보이면 스택을 떠올리세요.

정리

스택은 LIFO 한 줄로 요약됩니다. 괄호, 수식, 되돌리기, 모노톤 스택 — 모두
"가장 최근의 미해결 항목을 즉시 꺼낸다"는 같은 아이디어의 변주입니다.

스택을 코드로

스택은 직접 짤 수도 있고 라이브러리를 쓸 수도 있습니다. 두 방법과 대표 응용을
모두 다룹니다.

1. 라이브러리 스택

#include <stack>
stack<int> st;
st.push(5);
if (!st.empty()) {
    int x = st.top();   // 맨 위 보기
    st.pop();           // 맨 위 제거 (값을 돌려주지 않음!)
}
cout << st.size();

st = []            # 리스트가 곧 스택
st.append(5)       # push
if st:
    x = st[-1]     # top
    st.pop()       # pop (값도 돌려줌)

C++ stack::pop()은 값을 돌려주지 않으니, 꺼낸 값이 필요하면 top()으로 먼저
읽고 pop()하세요. 빈 스택에서 top/pop을 부르면 정의되지 않은 동작이므로
항상 empty()를 먼저 확인합니다.

2. 배열로 직접 구현 (가장 빠름)

int st[1000000], sp = 0;        // sp = 스택 포인터(다음 빈 칸)
void push(int x) { st[sp++] = x; }
int pop() { return st[--sp]; }
bool empty() { return sp == 0; }

경쟁 프로그래밍에서는 이렇게 배열로 직접 짜면 라이브러리보다 빠르고 디버깅도
쉽습니다.

3. 괄호 검사 완성 코드

bool valid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;          // 닫는데 짝이 없음
            char o = st.top(); st.pop();
            if (c == ')' && o != '(') return false;
            if (c == ']' && o != '[') return false;
            if (c == '}' && o != '{') return false;
        }
    }
    return st.empty();                              // 안 닫힌 게 없어야
}

def valid(s):
    pair = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in '([{':
            st.append(c)
        else:
            if not st or st[-1] != pair[c]:
                return False
            st.pop()
    return not st

두 가지를 모두 확인해야 합니다: 닫는 괄호인데 스택이 비었거나 짝이 안 맞으면
실패, 끝났을 때 스택에 무언가 남아도 실패.

4. 모노톤 스택: 오른쪽 큰 원소(NGE)

vector<int> nge(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;                      // 아직 답을 못 찾은 인덱스
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];       // i가 그 원소의 답
            st.pop();
        }
        st.push(i);
    }
    return res;                         // 끝까지 답 없으면 -1
}

각 인덱스는 한 번 push, 한 번 pop되므로 전체 \(O(N)\)입니다. 값이 아니라
인덱스를 쌓는 것이 포인트입니다(거리 계산 등에도 쓰려고).

5. 흔한 실수

• 빈 스택 접근 — top/pop 전에 empty() 확인.
• C++ pop()이 값 반환 안 함 — top()으로 먼저 읽기.
• 모노톤 스택의 부등호 — 큰 원소를 찾을 땐 <, "크거나 같은"을 원하면 <=로.
  엄밀/비엄밀을 문제 정의에 맞추세요.

6. 패턴 알아보기

"가장 가까운 ~", "올바른 괄호", "되돌리기", "다음 큰/작은 원소" — 이런 표현이
보이면 스택입니다. 특히 \(O(N^2)\)로 보이는 "각 원소마다 한쪽 방향 탐색"이
모노톤 스택으로 \(O(N)\)이 되는 경우가 많습니다.

실전에서 스택 문제 알아보기

스택 문제는 "스택을 쓰시오"라고 말해 주지 않습니다. 대신 특정한 문장
패턴으로 신호를 보냅니다. 그 패턴을 모아 정리합니다.

1. 출제 신호

• 짝 맞추기 — 괄호, 여는 것과 닫는 것, 태그. "올바른 괄호열"이라는 말이
  보이면 즉시 스택입니다.
• "가장 가까운 왼쪽(오른쪽)의 더 큰/작은 원소" — 오큰수 류. 모노톤
  스택의 대표 신호입니다.
• 취소/되돌리기 — 문자열 폭발(인접 같은 문자 제거), 편집기 커서, 백스페이스.
  "마지막에 한 일을 취소"는 LIFO 그 자체입니다.
• 중첩 구조의 깊이 — 괄호 깊이, 레이저 절단처럼 안쪽부터 처리되는 구조.
• 히스토그램 최대 직사각형처럼 "내 앞을 가로막는 첫 원소" 를 찾는 문제.

2. 풀이 결정 절차

1. 무엇을 push하나? — 값 자체인가, 인덱스인가? 위치·거리가 필요하면
   인덱스를 넣어야 합니다.
2. 언제 pop하나? — pop 조건을 한 문장으로 적어 보세요.
   "새 원소보다 작거나 같은 것은 더 이상 답이 될 수 없으므로 제거" 식으로.
3. 스택이 유지하는 불변식을 정합니다 — 모노톤 스택이라면 "항상
   감소(증가) 수열"이 유지되는지 확인합니다.
4. 다 처리한 뒤 스택에 남은 원소의 의미(짝 없음 = -1 등)를 정합니다.

3. 자주 하는 실수

• 빈 스택에서 pop/top. 닫는 괄호를 만났을 때 무조건 pop하면 )( 같은
  입력에서 터집니다. 항상 비었는지 먼저 확인하세요.

if (c == ')') {
    if (st.empty()) { ok = false; break; }   // 빈 스택 검사 먼저!
    st.pop();
}

• 모노톤 스택의 등호 방향. <로 pop할지 <=로 pop할지는 "같은 값"을 답으로
  인정하는지에 따라 갈립니다. 예제에 같은 값을 넣어 검증하세요.
• 값을 push해 놓고 거리를 물음. "몇 칸 떨어져 있는가"가 필요한데 값만
  넣으면 복원 불가입니다. 인덱스를 push하고 값은 a[idx]로 조회하세요.
• 결과 순서 뒤집기 누락. 스택으로 모은 결과는 역순입니다. 문자열을 만들 때
  마지막에 reverse가 필요한지 확인하세요.
• 모든 문자를 다 본 뒤 스택이 비었는지 확인 안 함. (((는 끝까지 에러가
  없지만 올바른 괄호열이 아닙니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 괄호 짝
맞추기로 시작해 폭발·취소형을 거쳐 모노톤 스택 문제로 끝나는 흐름이니
순서대로 푸세요.

각 문제마다 "pop 조건 한 문장"을 코드 작성 전에 주석으로 적는 연습을
하면 실수가 크게 줍니다. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.