스택 문제 풀이는 자료구조 이름을 외우는 것보다, 문제에서 LIFO 흐름이 숨어 있는지 보는 것이 더 중요합니다. stack은 단순한 push/pop 구조지만 괄호 검사, undo, 단조 스택처럼 실전 문제에서 매우 자주 등장합니다.
이번 글에서는 stack을 정의로 끝내지 않고, 어떤 문제에서 stack이 먼저 떠올라야 하는지를 코딩테스트 기준으로 자세히 정리하겠습니다.
stack을 가장 짧게 설명하면
stack은 마지막에 들어온 것이 먼저 나가는 LIFO 구조입니다. 즉 가장 최근 상태를 가장 먼저 다시 봐야 하는 문제와 잘 맞습니다.
stack = []
for ch in text:
if ch == "(":
stack.append(ch)
else:
if not stack:
return False
stack.pop()이런 괄호 검사 예시가 stack 입문에서 가장 대표적인 이유는, 최근 열린 괄호를 가장 먼저 닫아야 하기 때문입니다. 오래된 괄호가 아니라 방금 열린 괄호부터 처리해야 하므로 LIFO가 자연스럽습니다.
std::stack 설명을 보면 LIFO 구조라는 점이 핵심입니다. 실전에서는 이 성질이 괄호, undo, 단조 스택 문제 패턴으로 확장됩니다.
문제에서 어떤 신호가 보이면 stack일까
- 최근 상태를 다시 꺼내야 한다
- 쌍을 맞춰야 한다
- 되돌리기나 취소 흐름이 있다
- 왼쪽에서 아직 처리되지 않은 후보를 잠깐 쌓아 둬야 한다
즉 최근 것부터 다시 처리해야 하는 느낌이 있으면 stack 가능성이 큽니다. 괄호 검사, 브라우저 뒤로가기, undo, 단조 스택 문제가 대표적입니다.
괄호 검사에서 stack이 자연스러운 이유
괄호 문제는 짝을 맞추는 문제입니다. 그런데 닫는 괄호가 나왔을 때 가장 먼저 확인해야 하는 것은 “가장 최근에 열린 괄호가 무엇인가”입니다. 이 질문 자체가 stack 구조와 딱 맞습니다.
만약 queue처럼 오래된 괄호부터 확인하려고 하면 순서가 완전히 깨집니다. 즉 자료구조 선택이 단순 구현 차이가 아니라 문제 의미 자체와 연결됩니다.
undo 문제에서 왜 stack이 자주 등장할까
undo는 말 그대로 가장 최근 작업부터 취소해야 합니다. 마지막으로 한 입력, 마지막으로 추가한 문자, 마지막으로 실행한 명령을 먼저 되돌려야 하므로 stack이 자연스럽습니다.
이 감각은 자료구조 차원 stack과 설계 차원 undo/redo 모두에서 자주 보입니다. 예를 들어 Command 패턴 글도 결국 최근 작업을 기록하고 되돌리는 흐름과 강하게 연결됩니다.
단조 스택은 왜 더 어렵게 느껴질까
단조 스택은 일반 stack 위에 “항상 증가 상태” 또는 “항상 감소 상태”를 유지한다는 규칙이 추가된 형태입니다. 그래서 단순 push/pop이 아니라, 현재 원소가 이전 후보를 밀어내도 되는지를 계속 판단해야 합니다.
예를 들어 다음 큰 수 문제에서는 현재 숫자가 stack top보다 크면, 그 top은 더 이상 기다릴 이유가 없습니다. 그래서 계속 pop하면서 답을 확정합니다. 이때 stack은 단순 저장소가 아니라 “아직 답을 못 찾은 후보 집합” 역할을 합니다.
stack과 queue를 헷갈릴 때 보는 기준
- 오래된 것부터 처리해야 하면 queue 가능성이 크다
- 최근 것부터 되돌아봐야 하면 stack 가능성이 크다
- 레벨 확장과 최단거리면 queue 쪽, 괄호/undo/후보 유지면 stack 쪽일 때가 많다
탐색 흐름 비교는 BFS 글과 나란히 보면 더 분명해집니다.
실전에서 자주 하는 실수
- 괄호 문제를 단순 카운팅으로만 처리하려다 순서 오류를 놓친다
- undo 문제를 배열 끝 조작으로만 생각하고 stack 패턴을 의식하지 못한다
- 단조 스택을 “그냥 어려운 stack” 정도로만 외운다
- 최근 후보를 유지해야 하는 문제를 queue나 정렬로만 억지로 풀려 한다
마무리
스택 문제 풀이의 핵심은 자료구조 정의를 외우는 것이 아니라, 최근 상태를 먼저 처리해야 하는 문제 신호를 빠르게 알아보는 일입니다.
즉 괄호 검사, undo, 단조 스택처럼 가장 최근 후보를 가장 먼저 다시 봐야 하는가를 먼저 떠올리면 stack 문제가 훨씬 잘 보입니다.
