이번 포스트에서는 “스택 자료구조”를 정리했습니다. 자료구조란 “구조+연산” 이기 때문에 이러한 특징을 살펴보고, 이를 이용한 알고리즘 문제를 풀어보았습니다.
스택 구조
스택은 데이터를 한쪽으로만 넣을 수 있으며, 중간에 있는 데이터를 삭제할 수 없습니다. 가장 큰 특징은 후입선출 (LIFO: Last-In-First-Out) 형식의 선형 자료구조입니다.
후입선출 (LIFO):
- 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다.
- 이는 과자 프링글스를 생각하면 쉽습니다. 젤 나중에 넣은 칩 조각을 가장 먼저 먹게 되는 것과 같은 이치죠.
- 이는 먼저 들어온 데이터가 먼저 나가는 ‘큐 (Queue)’와의 가장 큰 차이점입니다.
스택 vs. 큐 vs. 리스트:
- 스택(Stack): 삽입과 삭제를 스택의 한쪽(top)에서만 수행합니다.
- 큐(Queue): 삽입은 큐의 한쪽(rear)에서 하고, 삭제는 삽입의 반대쪽(front)에서 수행합니다.
- 리스트(List): 순서가 있고 읽기, 삽입, 삭제를 어느 곳에서나 수행할 수 있습니다.
스택 자료구조 연산
스택(stack) 데이터 구조에 필요한 기본 연산들
- Push: 스택의 맨 위에 요소를 추가하는 연산입니다.
- Pop: 스택의 맨 위에서 요소를 제거하는 연산입니다.
- IsEmpty: 스택이 비어 있는지 확인하는 연산입니다.
- IsFull: 스택이 가득 찼는지 확인하는 연산입니다.
- Peek: 스택의 맨 위에 있는 요소를 제거하지 않고 값을 반환하는 연산입니다.
스택 자료구조 이용한 알고리즘
“올바른 괄호 사용 검사” 기능을 스택 자료 구조를 활용하여 풀 수 있습니다.
올바른 괄호의 조건은 아래와 같습니다.
- 왼쪽 괄호와 오른쪽 괄호의 종류와 개수가 같아야 함
- 닫는 괄호가 먼저 나오면 안됨
구현
- 리스트는 사실 스택 자료구조가 아닙니다. 하지만
append()와pop()만 사용해서 스택처럼 사용해보겠습니다. - 리스트에 여는 괄호는
append(), 닫는 괄호는pop()을 합니다. - 정상적인 괄호이면 리스트가 비어있을 것이고, 리스트에 남는 요소가 있다면 괄호 사용에 문제가 있다고 판단 할 수 있습니다.
"""
출력
출력은 표준 출력을 사용한다.
만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
예제 입력
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
예제 출력
NO
NO
YES
NO
YES
NO
예제 입력
3
((
))
())(()
예제 출력
NO
NO
NO
백준 문제 : https://www.acmicpc.net/problem/9012
"""
def check_bracket(str):
try:
check_li = []
for i in str:
if i == '(':
check_li.append(i)
elif i == ')':
check_li.pop()
print('NO') if check_li else print('YES')
except IndexError:
print('NO')
repeat = int(input())
input_li = [input() for _ in range(repeat)]
for input_str in input_li : check_bracket(input_str)마치며
알고리즘을 처음 공부해서 그런지 정말 간단해 보이는 문제도 몇 시간씩 걸리는 좌절을 경험하고 있습니다….ㅎ
어느 정도 숙련이 되나 쑥쑥 풀어질까요?… 주말에 그리디, 재귀, 이분 탐색을 다시 한 번 공부해야 할 것 같습니다.
참고하면 좋은 글
파이썬 문자열 함수 : f-string, count(), find(), replace(), join(), index()
파이썬의 기초 문법 중 하나인 문자열 함수 !! 저는 파이썬 문자열 함수는 약 4년 전에 파이썬 처음 공부할 때 빼고는 본 적이 없습니다. 그런데 알고리즘 문제를 풀다 보니 다시 한 번 정리하면 좋을 것 같아서 몇 가지 정리해보았습니다.. Read more