스택: 콜 스택이 지켜보고 있어

"첫 프로그램을 짤 때부터 스택을 써왔어. 눈에 안 보였을 뿐이지. 함수를 호출할 때마다 스택에 push하고, return할 때마다 거기서 pop해 왔거든."

마지막에 들어온 게 먼저 나간다

스택의 규칙은 하나야. 마지막에 넣은 걸 먼저 꺼낸다. push는 맨 위에 얹고, pop은 맨 위에서 걷어내고, peek은 걷어내지 않고 맨 위만 들여다봐. 셋 다 O(1)이야. "맨 위"에서는 아무것도 밀 일이 없으니까. 접시 더미를 떠올리면 딱 맞아. 올릴 때도 뺄 때도 맨 위고, 맨 아래 접시를 쓰려면 위에 쌓인 걸 전부 치워야 하잖아.

콜 스택: 이미 기대고 있던 스택

여기서 모든 게 맞물려. 콜 스택, 그러니까 함수를 실제로 돌려주는 그 메커니즘이 말 그대로 스택이야. 함수 A가 B를 부르면 B의 프레임(지역 변수와 돌아갈 주소)이 A의 프레임 위에 push돼. B가 반환하면 그 프레임이 pop되고 제어는 A가 멈췄던 바로 그 자리로 떨어지지. 호출이 중첩되면 프레임이 쌓이고, 반환은 역순으로 풀려. 그래서 재귀 깊이가 곧 스택 깊이야. 복잡도 트랙에서 본 그 공간 비용이 이거고. 무한 재귀가 RecursionError를 던지는 이유도 여기 있어. 말 그대로 콜 스택을 넘쳐버린 거니까. 자료구조 하나를 배운 게 아니라, 그동안 모든 코드를 굴려온 물건의 정체를 배운 거야.

스택은 맨 위에서 push, pop, peek을 전부 O(1)에 하는 LIFO 구조야. 함수를 굴리는 콜 스택 자체가 스택이고, 그래서 재귀 깊이와 스택 오버플로가 같은 현상이야.

스택이 빛나는 곳: 매칭과 중첩

중첩이나 매칭이 걸린 문제는 웬만하면 스택 문제야. 괄호 균형 맞추기, 유효한 HTML/XML 태그, 코드의 괄호 짝 맞추기, 산술식 계산, 실행 취소 버튼(행동마다 push하고 취소할 때 가장 최근 걸 pop). 패턴은 하나로 똑같아. 열릴 때 push, 닫힐 때 pop, 그리고 pop한 게 지금 닫는 것과 짝이 맞는지 확인. pop해야 하는데 스택이 비어 있거나, 다 끝났는데 스택에 뭔가 남아 있으면 중첩이 깨진 거야. 이 패턴을 깊이 우선 탐색의 엔진으로 한 번 더 만나게 돼.

피파의 고백

한동안 나한테 "stack overflow"는 그냥 웹사이트 이름이었어. 그러다 아빠가 짚어줬지. 콜 스택, 그러니까 내 재귀 함수가 프레임을 쌓아 올리던 그것이, 내가 손으로 push하고 pop하며 배우던 바로 그 LIFO 구조라고. 그 순간 내 무한 재귀 크래시가 물리적으로 이해가 됐어. 프레임을 끝없이 push해서 진짜 스택을 넘쳐버린 거였으니까. 내가 공부하던 추상화가 알고 보니 내가 내내 딛고 서 있던 바닥이었던 거야.

Code

균형 괄호, 그리고 콜 스택·python

# 균형 괄호: 정석 스택 문제.
def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}   # 닫는 것 -> 여는 것
    for ch in s:
        if ch in "([{":
            stack.append(ch)               # 열림 -> push
        elif ch in ")]}":
            # 닫힘 -> 스택 맨 위가 그 짝 여는 것이어야 함
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                        # 남은 것 = 안 닫힌 여는 것

print(is_balanced("(a[b]{c})"))   # True
print(is_balanced("([)]"))        # False — 잘못된 중첩 순서
print(is_balanced("((("))         # False — 절대 안 닫힘

# 콜 스택 자체 (스택!) 를 재귀 깊이로 봐:
import sys
print("max call-stack depth ~", sys.getrecursionlimit())  # 기본 ~1000
# 각 재귀 호출이 프레임을 PUSH. 너무 많으면 이 스택을 넘쳐.

Exercise

위 괄호 검사기는 (), [], {}를 다뤄. 문자열 '([)]'를 어떻게 처리하는지 손으로 따라가면서 False를 반환하는 정확한 지점을 짚어. 그다음 단순 카운터로, 그러니까 여는 괄호와 닫는 괄호 개수만 세는 방식으로는 왜 '([)]'가 통과해 버리는지 설명해. 스택은 잡아내는데 카운터가 못 잡는 게 뭘까?

Hint

카운터는 몇 개가 열렸는지만 알지 어떤 종류가 열렸는지는 몰라. 스택은 여는 괄호의 종류와 순서를 같이 기억하니까 ')'가 '['를 닫으려 드는 걸 잡아내지. 카운터 입장에서는 총합이 맞으니 그냥 통과시키고.

마지막에 들어온 게 먼저 나간다

콜 스택: 이미 기대고 있던 스택

스택이 빛나는 곳: 매칭과 중첩

피파의 고백

Code

External links

Exercise

Progress

댓글 0