thenullpage.com
1. 마지막에 넣은 것을 먼저 꺼내는 구조
스택(stack)은 값을 한쪽 끝에서만 넣고 빼는 자료구조입니다. 식당에 접시를 쌓아둔 모습과 같습니다. 새 접시는 맨 위에 올리고 꺼낼 때도 맨 위 접시부터 집습니다. 밑에 깔린 접시를 쓰려면 위에 놓인 것을 전부 치워야 합니다.
이렇게 마지막에 들어온 값이 먼저 나가는 규칙을 후입선출(LIFO)이라고 부릅니다. 넣는 동작은 push, 빼는 동작은 pop, 꺼내지 않고 맨 위 값만 들여다보는 동작은 top이라고 합니다. 세 동작 모두 맨 위 한 자리만 건드리니 값이 열 개든 백만 개든 걸리는 시간이 같은 O(1)입니다.
가운데 값을 못 꺼내는 것은 불편해 보이지만 이 제약이 오히려 쓸모입니다. 어떤 값이 나올 차례인지 고민할 필요 없이 항상 맨 위만 보면 되니, 나중에 들어온 것부터 처리해야 하는 문제가 그대로 풀립니다.
2. 파이썬에서는 리스트가 그대로 스택입니다
스택을 쓰겠다고 클래스를 새로 만들 필요는 없습니다. 리스트의 append와 pop이 이미 맨 뒤에서 넣고 빼는 동작입니다.
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)
print(stack.pop())
print(stack[-1])
print(stack)
[1, 2, 3]
3
2
[1, 2]
pop은 괄호 안을 비워두면 맨 뒤 값을 빼서 돌려줍니다. 꺼내지 않고 맨 위만 보고 싶을 때는 stack[-1]을 씁니다. 조심할 곳은 빈 스택입니다.
stack = []
stack.pop()
IndexError: pop from empty list
그래서 pop 앞에는 값이 남아 있는지 확인하는 조건이 붙습니다. 빈 리스트는 조건문에서 거짓으로 취급되니 if stack: 한 줄이면 충분합니다.
3. 괄호가 짝이 맞는지 검사하기
스택이 가장 잘 어울리는 문제입니다. 여는 괄호가 나오면 쌓아두고, 닫는 괄호가 나오면 가장 최근에 쌓아둔 것과 짝이 맞는지 봅니다.
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
else:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_valid("({[]})"))
print(is_valid("(]"))
print(is_valid("(("))
True
False
False
마지막 줄이 중요합니다. 끝까지 다 훑었는데 스택에 여는 괄호가 남아 있으면 닫히지 않은 것이라 거짓이 되어야 합니다. 문자열을 한 번만 지나가니 O(n)입니다.
4. 계산기가 수식을 푸는 방식
3 + 4 * 2처럼 사람이 쓰는 표기를 중위 표기법이라고 합니다. 곱셈을 먼저 해야 한다는 우선순위 때문에 왼쪽부터 순서대로 계산할 수가 없습니다. 연산자를 뒤에 두는 후위 표기법으로 바꾸면 3 4 2 * + 가 되고, 우선순위도 괄호도 필요 없어집니다. 이 형태는 스택 하나로 계산됩니다.
def calc(tokens):
stack = []
for t in tokens:
if t in "+-*/":
b = stack.pop()
a = stack.pop()
if t == "+":
stack.append(a + b)
elif t == "-":
stack.append(a - b)
elif t == "*":
stack.append(a * b)
else:
stack.append(a // b)
else:
stack.append(int(t))
return stack.pop()
print(calc(["3", "4", "2", "*", "+"]))
11
숫자는 쌓아두기만 하고, 연산자를 만나면 가장 최근에 쌓인 두 개를 꺼내 계산한 뒤 결과를 다시 넣습니다. 꺼내는 순서에 주의해야 합니다. 먼저 나오는 값이 오른쪽에 있던 숫자라서 a와 b를 바꿔 쓰면 뺄셈과 나눗셈의 답이 달라집니다.
5. 함수 호출 자체가 스택으로 돌아갑니다
프로그램이 함수를 부르면 돌아올 위치와 그 안의 변수들을 어딘가에 쌓아둡니다. 이 공간을 호출 스택이라고 합니다. 함수가 끝나면 맨 위 기록을 꺼내 원래 자리로 돌아갑니다. 재귀 함수가 동작하는 원리도 같습니다. 다만 쌓을 자리에 한계가 있습니다.
def depth(n):
return depth(n + 1)
depth(1)
RecursionError: maximum recursion depth exceeded
파이썬은 재귀 깊이를 기본 1000 근처로 제한해 두고 넘어서면 오류를 냅니다. 끝나지 않는 재귀를 일찍 잡아주는 안전장치입니다. 실제로 깊이 들어가야 하는 문제라면 sys.setrecursionlimit로 한도를 올리거나, 재귀를 걷어내고 직접 만든 스택에 담아 반복문으로 바꿉니다. 코딩 테스트에서 재귀 코드가 이유 없이 죽는다면 대개 이 한도에 걸린 것입니다.
6. 다음에 나오는 더 큰 값을 한 번에 찾기
각 위치에서 오른쪽을 보며 자기보다 큰 첫 값을 찾는 문제가 있습니다. 위치마다 오른쪽을 전부 훑으면 O(n^2)입니다. 아직 답을 못 찾은 위치를 스택에 담아두면 한 번 지나가는 것으로 끝납니다.
def next_greater(nums):
answer = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
answer[stack.pop()] = num
stack.append(i)
return answer
print(next_greater([2, 5, 3, 8, 1]))
[5, 8, 8, -1, -1]
값이 아니라 위치를 쌓는 것이 요령입니다. 새 값이 들어오면 스택 위쪽에 남아 있던 작은 값들의 답이 한꺼번에 정해지니 꺼내면서 채웁니다. 답을 못 찾은 값은 -1로 남습니다. 스택에는 항상 큰 값부터 순서대로 남아 있어서 이런 방식을 단조 스택이라고 부릅니다. 모든 위치가 스택에 한 번 들어갔다 한 번 나오므로 반복문이 겹쳐 보여도 전체는 O(n)입니다.
7. 스택을 떠올려야 하는 상황
지금까지 본 문제들의 공통점은 나중에 들어온 것부터 처리해야 한다는 점입니다. 괄호는 가장 최근에 열린 것과 짝을 맞추고, 수식은 가장 최근 두 숫자를 계산하고, 되돌리기는 마지막 작업부터 취소합니다. 브라우저 뒤로 가기도 방문한 주소를 쌓아두었다가 위에서부터 꺼내는 동작입니다.
정리하면 챙길 것은 세 가지입니다. 파이썬에서는 리스트의 append와 pop만으로 스택이 된다는 것, pop을 부르기 전에 비었는지 확인해야 한다는 것, 오른쪽에서 처음 만나는 큰 값 같은 문제는 단조 스택으로 O(n)까지 줄어든다는 것입니다.