Ch.4 스택과 큐

괄호 검증 — 스택의 킬러 앱

Valid Parentheses 문제를 스택으로 해결하는 원리를 이해한다괄호 매칭 알고리즘을 Python으로 구현한다

면접관이 좋아하는 첫 번째 스택 문제

LeetCode #20 Valid Parentheses는 면접에서 가장 자주 나오는 스택 문제입니다. 열린 괄호와 닫힌 괄호가 올바르게 짝을 이루는지 검증해야 합니다.

괄호가 여러 종류일 때, 순서까지 맞춰야 한다면?

스택에 열린 괄호를 넣고, 닫힌 괄호가 오면 꺼내서 비교 — 이것이 핵심 패턴입니다.

article

핵심 내용

"( )" "{ }" "[ ]" 세 종류의 괄호가 올바르게 짝을 이루는지 확인하세요

유효한 예시 "()" → True "()[]{}" → True "{[()]}" → True 무효한 예시 "(]" → False "([)]" → False "{" → False

핵심 규칙: 가장 최근에 열린 괄호가 가장 먼저 닫혀야 합니다 — LIFO!

알고리즘은 간단합니다 열린 괄호 → push, 닫힌 괄호 → pop 후 비교

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in pairs:        # 닫힌 괄호
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:                    # 열린 괄호
            stack.append(char)
    
    return len(stack) == 0

"{[()]}"를 한 글자씩 따라가 봅시다

시간복잡도: O(n) — 문자열 한 번 순회 공간복잡도: O(n) — 최악의 경우 모든 문자가 열린 괄호

면접에서 놓치기 쉬운 엣지 케이스 3가지

코드에서 `not stack` 체크가 세 번째 케이스를 막아줍니다

"([)]"은 유효한 괄호 조합이다

isValid("{[]}")를 실행하면 stack의 최종 상태는?

stack = ___

괄호 검증 알고리즘의 시간복잡도는?

괄호 검증 마스터!

key

핵심 용어

1️⃣

열린 괄호

stack에 push

2️⃣

닫힌 괄호

stack에서 pop 후 짝이 맞는지 확인

3️⃣

끝났을 때

stack이 비어있으면 True

⚠️

빈 문자열 ""

True — 닫아야 할 것이 없음

⚠️

여는 괄호만 "(("

False — stack이 남아 있음

⚠️

닫는 괄호 먼저 ")"

False — stack이 비어있는데 pop 시도

edit_note

정리 노트

괄호 검증 — 스택의 킬러 앱

알고리즘 패턴

열린 괄호: stack.append(char)
닫힌 괄호: stack.pop()으로 짝 비교
최종 확인: len(stack) == 0이면 True

복잡도

시간: O(n) — 한 번 순회
공간: O(n) — 최악 시 모두 열린 괄호

★

면접 팁: pairs 딕셔너리를 먼저 정의하면 코드가 깔끔해집니다!

image

시각 자료

다이어그램: ds-d28

check_circle

핵심 정리

1열린 괄호 → push, 닫힌 괄호 → pop 후 비교
2시간 O(n), 공간 O(n)
3엣지 케이스: 빈 문자열, 여는 괄호만, 닫는 괄호 먼저

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작