티스토리 뷰
'어서와! 자료구조와 알고리즘은 처음이지?'
스택(Stack)
✔ 자료(data element)를 보관할 수 있는 선형 구조이다.
✔ 데이터를 넣을 때는 한 쪽 끝에서 밀어넣어야 한다 (push 연산).
✔ 데이터를 꺼낼 때에는 데이터를 밀어 넣었던 쪽과 같은 쪽에서 뽑아 꺼내야 하는 제약이 있다 (pop 연산).
✔ 후입선출(LIFO, Last- In First - Out) 특징을 가진다.
스택에서 발생하는 오류
1. 비어있는 스택에서 데이터 원소를 꺼내려 하는 경우
✔ 스택 언더 플로우 (Stack underflow)
2. 꽉 찬 스택에 데이터 원소를 넣으려 할 때
✔ 스택 오버플로우(Stack overflow)
스택의 추상적 자료구조 구현
1. 배열(Array)을 이용하여 구현한다.
✔ Python 리스트와 메서드들을 이용
2. 연결 리스트(Linked list)를 이용하여 구현한다.
✔ 양 방향 연결리스트 이용
스택의 추상적 자료구조 구현
연산의 정의
1. size(): 현재 스택에 들어있는 데이터 원소의 수를 구한다.
2. isEmpty(): 현재 스택이 비어 있는지를 판단한다.
3. push(element): 데이터 원소 element를 스택에 추가한다.
4. pop(): 스택의 맨 위에 저장된 데이터 원소를 제거, 반환한다.
5. peek(): 스택의 맨 위에 저장된 데이터 원소를 반환한다. (제거하지 않음)
배열로 구현한 스택
class ArrayStack:
# 빈 스택을 초기화
def __init__(self):
self.data = []
# 스택의 크기를 리턴
def size(self):
return len(self.data)
# 스택이 비어있는지 확인
def isEmpty(self):
return self.size() == 0
# 데이터 원소 추가
def push(self, item):
self.data.append(item)
# 데이터 원소를 삭제(리턴)
def pop(self):
return self.data.pop()
# 스택의 꼭대기 원소 반환
def peek(self):
return self.data[-1]
[ 문1. 수식의 괄호 유효성 검사]
알고리즘 설계
수식을 왼쪽부터 한글자 씩 읽어서,
✔ 여는 괄호( '(' or '{' or '[')를 만나면 스택에 push 한다.
✔ 닫는 괄호(')' or '}' or ']')를 만나면
- 스택이 비어 있으면 올바르지 않은 수식
- 스택에서 pop, 쌍을 이루는 여는 괄호 인지 검사(맞지 않으면 올바르지 않은 수식)
✔ 끝 까지 검사한 후, 스택이 비어 있어야 올바른 수식
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
def solution(expr):
match = {
')': '(',
'}': '{',
']': '['
}
S = ArrayStack()
for c in expr:
# 여는 괄호 만나면 스택에 push()
if c in '({[':
S.push(c)
# 닫는 괄호 만난 경우
elif c in match:
# 스택이 비어 있으면 올바르지 않은 수식
if S.isEmpty():
return False
# 스택에서 pop, 쌍을 이루는 괄호인지 검사
else:
t = S.pop()
if t != match[c]:
return False
# 끝까지 검사한 후, 스택이 비어있어야 올바른 수식.
return S.isEmpty()
'Algorithm > 알고리즘' 카테고리의 다른 글
[프로그래머스 강의] 13강 스택(Stack) (3) (0) | 2022.05.08 |
---|---|
[프로그래머스 강의] 12강 스택(Stack) (2) (0) | 2022.05.08 |
[프로그래머스 강의] 10강 연결리스트(Linked List) (4) (0) | 2022.05.02 |
[프로그래머스 강의] 9강 연결리스트(Linked List) (3) (0) | 2022.04.30 |
[프로그래머스 강의] 8강 연결리스트(Linked List) (2) (0) | 2022.04.28 |
- Total
- Today
- Yesterday
- 리스트함축
- https
- 자바
- 데이터베이스
- 완전탐색
- It
- 파이썬
- 운영체제
- 보험
- 리스트2
- 연결리스트활용
- 정렬
- 리스트
- CS 스터디
- SW
- 프로세스 주소공간
- 코드업 기초
- 알고리즘
- 자료구조
- CS
- 프로그래머스강의
- 네트워크
- 자료구조와알고리즘 23강
- 리스트 복사
- 이차 리스트
- 프로그래머스
- 스터디
- Greedy sort
- 이진탐색
- CS.
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |