강의
목차
- 스택
- 수식의 후위 표기법
- 후위 표기 수식 계산
- 큐
- 환형 큐
- 우선 순위 큐
11. 스택
이제부터 살펴볼 자료구조 특정한 종류의 문제를 풀기 위한 알고리즘을 위해 구현되는 자료구조들
스택 : 자료를 보관할 수 있는 선형 구조 넣을 때에는 한 쪽 끝에서 밀어넣어야 하고 -> push 꺼낼 때에는 같은 쪽에서 꺼내야 하는 제약이 있음 -> pop
-
후입 선출 (LIFO) 특징을 가지는 선형 자료구조
- 스택의 동작
-
스택에서 발생하는 오류
- 비어있는 스택에서 데이터 원소를 꺼내려 할 때 -> 스택 언더플로우
- 꽉 찬 스택에 데이터 원소를 넣으려 할 때 -> 스택 오버 플로우
-
스택의 추상적 자료구조 구현
- 배열을 이용하여 구현
- python 리스트와 메서드 이용
- 연결 리스트 이용
- 지난 시간이 이용한 양방향 연결리스트 이용
- 배열을 이용하여 구현
- 연산의 정의
- size() 현재 스택에 들어 있는 데이트의 원소를 구함
- isEmpty() - 현재 스택이 비어 있는 지를 판단
- push(x) - 데이터 원소 x를 스택에 추가
- pop() - 스택의 맨 위에 저장된 데이터 원소를 제거 + 반환
- 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]
LinkedListStack:
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
class LinkedListStack:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size() == 0
def push(self, item):
node = Node(item)
self.data.insertAt(self.size() + 1, node)
def pop(self):
return self.data.popAt(self.size())
def peek(self):
return self.data.getAt(self.size()).data
라이브러리 사용
from pythonds.basic.stack import Stack
S = Stack()
dir(s)
## 하면 이미 정의되어있는 라이브러리가 나옴
실습문제 - 수식의 괄호 유효성 검사
- 알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서:
- 여는 괄호 - ( 또는 { 또는 [ 를 만나면 스택에 푸시
- 닫는 괄호 - ] - } -) 를 만나면
- 스택이 비어있으면 올바르지 않은 수식
- 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사
- 맞지 않으면 올바르지 않은 수식
- 끝까지 검사한 후 , 스택이 비어 있어야 올바른 수식
def solution(expr):
match = {
')': '(',
'}': '{',
']': '['
}
S = ArrayStack()
for c in expr:
if c in '({[':
S.push(c)
elif c in match:
if S.size() < :
return False
else:
t = S.pop()
if t != match[c]:
return False
return S.isEmpty()
12강. 스택의 응용 수식의 후위 표기법
- 중위 표기법과 후위 표기법
- 중위 표기법 - 연산자가 피연산자들의 사이에 위치
- 후위 표기법 - 연산자가 피연산자들의 뒤에 위치
중위 표현식 -> 후위 표현식
- A * B + C
- A출력
- 연산자 집어넣고
- B출력
- 연산자 우선순위. 스택 안에 있는 *가 우선순위가 높으니 pop() 한다
- 그리고 +을 스택에 넣는다
- C를 출력
- 수식의 끝에 왔으므로, 스택 안에 있는 연산 pop
- A + B * C
- A출력
- 연산자 집어 넣고
- B출력
-
- 이 스택 안 +보다 우선순위가 높으므로
- *도 스택에 넣고
- C 출력
- 수식의 끝에 왔으므로 스택 안에 있는 연산 pop
이렇게 중위 표현식을 왼쪽부터 오른쪽으로 스캔하면서 스택을 이용해서 연산의 우선순위 지켜가며 변환 가능
연산자가 동일한 경우
- A + B + C
- 우선순위가 같을 떄에도
- 스택에 들어잇는걸 먼저 스택에서 pop한 뒤
- 다시 스택에 +를 넣는다.
괄호처리
- 중위 : (A+B) * C
- 후위 : AB+C*
- 여는 괄호는 스택에 Push
-
닫는 괄호를 만나면 여는 괄호가 나올 떄까지 pop
- A*(B+C)
-
ABC+*
- 연산자를 만났을 떄, 여는 괄호 너머까지 pop하지 않도록
- 여는 괄호의 우선순위는 가장 낮게 설정
예제 손으로 써보기
직접 손으로 쓸 수 있어야 바꿀 수 있다는 건 문제를 풀면서 내 스스로도 공감한 내용
- 중위 : (A+B) * (C+D)
-
후위 : AB+CD+*
- 중위 : (A+(B-C)) *D
-
후위 : ABC-+D*
- 중위 : A*(B-(C+D))
- 후위 :ABCD+-*
알고리즘의 설계 - 이게 제일 중요
- 연산자의 우선순위 설정
prec = {
'*' :3,'/':3,
'+':2,'-':2,
'(':1
}
- 중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 그냥 출력
- ’(‘ 이면 스택에 Push
- ’)’ 이면 ‘(‘이 나올 때까지 스택에서 pop, 출력
- 연산자이면 스택에서 이보다 높(거나 같)은 우선순위의 것들을 pop, 출력
- 그리고 이 연산자는 스택에 push
- 스택엔 남아 있는 연산자는 모두 pop, 출력
코드의 구현 - 힌트
- 스택의 맨 위에 연산자와의 우선순위 비교
- 스택의
peek()
연산 이용
- 스택의
- 스택에 남아 있는 연산자 모두 모두 ()하는 순환문
while not opStack.isEmpty()
실습문제 답안
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]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
result = ""
for x in S:
if x == '(':
opStack.push(x)
elif x == ')':
while(opStack.peek() != '('):
result += opStack.pop()
opStack.pop() # 스택 안 '(' 처리해주기
elif x in '*/+-':
if(not opStack.isEmpty() and prec[opStack.peek()] >= prec[x]):
result += opStack.pop()
opStack.push(x)
else:
result += x
while not opStack.isEmpty():
result += opStack.pop()
return result
S = "A+B+C"
print(solution(S))
13. 스택의 후위 표기 수식 계산
- 중위 표기법 : 연산자가 피연산자들의 사이에 위치
- 후위 표기법 : 연산자가 피연산자들의 뒤에 위치
후위 표기식의 계산
-
AB+CD+*
- 피연산자이므로 스택에 A를 집어넣는다.
- B를 집어 넣는다
- B를 스택에서 pop하고 A를 pop해서 덧셈 연산 적용
- 이를 다시 스택에 넣는다
- C,D 푸시
- C,D + 연산 해주고 (-,/경우 나중 pop한 피연산자가 앞에 와야한다.) 연산 결과 푸시
- 스택에 pop해서 두개 곱해주고 다시 스택 push
- 마지막에 도달하였으므로, 이 원소를 pop 해내면 된다.
알고리즘의 설계
- 후위표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 스택에 push
- 연산자를 만나면 스택에서 pop -> (1), 또 pop->(2)
- (2) 연산 (1)을 계산, 이 결과를 스택에 push
- 수식의 끝에 도달하면 스택에서 pop -> 이것이 계산 결과
실제 수가 들어있는 수를 처리_ 연습문제 설명
- 수식의 문자열을 각각의 수와 기호로 분리해서 리스트로 만드는 작업 필요
def splitTokens(exprStr):
tokens = []
val = 0
valProcessing = False
for c in exprStr:
if c == ' ';
continue
if c in '0123456789':
val = val*10+int(c)
valProcesssing = True
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False
tokens.append(c)
if valProcessing:
tokens.append(val)
return tokens
-
inficToPostfix는 지난 번에는 문자열, 이번에는 splittokens라는 함수의 결과로 괄호면, 괄호, 연산자면 연산자, 수면 수로 하나씩 끊어서 리스트로 바꿈
- 중위 표현식을 splitTokens를 통해 리스트에 저장
- 토큰스에 저장되어있는 순서를 후위표현식으로 변환
- postfixEval로 계산해서 이 식의 결과를 리턴
실습 문제
- 주의할 점
- 문자가 아닌 숫자를 int형으로 변환해주었기 때문에, “*+/-“ 안에서 in 연산자를 사용할 수 없어. 비교 자체가 불가 ->
requires string as left operand, not int
- 하지만 리스트에 담아서 비교해주면 비교 가능 x in [‘*’, ‘/’, ‘+’, ‘-‘]
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 splitTokens(exprStr):
tokens = []
val = 0
valProcessing = False
for c in exprStr:
if c == ' ':
continue
if c in '0123456789':
val = val * 10 + int(c)
valProcessing = True
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False
tokens.append(c)
if valProcessing:
tokens.append(val)
return tokens
def infixToPostfix(tokenList):
prec = {
'*': 3,
'/': 3,
'+': 2,
'-': 2,
'(': 1,
}
opStack = ArrayStack()
postfixList = []
for x in tokenList:
if x == '(':
opStack.push(x)
elif x == ')':
while(opStack.peek() != '('):
postfixList.append(opStack.pop())
opStack.pop() # 스택 안 '(' 처리해주기
elif x in ['*', '/', '+', '-']:
if(not opStack.isEmpty() and prec[opStack.peek()] >= prec[x]):
postfixList.append(opStack.pop())
opStack.push(x)
else:
postfixList.append(x)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return postfixList
def postfixEval(tokenList):
opStack = ArrayStack()
result = 0
operators = {
'*': lambda x, y: y*x,
'/': lambda x, y: y//x,
'+': lambda x, y: y+x,
'-': lambda x, y: y-x,
}
for x in tokenList:
if x in operators.keys() and opStack.size() >= 2:
A = opStack.pop()
B = opStack.pop()
result = operators[x](A, B)
opStack.push(result)
else:
opStack.push(x)
return opStack.pop()
def solution(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val
testCase = "7*(9-(3+2))"
tokens = splitTokens(testCase)
postfix = infixToPostfix(tokens)
print(postfix)
print(postfixEval(postfix))
14강 큐
- 자료를 보관할 수 있는 (선형)구조
- 단 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
- enqueue 연산
- 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음
- dequeue 연산
-
선입선출(FIFO) 특징을 가지는 선형 자료구조
-
큐의 동작
-
큐의 추상적 자료구조 구현
- 배열을 이용하여 구현
- python 리스트와 메서드들을 이용
- 연결리스트를 이용하여 구현
- 양방향 연결리스트 이용
- 배열을 이용하여 구현
- 연산의 정의
- size() 데이터 원소의 수
- isEmpty()
- enqueue(x)
- dequeue() 제거 + 반환
- peek()
배열로 구현한 큐
스택과 다른 점
def dequeue(self):
return self.data.pop(0)
def peek(self):
return self.data[0]
- 배열로 구현한 큐의 연산 복잡도
- dequeue()는 O(n) 나머지는 다 O(1)
이중 연결리스트로 큐를 구현
- 이게 이번 실습문제
- 이중 연결리스트 중 어떤 것을 활용하면 편할까 ?
라이브러리
from pythonds.basic.queue import Queue
Q = Queue()
dir(Q)
self.data.getLength() self.data.getLength() == 0 self.data.getAt(1).data
실습 답안
이게 왜 안되지 한참 고민했는데 enqueue와 dequeue를 반대로 생각했었다. 앞에서 들어가고 끝에서 나간다. 헷갈리지 말자
class LinkedListQueue:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size()==0
def enqueue(self, item):
node = Node(item)
self.data.insertAt(1,node)
def dequeue(self):
return self.data.popAt(self.size())
def peek(self):
return self.data.getAt(self.size()).data
15강 환형큐
큐의 활용 : 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronusly) 일어나는 경우
- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
- 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우
- 환형 큐(Circular Queue) : 정해진 개수의 저장 공간을 빙 돌려가며 이용
- 데이터를 넣는 곳 rear
- 데이터를 꺼내는 곳 front
- 정해진 개수의 저장 공간을 빙 돌려가며 이용
- 큐가 가득차면 ? 더이상 원소를 넣을 수 없음. 큐의 길이를 기억하고 있어야
환형 큐의 추상적 자료구조 구현
- 연산의 정의 지난 번에 isFull() 이란 연산을 정의해서, 큐에 데이터 원소가 꽉 차있는 지를 판단.
- 배열로 구현한 환형 큐
- 정해진 길이 n의 리스트를 확보해둔다.
배열로 구현한 환형큐
class CircularQueue:
def __init__(self,n):
self.maxCount = n
self.data =[None]*n
self.count = 0
self.front = -1
self.rear = -1
def size(self): # 현재 큐 길이를 반환
return self.count
def isEmpty(self)
return self.count == 0
def isFull(self):
return self.count == self.maxCount
def enqueue(self,x):
if self.isFull(): # 큐에 데이터 원소 추가
# IndexError('Queue full') exception으로 처리
self.rear = [ 빈칸 ]
self.data[self.rear] = x
self.count +=
def dequeue(self):
if [ 빈칸 ]: # 큐에서 데이터 원소 뽑아내기
raise IndexError('Queue empty')
self.front = [ 빈칸 ]
x = [빈 칸 ]
self.count -= 1
return
def peek(self):
if [ 빈칸 ]: # 큐의 맨 앞 원소 들여다보기
raise IndexError('Queue empty')
return [ 빈 칸 ]
답안
1. (self.rear+1)%self.maxCount
2. self.isEmpty()
3. (self.front+1)%self.maxCount
4. self.data[self.front]
5. self.data[(self.front+1)%self.maxCount]
16장 우선순위 큐
큐가 FIFO (First-in First-out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
- 예를 들어 enqueue로 6,7,3,2 삽입해도
- 우선 순위에 따라 dequeue하게 되면 2,3,6,7과 같이 나오게 되는 큐를 말한다.
우선순위 큐의 활용
- 운영체제의 CPU 스케줄러
우선순위 큐의 구현
- 서로 달든 두 가지 방식이 가능하다
- Enqueue할 때 우선순위 순서를 유지하도록
- Dequeue할 때 우선순위 높은 것을 선택
- 어느 것이 더 유리? Enqueue가 조금 더 유리하다.
-
Dequeue할 때, 우선순위가 가장 높은 걸 선택하려면, 모든 데이터 원소를 다 찾아봐야 한다. 하지만 Queue는 우선순위가 높은 대로 설정이 되어 있기 때문에, 적절한 위치를 바로 찾을 수 있다.
- 서로 다른 두 가지 재료 이용 가능
- (1) 선형 배열
- (2) 연결리스트
- 어느 것이 더 유리하까?
- 시간적으로는 연결리스트가 유리. 중간에 데이터 원소를 삽입해야 하는 일이 빈번하게 발생할텐데, 선형배열을 사용하면, 중간에 원소 삽입시 원소를 밀어줘야 하기 때문에 속도가 느려진다
- 메모리 공간 측면에서는 선형 배열이 더 효율적일 것이다.
우선순위 큐의 초기화
from doublylinkedlist import Node, DoublyLinkedList
class PrioirtyQueue:
def __init__(self,x): # 양방향 연결리스트를 이용하여 빈 큐를 초기화
self.queue = DoublyLinkedList()
실습문제
맨처음 빈칸 처음 시작할 때 어디서 시작해야 하는가 while조건 하나 끝까지 가지 않았을 조건, 또 다른 빈칸 -> 우선순위가 높은 것 마지막 -> inser어쩌구의 메소드를 적어서 알맞은 호출로 채우면 된다.
- 주의 : 양방향 연결리스트의 getAt( ) 메서드를 이용하지 않음.
- getAt()을 이용하면 그 위치까지 칸을 세서 간다.
class PriorityQueue:
def __init__(self):
self.queue = DoublyLinkedList()
def size(self):
return self.queue.getLength()
def isEmpty(self):
return self.size() == 0
def enqueue(self, x):
newNode = Node(x)
curr = self.queue.head
while curr.next.data != None and x < curr.next.data:
curr = curr.next
self.queue.insertAfter(curr, newNode)
def dequeue(self):
return self.queue.popAt(self.queue.getLength())
def peek(self):
return self.queue.getAt(self.queue.getLength()).data
def solution(x):
return 0
참고자료 [파이썬_자료구조_알고리즘]https://programmers.co.kr/learn/courses/57