자료구조: 큐(Queue)

[Queue]

빨대에 element 넣는 거라 생각하면 됨

선입선출

 

List 구조 사용하기

[- ] list 자료구조는 무작위 접근에 최적화된 자료구조임.

     따라서, pop(x) 연산의 시간복잡도는 O(N)로 N이 커질수록 매우 느려짐.

     => queue 자료구조 구현시 list 자료구조 비추천

# list로 구현하기
queue = list()

# 요소 추가시 append(x)
queue.append(2)
queue.append(1)

# 삭제시 del list[index] or pop(index) or remove(element)
del queue[1]
queue.pop(0)

 

Deque

double-ended queue의 약자로 데이터를 양방향에서 추가 제거 가능한 자료구조임.

[+] popleft(), appendleft(x)의 시간복잡도는 O(1)로 list보다 성능이 뛰어남.

[- ] 무작위 접근의 시간복잡도가 O(N)이고 내부적으로 linked list를 사용하므로 N번째 데이터에 접근하기 위해서는 N번의 순회가 필요.

 

collections 모듈 사용

# 라이브러리로 구현
from collections import deque
queue = deque([1,2,3])

# 요소 추가시, append()
queue.append(5)

# 요소 맨 앞에 추가시, appendleft(element)
queue.appendleft(0)

# 왼쪽 요소 제거시 popleft()
queue.popleft()

참고하면 좋을 블로그

: https://velog.io/@nayoon-kim/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque

[파이썬] deque

 

Queue class 사용

데이터 추가와 삭제가 하나의 메서드로 처리됨.

deque와 성능이 같음.

[+] 데이터 추가/삭제는 O(1)

[- ] 데이터 접근은 O(N)

# 라이브러리로 구현, Queue(), LifoQueue(), PriorityQueue()
import queue
queue = queue.Queue()

# 요소 추가시 put()
queue.put(1)

# 제거시 get() : 한번에 한개씩 선입선출 제거
queue.get()

# queue 크기, 요소 개수 파악 시, qsize()
queue.qsize()

#----------------------------------
# LIFO 후입선출
import queue

queue = queue.LifoQueue()


#----------------------------------
# priority queue
queue = queue.PriorityQueue()

# (우선순위, 요소)로 전달
queue.put((5, 0))
queue.put((10, 1))

 

우선순위 큐

배열, 연결리스트, 힙으로 구현 가능.

그 중 힙으로 구현하는 것이 가장 효율적.

표 출처: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

 

백준 알고리즘: 2164번 (https://www.acmicpc.net/problem/2164)

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다. >> 첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

from collections import deque

N = int(input())
card_list = list(range(1,N+1))
card = deque(card_list)

for i in range(N):
    if len(card) == 1:
	    print(card[0])
    else:
        card.popleft()
        changed = card.popleft()
        card.append(changed)

 

 

오답노트

• input()한 결과는 string임. -> int로 바꿔줘야 함
• range(N)은 0부터 n-1까지 range보여줌
• 숫자만 나오게 하려면 list or deque에서 element만 나오게 해야함