[데이터구조] 스택, 큐, 해싱

스택, 큐, 해싱

  1. 스택,큐의 개념

  2. 스택, 큐의 의미

  3. 해싱

지난시간 요약
이번과정의 목표 : 목적 달성을 위한 연산 횟수를 줄이는 자료구조 디자인.
연산횟수를 줄이면 장땡인가? 이번과정에서는 YES. (반드시 그런 것은 아님.)

주문 처리 시스템 (1주차 문제)

  • 링크드 리스트

    • removeOrder : 리스트에서 따라가면서 지운다? 시간이 너무 오래걸림.

      • 해결 : 딕셔너리를 사용하면 Order ID로 원소를 바로 알 수 있음.

      • 입력값 : Order ID

      • 예) d[ orderiD = 182214 ] = 3

    -   문제 : 182214를 지우는것은 가능한데, 링크드 리스트의 특성상 앞의 원소를 뒤의 원소와 연결을 시켜줘야 함. (BUT 이전의 노드를 모름)

        -   Doubly LinkedList

        -   설명 : 182214의 앞과 뒤를 모두 저장하는 포인터를 만듬.

        -   장점 : add랑 remove는 많고 조회가 별로 없을 경우에 성능이 좋음.

        -   단점 : add랑 remove가 적고 조회가 많은 경우 성능이 나쁨. (getOrder의 속도가 매우 느림)

            -   왜? : 리스트는 연속된 값을 읽는데 매우 빠름. 반면 링크드 리스트는 연속된 값을 읽는데 매우 느림. 보고 따라가고 보고 따라가기 떄문.
  1. 스택, 큐의 개념

    대표적인 기초 자료구조

  • 스택(STACK) : Last in First Out

  • 큐(QUEUE) : First in First Out

  • 트리(TREE)

  • 그래프(Graph)

PUSH : 스택에 자료를 넣음.
POP : 스택에서 자료를 꺼냄.
예) push(1) push(2) pop() push(3) pop() pop()

  • 스택 : 2 3 1 나중에 들어온 순서대로 나옴

  • 큐 : 1 2 3 들어간 순서대로 나옴

  1. 스택, 큐의 의미

    • 스택, 큐는 어디에 쓰이는가?

      • 스택, 큐는 자료구조. 그렇다면 무슨 자료를 저장하는가?

      • 상태(Status)를 저장함.

        • 스택은 상태의 의존관계가 생길때. A라는 일을 마치기 위해서 B라는 일을 먼저 끝내야 함. (재귀호출로 이어짐)

        • 큐는 상태의 의존관계가 없을때. A와 B가 서로 관련이 없지만 모두 하기는 해야할 때. (스케쥴링, 병렬화)

```
# 클래스 스택 구현하기 
class Stack:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        스택 myStack을 만듭니다.
        '''
        self.myData = []

    def push(self, n) :
        '''
        stack에 정수 n을 넣습니다.
        '''
        self.myData.append(n)


    def pop(self) :
        '''
        stack에서 가장 위에 있는 정수를 제거합니다. 만약 stack에 아무 원소가 없다면 아무 일도 하지 않습니다.
        '''
        self.myData = self.myData[:-1] # self.myData.pop()


    def size(self) :
        '''
        stack에 들어 있는 정수의 개수를 return 합니다.
        '''
        return len(self.myData)

    def empty(self) :
        '''
        stack이 비어있다면 1, 아니면 0을 return 합니다.
        '''
        if len(self.myData) == 0:
            return 1
        else:
            return 0

    def top(self) :
        '''
        stack의 가장 위에 있는 정수를 return 합니다. 만약 stack에 들어있는 값이 없을 경우에는 -1을 return 합니다.
        '''
        if len(self.myData) == 0:
            return -1 
        else:
            return self.myData[-1]


def main():
    stack = Stack()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''
    stack.push(1)
    stack.push(2)
    stack.pop()
    stack.push(4)
    stack.pop()

    print(stack.size()) 
    print(stack.top())
    print(stack.empty())

if __name__ == "__main__":
    main()

```
문제1 : 큐 규현하기 

큐 구현하기
이번 예제에서는 정수를 저장하는 Queue 클래스를 구현합니다.

Queue 클래스 내부의 함수를 모두 구현하시고 아래의 예제를 테스트해보세요.

완벽하게 동작한다고 생각되시면 제출을 눌러 점수를 확인해보세요!
class Queue:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        큐 myQueue을 만듭니다.
        '''
        self.data = []

    def push(self, n) :
        '''
        queue에 정수 n을 넣습니다.
        '''
        self.data.append(n)

    def pop(self) :
        '''
        queue에서 가장 앞에 있는 정수를 제거합니다. 만약 queue에 들어있는 값이 없을 경우에는 아무 일도 하지 않습니다. 
        '''
        if len(self.data) == 0:
            pass
        else:
            self.data = self.data[1:]

    def size(self) :
        '''
        queue에 들어 있는 정수의 개수를 return 합니다.
        '''
        return len(self.data)

    def empty(self) :
        '''
        queue이 비어있다면 1, 아니면 0을 return 합니다.
        '''
        if len(self.data) == 0:
            return 1
        else:
            return 0

    def front(self) :
        '''
        queue의 가장 앞에 있는 정수를 return 합니다. 만약 queue에 들어있는 값이 없을 경우에는 -1을 return 합니다.
        '''
        if len(self.data) == 0:
            return -1
        else:
            return self.data[0]

    def back(self) :
        '''
        queue의 가장 뒤에 있는 정수를 return 합니다. 만약 queue에 들어있는 값이 없을 경우에는 -1을 return 합니다.
        '''
        if len(self.data) == 0:
            return -1
        else:
            return self.data[-1]




def main():
    queue = Queue()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''
    queue.push(1)
    queue.push(2)
    queue.pop()
    queue.push(4)
    queue.pop()

    print(queue.size()) 
    print(queue.front())
    print(queue.empty()) 

if __name__ == "__main__":
    main()
문제2 : 계산 순서 정하기 

계산 순서 정하기
이번 문제에서는 괄호가 포함된 수식p이 있을 때, 어느 괄호부터 계산해야 하는지를 구해봅니다.

괄호 쌍이 주어질 때, 각 괄호가 몇 번째로 계산되어야 하는 괄호인지를 출력하는 findOrder(p)를 작성하세요.

[입력값] 괄호 p가 주어집니다. 괄호 p는 항상 올바른 괄호라고 가정해도 좋습니다. 즉, ‘)(‘이나 ‘())’ 과 같은 입력은 주어지지 않습니다.

[결과값] 각 괄호가 몇 번째로 계산되어야 하는 괄호인지를 출력합니다.
def findOrder(p) :
    '''
    괄호 p가 주어질 때, 각 괄호가 몇 번째로 계산되어야 하는 괄호인지를 list로 반환합니다.

    예를 들어, p='(()())' 일 경우, [3, 1, 1, 2, 2, 3] 을 반환합니다.
    '''

    result = [0] * len(p) # [0, 0, 0, 0, 0, 0]
    stack = []
    cnt = 1

    for i in range(len(p)) : # range(6) : 0 ~ 5로 저장
        if p[i] == '(' : # (가 들어오면 stack에 저장.
            stack.append(i) # (가 저장되어있는 순서를 기록.
        else :
            result[i] = cnt # )가 들어오면 )가 몇번째인지 기록. 그게 cnt이고 i번째 result에 cnt값 저장
            result[stack.pop()] = cnt # stack.pop()을 하면 가장 마지막의 (의 위치가 출력되도록.
            cnt += 1

    return result

def main():
    '''
    Do not change this code
    '''

    p = input()
    print(*findOrder(p))

if __name__ == "__main__":
    main()
처음에 위의 아이디어를 생각 못했음. stack을 사용할 것은 같았으나 stack = []를 하나 더 만들어서
'(' 만을 저장하고 ')'가 들어오면 result에서 i번째에 cnt값을 저장하고, stack에 '('을 저장한 후 가장 마지막 '('의 위치를 출력하도록. 

문제3 : 주문 처리하기

processOrder(orders) 함수는 사용자가 입력한 주문 정보 orders가 처리되는 순서를 리스트로 반환합니다.

주문 정보는 orderInfo 클래스를 통해 사용됩니다.

일반 주문보다 VIP 고객의 주문의 우선순위가 높습니다.예를 들어 3분이 걸리는 일반 주문과 4분이 걸리는 VIP 주문이 있을 경우에는 4분이 걸리는 VIP 주문을 먼저 처리한 후 3분이 걸리는 일반 주문을 처리합니다.

주문을 처리하고 있는 도중에 어떠한 주문이 들어오더라도 하던 일을 끝내고 다음 주문을 처리합니다.

[입력값] 〔1〕 n: 주문의 수
〔2~〕 a b c
a: 고객이 방문하는 시간
b: 주문을 처리하기 위해 걸리는 시간
c: VIP 여부 (0: 일반, 1: VIP)
(a 순으로 정렬되어 입력, 동일한 시간에 2개이상의 주문은 없다고 가정)

[결과값] 주문이 처리되는 순서를 출력합니다. 먼저 처리되는 주문 번호를 먼저 출력하도록 합니다.
# 못풀었으니 다시 풀어봐야 함. 
class orderInfo:
    '''
    이 부분은 수정하지 마세요.
    '''
    def __init__(self, t, d, v):
        self.time = t
        self.duration = d
        self.vip = v

def selectQueue(orders, VIP, non_VIP, time):
    if len(VIP) == 0 and len(non_VIP) > 0:
        return non_VIP 
    elif len(non_VIP) == 0 and len(VIP) > 0:
        return VIP
    else:
        if time < orders[VIP[0]].time and time < orders[non_VIP[0]].time:
            if orders[VIP[0]].time <= orders[non_VIP[0]].time:
                return VIP
            elif orders[VIP[0]].time > orders[non_VIP[0]].time :
                return non_VIP
            else:
                return -1 
        else:
            if orders[VIP[0]].time <= time:
                return VIP
            elif orders[non_VIP[0]].time <= time:
                return non_VIP
            else:
                return -1            


def processOrder(orders) :
    '''
    주문 정보가 주어질 때, 주문이 처리되는 순서를 출력합니다.
    '''
    if len(orders)==0:
        return 0

    result = []
    time = 0
    VIP = []
    non_VIP = []

    for i in range(len(orders)):
        if orders[i].vip==1:
            VIP.append(i)
        else:
            non_VIP.append(i)
    while not (len(VIP)==0 and len(non_VIP)==0):
        which = selectQueue(orders, VIP, non_VIP, time)
        idx = which.pop(0)
        time = max(time, orders[idx].time) + orders[idx].duration
        result.append(idx+1)
    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    p = int(input())

    orders = []

    for i in range(p) :
        myList = [int(v) for v in input().split()]

        orders.append(orderInfo(myList[0], myList[1], myList[2]))

    print(*processOrder(orders))

if __name__ == "__main__":
    main()

댓글(0)

Designed by JB FACTORY