스택

🎯 학습 목표

이 강을 마치면 스택(stack)의 동작 원리인 LIFO를 설명하고, 파이썬 리스트로 스택을 구현할 수 있습니다. 그리고 스택이 답이 되는 문제 유형 — 괄호 검사, 짝 맞추기, 되돌리기, 수식 계산 — 을 알아보고 직접 풀 수 있게 됩니다.

스택은 구조가 단순한데 활용도가 매우 높습니다. 그리고 뒤에 나올 재귀(13강)와 DFS(23강)가 내부적으로 스택으로 동작하므로, 여기서 확실히 잡아 두면 뒤가 편해집니다.

💡 LIFO — 마지막에 넣은 것이 먼저 나온다

스택은 한쪽 끝에서만 넣고 뺄 수 있는 자료구조입니다. 그래서 가장 나중에 넣은 것이 가장 먼저 나옵니다. 이 규칙을 LIFO(Last In, First Out)라고 부릅니다.

스택의 동작

  push(1)   push(2)   push(3)      pop()      pop()
                                  → 3 반환   → 2 반환

            ┌───┐
            │ 3 │ ← top
    ┌───┐   ├───┤    ┌───┐    ┌───┐
    │ 2 │   │ 2 │    │ 2 │←top│   │
  ┌─┴───┴─┐ ├───┤  ┌─┴───┴─┐┌─┴───┴─┐
  │   1   │ │ 1 │  │   1   ││   1   │←top
  └───────┘ └───┘  └───────┘└───────┘

  ▲ 넣는 곳과 빼는 곳이 같다 (top)
    중간에 있는 값은 꺼낼 수 없다

  현실의 비유
   · 접시 쌓기 — 맨 위 접시부터 꺼낸다
   · 브라우저 뒤로 가기 — 마지막 방문 페이지부터
   · 실행 취소(Ctrl+Z) — 마지막 작업부터 되돌린다

스택의 기본 연산은 네 가지입니다. 전부 O(1)입니다.

연산	의미	파이썬 리스트로는
push	맨 위에 넣기	stack.append(x)
pop	맨 위에서 꺼내기	stack.pop()
peek / top	맨 위를 보기만 하기	stack[-1]
isEmpty	비었는지 확인	not stack

여기서 3강의 내용이 이어집니다. 리스트의 맨 뒤 추가·삭제는 O(1)이었습니다. 스택은 맨 뒤만 쓰는 자료구조이므로, 파이썬 리스트를 그대로 스택으로 쓰면 됩니다. 별도 클래스를 만들 필요가 없습니다.

반대로 맨 앞을 쓰면 안 됩니다. insert(0, x)와 pop(0)은 O(n)이라 스택으로 쓰기에 부적절합니다.

📖 스택이 답이 되는 문제 유형

문제를 읽다가 다음 신호가 보이면 스택을 떠올리세요.

• 짝을 맞춰야 한다 — 괄호, 태그, 여는 것과 닫는 것
• 가장 최근 것과 비교한다 — 직전 값, 마지막으로 본 것
• 되돌려야 한다 — 실행 취소, 뒤로 가기
• 중첩 구조를 처리한다 — 안쪽부터 계산해야 하는 수식
• 역순으로 꺼내야 한다 — 넣은 반대 순서로 처리

대표 예 : 괄호 검사의 원리

  입력 "( [ ] { } )" 를 왼쪽부터 본다

  (   → 여는 괄호다. 스택에 넣는다        [ ( ]
  [   → 여는 괄호다. 스택에 넣는다        [ ( , [ ]
  ]   → 닫는 괄호다. 맨 위와 짝인가?
        맨 위 [ 와 짝이 맞다 → 꺼낸다     [ ( ]
  {   → 넣는다                            [ ( , { ]
  }   → 맨 위 { 와 짝 → 꺼낸다            [ ( ]
  )   → 맨 위 ( 와 짝 → 꺼낸다            [ ]

  끝났을 때 스택이 비어 있으면 → 올바른 괄호

  ▲ 실패하는 경우 세 가지
   ① 닫는 괄호인데 스택이 비어 있다   → ")(" 같은 경우
   ② 맨 위와 짝이 안 맞는다           → "(]" 같은 경우
   ③ 다 봤는데 스택이 안 비었다       → "((" 같은 경우

  ▲ 왜 스택인가
    가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다.
    이것이 정확히 LIFO다.

💻 실전 예제 — 괄호 검사와 수식 계산

두 가지 대표 문제를 구현해 보겠습니다.

def is_valid_brackets(s):
    """괄호가 올바르게 짝지어졌는지 → O(n)"""
    pairs = {")": "(", "]": "[", "}": "{"}   # 닫는 것 → 여는 것
    stack = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)                 # 여는 괄호는 쌓는다
        elif ch in pairs:
            if not stack:                    # ① 꺼낼 게 없다
                return False
            if stack.pop() != pairs[ch]:     # ② 짝이 안 맞는다
                return False
    return not stack                         # ③ 남아 있으면 False


def calc_postfix(tokens):
    """후위 표기식 계산 : ["3","4","+","2","*"] → 14"""
    stack = []
    for token in tokens:
        if token in "+-*/":
            b = stack.pop()                  # 나중에 넣은 것이 오른쪽 값
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))     # 0에 가까운 쪽으로 버림
        else:
            stack.append(int(token))
    return stack[0]


print(is_valid_brackets("([]{})"))   # True
print(is_valid_brackets("(]"))       # False
print(is_valid_brackets("(("))       # False
print(calc_postfix(["3", "4", "+", "2", "*"]))   # (3+4)*2 = 14

코드를 줄 단위로 보겠습니다.

• pairs = {")": "(", ...} — 닫는 괄호를 키로 두고 짝인 여는 괄호를 값으로 저장합니다. 딕셔너리 조회는 평균 O(1)이라 if문을 여러 번 쓰는 것보다 깔끔합니다.
• if ch in "([{" — 문자열에 대한 in이지만 길이가 3인 상수 문자열이므로 사실상 O(1)입니다.
• if not stack — 빈 리스트는 거짓으로 평가됩니다. len(stack) == 0과 같은 뜻이고 더 파이썬답습니다.
• stack.pop() != pairs[ch] — 맨 위를 꺼내면서 동시에 짝을 확인합니다. 한 줄로 두 가지를 처리합니다.
• return not stack — 반복이 끝났을 때 스택이 비어 있어야 올바릅니다. 남아 있다면 닫히지 않은 괄호가 있다는 뜻입니다.
• b = stack.pop(), a = stack.pop() — 순서가 중요합니다. 나중에 꺼낸 것이 왼쪽 피연산자입니다. 뺄셈·나눗셈에서 순서를 바꾸면 답이 틀립니다.
• int(a / b) — 파이썬의 //는 음수에서 아래로 내림합니다. 문제에서 0 방향 버림을 요구하면 int(a / b)를 써야 합니다. 이 차이로 틀리는 경우가 실제로 많습니다.

두 함수 모두 입력을 한 번만 훑고, 각 원소마다 O(1) 연산을 하므로 시간 O(n)입니다. 공간은 최악의 경우 모든 원소가 스택에 쌓이므로 O(n)입니다.

후위 표기식은 연산자를 뒤에 쓰는 방식입니다. 3 4 +는 3 + 4를 뜻합니다. 괄호 없이도 계산 순서가 정해지기 때문에 스택 하나로 계산이 됩니다.

⚠️ 자주 하는 실수

첫째, 빈 스택에서 pop()을 합니다. 빈 리스트에 pop()을 하면 오류가 납니다. 꺼내기 전에 반드시 if not stack으로 확인하세요. 괄호 문제에서 ")(" 같은 입력이 이 오류를 유발합니다.

둘째, pop(0)을 씁니다. 스택은 맨 뒤를 씁니다. pop(0)은 맨 앞이고 O(n)이며, 동작도 스택이 아니라 큐가 됩니다.

셋째, 피연산자 순서를 뒤집습니다. a - b와 b - a는 다릅니다. 스택에서 먼저 꺼낸 것이 오른쪽이라는 점을 항상 기억하세요.

넷째, 마지막에 스택이 비었는지 확인하지 않습니다. "((" 같은 입력은 반복문 안에서는 아무 문제가 없습니다. 끝난 뒤에 남아 있는지를 봐야 잡힙니다.

다섯째, 스택 대신 문자열 치환을 반복합니다. 괄호를 replace("()", "")로 계속 지우는 방식도 답은 나오지만, 매번 O(n) 복사가 일어나 O(n²)이 됩니다. 스택은 O(n)입니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	스택은 LIFO — 마지막에 넣은 것이 먼저
2	파이썬은 리스트를 그대로 스택으로 쓴다
3	append / pop() / stack[-1] — 전부 O(1)
4	짝 맞추기·최근 값 비교·되돌리기면 스택
5	꺼내기 전에 비었는지 확인
6	끝난 뒤 스택이 비었는지도 확인
7	후위 표기식은 먼저 꺼낸 값이 오른쪽

지금 해 볼 것은 괄호 검사 함수에 "([)]"를 넣어 보는 것입니다. 여는 괄호 개수와 닫는 괄호 개수는 같지만 순서가 어긋난 경우이고, 개수만 세는 풀이로는 잡히지 않습니다. 스택이 왜 필요한지 보여 주는 입력입니다.

다음 6강 「큐」에서는 스택과 반대인 FIFO 구조를 다룹니다. 3강에서 잠깐 등장한 deque가 주인공이고, 24강 BFS의 토대가 되는 자료구조입니다.

📚 참고 자료

• Using Lists as Stacks — Python 공식 문서
• Truth Value Testing — Python 공식 문서
• TimeComplexity — Python Wiki