항해99-17기 4일차 TIL
- 백준 2164. 카드2 - https://www.acmicpc.net/problem/2164
(강의 내용에 포함된 문제이다. )
- leetcode 225. 큐를 이용한 스택 구현 - https://leetcode.com/problems/implement-stack-using-queues/ - <파이썬 알고리즘 인터뷰> (이하 책) 255p.
- leetcode 232. 스택을 이용한 큐 구현 - https://leetcode.com/problems/implement-queue-using-stacks/ - 책 257p.
- leetcode 622. 원형 큐 디자인 - https://leetcode.com/problems/design-circular-queue/ - 책 259p.
- 백준 1966. 프린터 큐 - https://www.acmicpc.net/problem/1966
오늘 발표를 맡은 과제는 leetcode 232. 스택을 이용한 큐 구현, 백준 1966. 프린터 큐 이다.
오늘의 강의 내용과 문제는 큐에 관한 내용이다.
# 큐 (Queue)
큐(Queue)는,
FIFO의 처리 구조를 가지며, 데크(Deque)나 우선순위 큐(Priority Queue) 같은 변형들이 유용하게 쓰인다.
너비 우선 탐색(Breadth-First Search - BFS)이나 캐시 등을 구현할 때도 널리 사용된다.
또한 파이썬의 리스트는 큐의 모든 연산을 지원한다. 다만 더 나은 성능을 위해서는 O(n)의 시간 복잡도를 갖는 리스트 보다
O(1)의 시간 복잡도를 가지는 데크(collections.deque)를 사용하는 편이 좋다.
# 연결 리스트를 통한 큐 ADT 구현
클래스로 Node를 정의해서 포인터로 연결하여 큐를 구현할 수 있다.
아래는 큐의 구조를 구현한 연결 리스트 코드이다.
class Node:
def __init__(self, val):
self.val = val
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def push(self, val):
node = Node(val)
if not self.head:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def pop(self):
if not self.head:
return None
node = self.head
self.head = self.head.next
return node.val
def isEmpty(self):
return not self.head
push를 통해 tail에 값이 추가되는 방식이고,
pop을 사용했을 때, head를 반환함으로써 FIFO를 구현한다.
2164. 카드 2
from. 백준
6이라는 수가 주어진다고 하면,
- [ 1, 2, 3, 4, 5, 6 ]
맨 앞 제거 - [ 2, 3, 4, 5, 6 ]
맨 앞 맨 뒤로 - [ 3, 4, 5, 6, 2 ]
맨 앞 제거 - [ 4, 5, 6, 2 ]
맨 앞 맨 뒤로 - [ 5, 6, 2, 4 ]
... ...
이처럼 반복을 거쳐, 마지막에 남는 수를 구하는 것이다.
# 2164. 풀이
from collections import deque
num = int(input())
def test_problem_queue(num):
deq = deque([i for i in range(1, num + 1)])
while len(deq) > 1:
deq.popleft()
deq.append(deq.popleft())
return deq.popleft()
print(test_problem_queue(num))
num은 boj 문제의 케이스 입력을 받는 input()이다.
deq에 deque를 할당하는데 값은 1부터 num + 1 이전까지의 숫자이다.
데크의 길이가 1보다 크면, 즉 2개 이상일 때 기준으로 반복을 실행한다.
popleft를 사용해 가장 앞쪽 값을 삭제하고, append(popleft())를 통해 맨 앞의 값을 맨 뒤로 옮긴다.
반복문을 탈출하게 되면 deq의 popleft()를 리턴한다. (이때 deq에는 단 하나의 값이 남아 있다. - pop()을 사용해도 무관하다.)
큐의 사용을 이해하기 좋은 간단한 문제였다.
232. - Implement Queue using Stacks
from. leetcode
크롬에 내장된 영한 번역을 사용했다.
오역이 다소 있다.
# 232. 풀이
class MyQueue:
def __init__(self):
self.top = []
def push(self, x: int) -> None:
self.top.append(x)
def pop(self) -> int:
return self.top.pop(0)
def peek(self) -> int:
self.top.append(self.top[0])
return self.top.pop()
def empty(self) -> bool:
return self.top == []
리스트로 큐의 FIFO 구조를 구현했다.
push의 경우 동일하게 작용하는 append를 이용했고,
pop은 pop(0)으로 데크의 popleft처럼 가장 앞쪽 값이 나가게끔 하였다.
# 232. 책 - 풀이
1966. - 프린터 큐
from. 백준(img)
크
# 1966. 풀이
아래는 나의 풀이이다.
참
