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

"넌 첫 프로그램부터 스택을 써왔어 — 그저 못 봤을 뿐이야. 네가 하는 모든 함수 호출이 하나에 push 하고, 모든 return 이 거기서 pop 해."

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

스택엔 규칙 하나: 마지막에 넣은 게 먼저 꺼내는 거. push 는 맨 위에 추가, pop 은 맨 위에서 제거, peek 은 제거 없이 맨 위를 봐 — 다 O(1), "맨 위" 는 절대 뭔가를 밀 필요가 없으니까. 접시 더미를 생각해: 맨 위에서 더하고 가져가고, 맨 아래 거에 닿으려면 위에 있는 걸 다 치워야 해.

콜 스택: 네가 이미 의존하는 스택

모든 걸 다시 짜맞추는 부분: 콜 스택 — 네 함수를 돌리는 메커니즘 — 이 말 그대로 스택이야. 함수 A 가 B 를 호출하면, B 의 프레임 (그 지역 변수, return 주소) 이 A 의 프레임 위에 push 돼. B 가 반환하면, 그 프레임이 pop 되고, 제어가 A 가 떠난 정확히 그 자리로 떨어져. 중첩 호출이 쌓이고; 반환은 역순으로 풀려. 그래서 재귀 깊이 = 스택 깊이 (Complexity 트랙의 공간 비용) 이고, 무한 재귀가 RecursionError 를 던지는 이유야 — 말 그대로 콜 스택을 넘친 거야. 자료구조만 배운 게 아니라; 네 모든 코드를 실행해온 그것을 배운 거야.

스택은 맨 위에서 O(1) push/pop/peek 하는 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