알고리즘 03 - (기본 패턴 03) - (2) DFS(깊이 우선 탐색, Depth-First Search) - Stak 이란?

스택(Stack) 알고리즘이란?

---

1. 스택이란?

• 스택(Stack)은 데이터를 쌓아 올리는 구조로, LIFO(Last In, First Out) 원칙에 따라 동작합니다.
  • LIFO: 마지막에 추가된 데이터가 가장 먼저 제거됩니다.
  • 예: 접시를 쌓아 올린 후, 가장 위의 접시부터 꺼내는 구조.

---

2. 스택의 기본 연산

1. push: 데이터를 스택의 맨 위에 추가.
2. pop: 데이터를 스택의 맨 위에서 제거.
3. peek (또는 top): 스택의 맨 위 데이터를 확인.
4. isEmpty: 스택이 비어 있는지 확인.

---

3. 스택의 사용 사례

• 괄호의 유효성 검사:
  • 중첩된 괄호가 올바르게 닫혔는지 확인.
• DFS(깊이 우선 탐색):
  • 재귀를 명시적으로 구현할 때 사용.
• 후위 표기법 계산(Postfix Evaluation):
  • 수식 계산 시 사용.
• 문자열 뒤집기:
  • 문자열을 스택에 넣고 순서대로 꺼내면 역순이 됩니다.

---

4. 스택 문제: 괄호 유효성 검사

문제 설명

주어진 문자열이 올바른 괄호 구조를 가지는지 확인하세요.
괄호는 (), {}, []만 사용됩니다.

입력

• 예: "()[]{}", "(]", "([{}])"

출력

• 올바른 괄호: True
• 올바르지 않은 괄호: False

---

5. 스택을 활용한 해결 방법

아이디어

• 여는 괄호 (, {, [를 스택에 추가.
• 닫는 괄호 ), }, ]를 만나면:
  • 스택의 맨 위(가장 마지막에 추가된 값)와 비교.
  • 짝이 맞으면 스택에서 제거(pop).
  • 짝이 맞지 않으면 유효하지 않은 구조.

코드

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}  # 짝 맞추기

    for char in s:
        if char in mapping:  # 닫는 괄호일 경우
            top = stack.pop() if stack else '#'  # 스택이 비었으면 '#' 사용
            if mapping[char] != top:  # 짝이 맞지 않으면 False
                return False
        else:  # 여는 괄호일 경우
            stack.append(char)  # 스택에 추가

    return not stack  # 스택이 비었으면 True (모두 짝이 맞음)

---

6. 실행 과정 출력

입력 문자열: "([{}])"

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        print(f"현재 문자: {char}")
        if char in mapping:
            top = stack.pop() if stack else '#'
            print(f" - 스택에서 꺼낸 값: {top}")
            if mapping[char] != top:
                print(f" - 불일치: {char}는 {top}와 짝이 맞지 않음")
                return False
        else:
            stack.append(char)
            print(f" - 스택에 추가: {stack}")
    
    print(f"스택 상태: {stack}")
    return not stack

# 테스트 실행
print(is_valid("([{}])"))  # 출력: True

출력 결과

현재 문자: (
 - 스택에 추가: ['(']
현재 문자: [
 - 스택에 추가: ['(', '[']
현재 문자: {
 - 스택에 추가: ['(', '[', '{']
현재 문자: }
 - 스택에서 꺼낸 값: {
현재 문자: ]
 - 스택에서 꺼낸 값: [
현재 문자: )
 - 스택에서 꺼낸 값: (
스택 상태: []
True

---

7. 문제 풀이 순서

1. 여는 괄호는 스택에 추가.
2. 닫는 괄호는 스택의 맨 위 값과 비교:
   • 짝이 맞으면 스택에서 제거.
   • 짝이 맞지 않으면 유효하지 않은 구조로 판단.
3. 문자열 탐색이 끝난 후 스택이 비었는지 확인:
   • 스택이 비었으면 모든 괄호가 짝을 이룸 → True.
   • 스택에 값이 남아 있으면 짝이 안 맞는 괄호가 있음 → False.

---

8. 스스로 사고하고 암기하기 쉽게 정리

스택의 핵심 아이디어

1. “쌓고 꺼낸다”:
   • 데이터를 쌓아 올린 후, 마지막 데이터를 먼저 꺼냄(LIFO).
2. “닫는 괄호는 스택에서 쌍을 꺼낸다”:
   • 괄호 문제에서 닫는 괄호는 스택에서 가장 최근의 여는 괄호와 비교.

암기 문장

• “스택은 LIFO: 마지막에 들어간 것이 먼저 나온다.”
• “여는 괄호는 넣고, 닫는 괄호는 빼고 짝을 맞춘다.”

시각적 예제

• 입력: "([{}])"

  스택 상태:
  1. 추가 '(' → ['(']
  2. 추가 '[' → ['(', '[']
  3. 추가 '{' → ['(', '[', '{']
  4. 제거 '}' → ['(', '[']
  5. 제거 ']' → ['(']
  6. 제거 ')' → []
  최종: 스택이 비었으므로 True
  

---

9. 스택 연습 문제

1. 문제: 괄호의 유효성 검사
   • 입력: "({[]})", "([)]"
   • 출력: True, False
2. 문제: 문자열 뒤집기
   • 입력: "hello"
   • 출력: "olleh"
3. 문제: 후위 표기법 계산
   • 입력: "2 3 + 4 *"
   • 출력: 20

---