큐(Queue)는 FIFO구조로 먼저 집어넣은 데이터를 가장 먼저 뺄 수 있는 데이터 구조이다.
나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념이다. 덱(Deque)은 양쪽 끝에서 삽입과 삭제가
모두 가능한 자료구조인데, 큐와 스택을 합친 형태라고 생각하면 쉽다. 아래 코드는 큐 코드 예시이다.
큐 구현 문제(10845번 큐)
import sys
class Queue():
def __init__(self):
self.li = []
def push(self, n):
self.li.append(n)
def pop(self):
print(self.li.pop(0) if self.li else -1)
def size(self):
print(len(self.li))
def empty(self):
print(0 if self.li else 1)
def front(self):
print(self.li[0] if self.li else -1)
def back(self):
print(self.li[-1] if self.li else -1)
queue = Queue()
for _ in range(int(sys.stdin.readline())):
s = sys.stdin.readline().split()
if s[0] == "push":
queue.push(int(s[1]))
elif s[0] == "pop":
queue.pop()
elif s[0] == "size":
queue.size()
elif s[0] == "empty":
queue.empty()
elif s[0] == "front":
queue.front()
elif s[0] == "back":
queue.back()
백준 알고리즘 문제 풀이)
백준 알고리즘 10845번 큐(python)
기본적인 큐 문제이다. sys.stdin.readline을 사용하지 않으면 시간 초과가 나온다. import sys class Queue(): def __init__(self): self.li = [] def push(self, n): self.li.append(n) def pop(self): print(se..
jinho-study.tistory.com
백준 알고리즘 10866번 덱(python)
기본적인 덱(Deque) 문제이다. sys.stdin.readline을 사용하지 않으면 시간 초과가 나온다. import sys class Deque(): def __init__(self): self.li = [] def push_front(self, n): self.li.insert(0, n) def pus..
jinho-study.tistory.com
백준 알고리즘 11866번 요세푸스 문제 0(python)
기본적인 큐 문제이다. 순환큐! N, K = map(int, input().split()) queue = [i for i in range(1, N+1)] res = [] for _ in range(N): for i in range(K-1): queue.append(queue.pop(0)) res.append(queue.pop(0))..
jinho-study.tistory.com
백준 알고리즘 2164번 카드2(python)
기본적인 큐 문제이다. 그냥 리스트로 큐를 구현해서 풀려고 하면 시간 초과가 나와서 collections.deque를 사용해서 풀었다. collections모듈 안의 deque가 CPython으로 구성되어 있어서 그런지 속도면에
jinho-study.tistory.com
백준 알고리즘 1966번 프린터 큐(python)
숫자들이 담긴 큐와, 인덱스들이 담긴 리스트를 같이 사용해서 풀어야 하는 문제이다. from collections import deque for _ in range(int(input())): N, M = map(int, input().split()) queue = deque(map(int, i..
jinho-study.tistory.com
백준 알고리즘 1158번 요세푸스 문제(python)
순환큐 문제이다. 11866번 요세푸스 문제 0과 같은 문제이다. 11866번은 그냥 리스트로 큐를 구현해서 풀어도 맞았었는데 이 문제는 시간초과가 나와서 속도가 매우 빠른 collections.deque를 사용했다.
jinho-study.tistory.com
백준 알고리즘 18258번 큐 2(python)
큐 문제이다. 10845번 큐와 같은 문제이다. 이 문제는 collections.deque와 sys.stdin.readline을 사용해서 풀지 않으면 시간 초과가 나온다. 주의하자. import sys from collections import deque class Queue():..
jinho-study.tistory.com
백준 알고리즘 12789번 도키도키 간식드리미(python)
스택과 큐를 둘 다 사용해야 되는 문제이다. from collections import deque N = int(input()) queue = deque(map(int, input().split())) stack = deque() i = 1 while queue: if queue and queue[0] == i: queue..
jinho-study.tistory.com
백준 알고리즘 15828번 Router(python)
기본적인 큐 문제이다. import sys from collections import deque N = int(sys.stdin.readline()) queue = deque() while 1: n = int(sys.stdin.readline()) if n == -1: break if n != 0 and len(queue) < N: qu..
jinho-study.tistory.com
백준 알고리즘 1021번 회전하는 큐(python)
기본적인 덱 문제이다. from collections import deque N, M = map(int, input().split()) li = list(map(int, input().split())) queue = deque(range(1, N+1)) cnt = 0 for n in li: while queue[0] != n: t = q..
jinho-study.tistory.com
백준 알고리즘 2161번 카드1(python)
기본적인 덱 문제이다. 2164 카드2와 거의 동일한 문제이다. from collections import deque N = int(input()) queue = deque([i for i in range(1, N+1)]) while len(queue) > 1: print(queue.popleft(), end=' '..
jinho-study.tistory.com
백준 알고리즘 2346번 풍선 터뜨리기(python)
기본적인 덱 문제이다. 조금 더 쉽게 풀 수도 있을 것 같은 문제인데 연습 삼아 그냥 이런 식으로 풀어봤다. from collections import deque N = int(input()) li = [[n, i+1] for i, n in enumerate(map(int, inp..
jinho-study.tistory.com
백준 알고리즘 13417번 카드 문자열(python)
그리디 알고리즘 & 덱 문제이다. 덱의 맨 처음 값보다 t가 크다면 덱의 맨 뒤에 t를 추가, 그렇지 않다면 덱의 맨 앞에 t를 추가해주면 된다. from collections import deque for _ in range(int(input())): N = i..
jinho-study.tistory.com
백준 알고리즘 18115번 카드 놓기(python)
기본적인 덱 문제이다. 카드 방향 때문에 되게 헷갈리는 문제이다. 난이도에 비해 푸는데 시간이 오래 걸린 것 같다. from collections import deque N = int(input()) li = deque(map(int, input().split())) aft..
jinho-study.tistory.com
백준 알고리즘 20301번 반전 요세푸스(python)
구현 & 덱 문제이다. 요세푸스 문제에서 조금 진화한 버전인 것 같은데, 오른쪽으로 돌 때는 K-1번, 왼쪽으로 돌 때는 K번 돈다는 점만 이해하면 쉽게 풀 수 있다. PyPy3로 제출해야 시간 초과가 안
jinho-study.tistory.com
백준 알고리즘 5430번 AC(python)
덱 문제이다. 생각보다 쉽지 않은 문제였다. 런타임 에러에 주의해줘야 하고 시간도 빡빡하기 때문이다. 핵심은 R이 들어올 때마다 reverse 하면 안 된다는 점이다. 이것 때문에 계속 시간 초과가
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
|---|---|
| 깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함) (0) | 2021.03.10 |
| 스택(Stack) (백준 문제 포함) (0) | 2021.03.05 |
| 그리디(greedy) 알고리즘 (백준 문제 포함) (0) | 2021.01.29 |
| 이분 탐색(Binary Search) 백준 문제 포함 (0) | 2021.01.28 |