스택 활용 (괄호 검사, DFS)
스택의 LIFO 특성을 활용한 대표적인 실무 알고리즘들
1. 괄호 유효성 검사
입력: "({[]})"
스택 변화:
( → [( ]
{ → [( { ]
[ → [( { [ ]
] → [( { ] ← [ 와 매칭!
} → [( ] ← { 와 매칭!
) → [ ] ← ( 와 매칭!
→ 스택 비어있음 → 유효
입력: "({)}"
( → [( ]
{ → [( { ]
) → { 와 ) 가 맞지 않는다. 무효
def is_valid(s):
stack = []
pairs = {')':'(', '}':'{', ']':'['}
for ch in s:
if ch in '({[':
stack.append(ch)
elif ch in ')}]':
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0
2. DFS (깊이 우선 탐색)
1
/ \
2 3
/ \
4 5
스택 DFS: [1] → [3,2] → [3,5,4]
→ 방문: 1 → 2 → 4 → 5 → 3
3. 콜 스택 (함수 호출)
main() 호출
↓ 스택: [main]
foo() 호출
↓ 스택: [main, foo]
bar() 호출
↓ 스택: [main, foo, bar]
bar() 반환
↓ 스택: [main, foo]
foo() 반환
↓ 스택: [main]
main() 반환
↓ 스택: []
스택 오버플로우: 재귀 너무 깊으면 스택 메모리 초과!
4. 후위 표기식 계산
중위: 3 + 4 * 2
후위: 3 4 2 * +
계산:
3 → [3]
4 → [3, 4]
2 → [3, 4, 2]
<em> → [3, 8] (4</em>2)
+ → [11] (3+8)
스택 활용 정리
| 활용 | 핵심 원리 |
|---|---|
| 괄호 검사 | 열림→push, 닫힘→pop 매칭 |
| DFS | 다음 방문할 노드 push |
| 콜 스택 | 함수 호출→push, 반환→pop |
| 후위 표기식 | 피연산자 push, 연산자→pop 2개 |
| Undo/Redo | 행동 push, 되돌리기 pop |
| 뒤로가기 | 페이지 push/pop |