알고리즘 이론 - 스택

☑️ To-do

• 스택 이론 정리
• week02 문제 풀이
  • 2493 / 11866 / 3190

 

 

---

스택

• 스택에서는 두 가지 연산만을 사용해서 원소의 수정을 할 수 있다.
• push , pop
• LIFO (Last In First Out) : 후입선출

 

스택 용어

• top (위치) : 삽입과 삭제 발생
• push : top에 데이터 삽입
• pop : top 데이터 삭제 후 반환
• peek : top 데이터 확인

 

활용

• DFS
• 백트래킹
• 재귀

 

 

---

Stack 자료형 정의(Ver 1)

• 스택의 원래 정의대로 스택 자료형의 조작 범위를 제한하기 위해 클래스로 새로운 자료형을 정의한다.
• 고정된 길이의 스택으로 정의한다.

 

스택 구현에 필요한 메소드들

• __init__() : 스택 초기화
• __len__() : 스택 내 데이터 개수 확인
• is_empty() : 스택이 비어있는지 확인
• is_full() : 스택이 가득 차 있는지 판단
• push() : 원소 삽입
• pop() : 원소 추출
• peek() : top 위치의 원소 반환
• clear() : 스택 내 모든 원소 삭제
• find() : 원소 검색
• count() : 원소 개수 카운트
• __contains__() : 데이터가 포함 여부 확인

 

fixed_stack.py

class FixedStack:

    class Empty(Exception): # 빈 배열 접근 시
        pass

    class Full(Exception): # 가득 찬 배열 접근 시
        pass

    def __init__(self, capacity): # 스택 초기화
        self.stack = [None] # 스택 본체
        self.capacity = capacity # 스택 크기
        self.ptr = 0 # 스택 포인터

    def __len__(self): # 스택에 들어있는 데이터 개수
        return self.ptr

    def is_empty(self): # 스택이 비어 있는지 판단(bool)
        return self.ptr <= 0

    def is_full(self): # 스택이 가득 차 있는지 판단(bool)
        return self.ptr >= self.capacity

    def push(self, value): # 스택에 요소 삽입
        if self.is_full():
            raise FixedStack.Full
        self.stack[self.ptr] = value
        self.ptr += 1

    def pop(self): # 스택에서 데이터 꺼냄
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stack[self.ptr]

    def peek(self): # 스택의 top요소 확인
        if self.is_empty():
            raise FixedStack.Empty
        return self.stack[self.ptr - 1]

    def clear(self): # 스택의 모든 데이터 삭제
        self.ptr = 0

    def find(self, value): # 스택에서 value를 찾아 인덱스를 반환 
        for i in range(self.ptr - 1, -1, -1):
            if self.stack[i] == value:
                return i
        return -1

    def count(self, value): # 스택에 있는 value의 개수를 반환
        c = 0
        for i in range(self.ptr):
            if self.stack[i] == value:
                c += 1
        return c

    def __contains__(self, value): # 스택에 value가 있는지 판단
        return self.count(value)

    def dump(self): # 스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stack[:self.ptr])

 

 

---

Stack 자료형 정의(Ver2. simple version)

stack.py

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError: # 비어있는 배열에 pop연산을 시도할 때 발생
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

 

• 클래스 명은 관례 상, 대문자로 시작한다
• 생성 함수 __init__
  • 여기서 self 는 생성된 객체 자기 자신을 지칭한다.
  ⭐ 어떤 클래스의 메소드든 간에 모두 파라미터는 self 로 시작돼야 한다!

def __init_(self):
		self.items = [] # '.' : 객체의 멤버 변수에 접근할 때 사용

 

• 길이 반환 함수 __len__
  • s.len()을 안하고 그냥 len()을 해도 해당 함수가 호출된다.

def __len__(self):
        return len(self.items)

 

 

• 모두 선형 시간 $O(1)$ 의 시간 복잡도를 갖는다!

 

---

➕ Plus

1. 예외 처리의 기본 구조

• try : 원래 실행문
• except : 예외 포착 및 처리
• else : 예외가 포착되지 않음 (생략 가능)
• finally : 마무리 (생략 가능)

 

2. raise문을 통한 예외 처리

프로그램 실행 중 의도적으로 에러를 발생시키는 방법

• 표준 내장 예외 처리 (파이썬이 제공하는 예외 처리)
  • BaseException 클래스와 직간접적으로 파생한 클래스로 제공
• 프로그래머가 정의하는 사용자 정의 예외 처리
  • Exception 클래스에서 파생

a = int(input())

if a < 0:
    raise ValueError # 내장 에러 클래스 사용
elif a == 0:
    raise Exception("Error Message!") # 직접적으로 에러 메시지 사용

 

 

 

---

백준 문제 풀이

2493. 탑

 

• Try 1 :시간초과

import sys
​
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
answer = [0] * n
​
for i in range(n - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        if arr[j] > arr[i]:
            answer[i] = j + 1
            break
​
for a in answer:
    print(a, end=' ')

• 완전탐색
• $O(n^2)$ 의 시간 복잡도를 가진다.

 

• Try 2 :시간초과

import sys
​
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
answer = [0] * n
stack = [(0, arr.pop(0))]
​
i = 1
while arr: 
    top = arr.pop(0)
    while stack and stack[-1][1] <= top:
        stack.pop()
​
    if not len(stack): answer[i] = 0
    else: answer[i] = stack[-1][0] + 1
    stack.append((i, top))
    i += 1
​
[print(a, end=' ') for a in answer]

• 스택으로 구현했지만 pop(0) 이 시간복잡도 $O(n)$ 이 소요된다.

 

• Success

# pop() 보다 큰 탑이 있을 경우 해당 탑이 수신
import sys
​
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
answer = [0] * n
stack = [(0, arr.pop(0))]
arr.reverse() # Try2 에서 시간초과 해결 -> reverse를 하고 pop()으로 추출
​
i = 1
while arr: 
    top = arr.pop()
    # 현재 top 보다 작은 값이 가장 가까이에 있으면 모두 pop
    # 전부 가려지게 됨
    while stack and stack[-1][1] <= top:
        stack.pop()
    # 스택이 비었을 경우
    if not len(stack): answer[i] = 0
    else: answer[i] = stack[-1][0] + 1
    stack.append((i, top))
    i += 1
​
[print(a, end=' ') for a in answer]
​

 

• 스택에 탑의 높이 값을 넣는다.
• 이때 스택내에 있는 현재 타깃 값 즉, 변수 top 값 보다 작은 값들을 스택에서 제거해준다.
  • 탑의 작은 탑은 무조건 맨 뒤쪽에 있는 큰 탑에 의해 가려진다!

 

 

---

🔗 Reference

• 파이썬 코딩 도장: 38.1 try except로 사용하기
• (https://dojang.io/mod/page/view.php?id=2398)
• 파이썬 에러 종류 : Built-in Exceptions — Python 3.11.0 documentation
• (https://docs.python.org/3/library/exceptions.html#concrete-exceptions)