파이썬자료구조(11-16)스택-우선순위큐

강의

목차

  1. 스택
  2. 수식의 후위 표기법
  3. 후위 표기 수식 계산
  4. 환형 큐
  5. 우선 순위 큐

11. 스택

이제부터 살펴볼 자료구조 특정한 종류의 문제를 풀기 위한 알고리즘을 위해 구현되는 자료구조들

스택 : 자료를 보관할 수 있는 선형 구조 넣을 때에는 한 쪽 끝에서 밀어넣어야 하고 -> push 꺼낼 때에는 같은 쪽에서 꺼내야 하는 제약이 있음 -> pop

  • 후입 선출 (LIFO) 특징을 가지는 선형 자료구조

  • 스택의 동작
  • 스택에서 발생하는 오류

    • 비어있는 스택에서 데이터 원소를 꺼내려 할 때 -> 스택 언더플로우
    • 꽉 찬 스택에 데이터 원소를 넣으려 할 때 -> 스택 오버 플로우
  • 스택의 추상적 자료구조 구현

    1. 배열을 이용하여 구현
      • python 리스트와 메서드 이용
    2. 연결 리스트 이용
      • 지난 시간이 이용한 양방향 연결리스트 이용
  • 연산의 정의
    • 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
  1. A출력
  2. 연산자 집어넣고
  3. B출력
  4. 연산자 우선순위. 스택 안에 있는 *가 우선순위가 높으니 pop() 한다
  5. 그리고 +을 스택에 넣는다
  6. C를 출력
  7. 수식의 끝에 왔으므로, 스택 안에 있는 연산 pop
  • A + B * C
  1. A출력
  2. 연산자 집어 넣고
  3. B출력
    • 이 스택 안 +보다 우선순위가 높으므로
  4. *도 스택에 넣고
  5. C 출력
  6. 수식의 끝에 왔으므로 스택 안에 있는 연산 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

0%