공부하는허딩크 : https://www.youtube.com/live/Xx_DRXY3r2Q?feature=shared
<첫번째 시도 : 시간초과>
아직 deque라이브러리 공부하기 전 상태로 아래의 코드로 제출했더니 시간초과가 발생
list를 set으로 바꿔서 사용하여 시간초과를 해결해 보려고 했으나 불가능함
set은 기본적으로 remove(keyerror발생), discard, add를 활용할 수 있으나 반환값이 없어 아래 형식의 코드로 불가능
# 시간 초과 : Queue알고리즘을 사용해야 하나?
N = list(i for i in range(1, int(input()) + 1))
while len(N) > 1:
N.pop(0)
N.append(N.pop(0))
print(*N)
<두번째 시도 : 맞았습니다.>
deque라이브러리 활용.
import sys
from collections import deque
input = sys.stdin.readline
N = deque(i for i in range(1, int(input()) + 1))
while len(N) > 1:
N.popleft()
N.append(N.popleft())
print(*N)
※ Collections모듈에서 제공하는 deque 자료구조 (double-ended queue) : 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
큐는 FIFO (First In First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 방식입니다. 주로 대기열 시스템, 작업 스케줄링 등에서 사용됩니다.
1. 특징
- 양쪽 끝에서 삽입/삭제: deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입과 삭제를 할 수 있습니다. 이는 리스트의 경우 O(n) 시간이 걸리는 것과 큰 차이가 있습니다.
- 순서 유지: deque는 삽입된 순서대로 요소를 유지합니다. 따라서, 순서가 중요한 데이터 구조를 구축할 때 유용합니다.
- 고정 크기: deque는 고정 크기로 설정할 수 있지만, 기본적으로 크기에 제한이 없습니다.
2. 사용법
deque를 사용하기 위해서는 collections 모듈에서 import 해야 합니다.
from collections import deque
3. 기본 메서드
deque에서 자주 사용하는 메서드는 다음과 같습니다
1. 생성자:
d = deque() # 빈 deque 생성
d = deque([1, 2, 3]) # 초기값을 가진 deque 생성
2. 삽입:
append: 오른쪽 끝에 추가
d.append(4) # deque에 4 추가
appendleft: 왼쪽 끝에 추가
d.appendleft(0) # deque의 맨 앞에 0 추가
3. 삭제:
pop: 오른쪽 끝에서 제거
d.pop() # 맨 뒤의 요소 제거 및 반환
popleft: 왼쪽 끝에서 제거
d.popleft() # 맨 앞의 요소 제거 및 반환
4. 길이:
len: deque의 길이
length = len(d) # deque의 요소 개수
5. 확인:
in: 요소가 있는지 확인
if 1 in d: # 1이 deque에 있는지 확인
print("1 is in the deque")
4. 예제
아래는 deque를 사용하는 간단한 예제입니다:
from collections import deque
# 빈 deque 생성
d = deque()
# 요소 추가
d.append(1) # [1]
d.append(2) # [1, 2]
d.appendleft(0) # [0, 1, 2]
# 요소 제거
removed_item = d.pop() # [0, 1], removed_item = 2
removed_item_left = d.popleft() # [1], removed_item_left = 0
# 최종 상태 출력
print(d) # deque([1])
※ Python에서는 큐(Queue), 스택(Stack), 버퍼(Buffer)와 같은 데이터 구조를 구현하기 위해 다양한 내장 라이브러리와 모듈을 제공합니다. 아래에 각 데이터 구조를 구현하는 라이브러리 활용 방법을 설명하겠습니다.
1. 큐 (Queue)
Python에서는 queue 모듈을 사용하여 큐를 구현할 수 있습니다. 이 모듈은 스레드 안전성을 보장하는 큐를 제공합니다.
사용 예시
import queue
# 큐 생성
q = queue.Queue()
# 데이터 추가
q.put(1)
q.put(2)
q.put(3)
# 데이터 제거
print(q.get()) # 1
print(q.get()) # 2
# 큐 크기 확인
print(q.qsize()) # 1
다른 유형의 큐
queue 모듈은 다음과 같은 다른 유형의 큐도 제공합니다:
- 우선순위 큐: PriorityQueue
- FIFO 큐: Queue
- LIFO 큐: LifoQueue
우선순위 큐 예시
import queue
pq = queue.PriorityQueue()
# (우선순위, 데이터) 형식으로 추가
pq.put((2, 'second'))
pq.put((1, 'first'))
pq.put((3, 'third'))
# 우선순위에 따라 데이터 제거
print(pq.get()) # (1, 'first')
print(pq.get()) # (2, 'second')
2. 스택 (Stack)
Python에서는 스택을 구현하기 위한 전용 모듈은 없지만, 리스트를 사용하거나 collections 모듈의 deque를 사용하여 스택을 쉽게 구현할 수 있습니다.
리스트를 사용한 스택
# 리스트를 스택으로 사용
stack = []
# 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
# 데이터 제거
print(stack.pop()) # 3
print(stack.pop()) # 2
collections.deque를 사용한 스택
from collections import deque
stack = deque()
# 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
# 데이터 제거
print(stack.pop()) # 3
print(stack.pop()) # 2
3. 버퍼 (Buffer)
Python에는 기본적으로 버퍼를 위한 전용 모듈은 없지만, 리스트 또는 collections.deque를 사용하여 버퍼를 구현할 수 있습니다. 그러나, 입출력 관련 작업에 대한 버퍼는 io 모듈에서 사용할 수 있습니다.
io 모듈을 사용한 버퍼 예시
import io
# 메모리 버퍼 생성
buffer = io.BytesIO()
# 데이터 쓰기
buffer.write(b'Hello, World!')
# 버퍼의 시작으로 이동
buffer.seek(0)
# 데이터 읽기
print(buffer.read()) # b'Hello, World!'
요약
- 큐(Queue): queue 모듈을 사용하여 다양한 유형의 큐(기본 큐, 우선순위 큐, LIFO 큐 등)를 쉽게 구현할 수 있습니다.
- 스택(Stack): 리스트 또는 collections.deque를 사용하여 스택을 구현할 수 있습니다.
- 버퍼(Buffer): 데이터의 임시 저장을 위해 io 모듈을 사용하여 메모리 내의 버퍼를 구현할 수 있습니다.
이렇게 다양한 라이브러리를 활용하여 큐, 스택, 버퍼를 쉽게 구현하고 사용할 수 있습니다.
※ class구조 : Queue, Stack, Buffer
큐(Queue), 스택(Stack), 버퍼(Buffer)는 각각 데이터 구조를 다루는 방법입니다. 이들은 컴퓨터 과학에서 다양한 문제를 해결하는 데 사용됩니다. 각각의 구조에 대한 정의와 사용 방법을 아래에 자세히 설명하겠습니다.
1. 큐 (Queue)
정의
큐는 FIFO (First In First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 방식입니다. 주로 대기열 시스템, 작업 스케줄링 등에서 사용됩니다.
구현 방법
Python에서는 리스트를 사용하거나 collections 모듈의 deque를 사용할 수 있습니다. deque는 큐의 성능을 높이기 위해 양쪽 끝에서 빠른 삽입과 삭제를 지원합니다.
리스트를 사용한 큐 구현
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item) # 큐의 뒤쪽에 추가
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0) # 큐의 앞쪽에서 제거
else:
raise IndexError("dequeue from an empty queue")
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# 사용 예시
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 1
print(q.dequeue()) # 2
print(q.size()) # 1
deque를 사용한 큐 구현
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item) # 큐의 뒤쪽에 추가
def dequeue(self):
if not self.is_empty():
return self.queue.popleft() # 큐의 앞쪽에서 제거
else:
raise IndexError("dequeue from an empty queue")
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# 사용 예시
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 1
print(q.dequeue()) # 2
print(q.size()) # 1
2. 스택 (Stack)
정의
스택은 LIFO (Last In First Out) 구조로, 가장 최근에 들어온 데이터가 가장 먼저 나가는 방식입니다. 주로 재귀적 문제, 함수 호출 관리 등에서 사용됩니다.
구현 방법
스택은 리스트를 사용하여 간단히 구현할 수 있으며, append()와 pop() 메서드를 사용하여 데이터를 추가하고 제거할 수 있습니다.
리스트를 사용한 스택 구현
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item) # 스택의 꼭대기에 추가
def pop(self):
if not self.is_empty():
return self.stack.pop() # 스택의 꼭대기에서 제거
else:
raise IndexError("pop from an empty stack")
def peek(self):
if not self.is_empty():
return self.stack[-1] # 스택의 꼭대기 요소를 반환
else:
raise IndexError("peek from an empty stack")
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# 사용 예시
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop()) # 3
print(s.peek()) # 2
print(s.size()) # 2
3. 버퍼 (Buffer)
정의
버퍼는 데이터를 일시적으로 저장하는 용도로 사용되는 메모리 공간입니다. 일반적으로 입출력 작업에서 사용됩니다. 데이터를 일시적으로 저장하여 I/O 작업을 최적화하는 역할을 합니다.
구현 방법
버퍼는 다양한 방식으로 구현될 수 있습니다. 가장 간단한 예로는 리스트를 사용하여 데이터를 저장하고, 지정된 크기를 초과하면 데이터를 처리하는 방식을 사용할 수 있습니다.
버퍼 구현 예시
class Buffer:
def __init__(self, capacity):
self.capacity = capacity # 버퍼의 용량
self.buffer = []
def add(self, item):
if len(self.buffer) < self.capacity:
self.buffer.append(item) # 버퍼에 데이터 추가
else:
raise OverflowError("Buffer is full")
def process(self):
if not self.is_empty():
# 데이터를 처리하는 로직
item = self.buffer.pop(0) # FIFO 방식으로 데이터 처리
print(f"Processing item: {item}")
else:
print("Buffer is empty")
def is_empty(self):
return len(self.buffer) == 0
# 사용 예시
b = Buffer(capacity=3)
b.add(1)
b.add(2)
b.add(3)
b.process() # Processing item: 1
b.process() # Processing item: 2
b.add(4)
b.process() # Processing item: 3
요약
- 큐(Queue): FIFO 구조로 데이터를 처리하며, enqueue로 데이터를 추가하고 dequeue로 데이터를 제거합니다. deque를 사용하면 성능이 향상됩니다.
- 스택(Stack): LIFO 구조로 데이터를 처리하며, push로 데이터를 추가하고 pop으로 데이터를 제거합니다. peek 메서드를 통해 꼭대기 요소를 확인할 수 있습니다.
- 버퍼(Buffer): 데이터를 일시적으로 저장하는 용도로 사용되며, 입력 및 출력을 최적화하는 데 유용합니다. 데이터 추가 및 처리 방법을 정의하여 사용할 수 있습니다.
이러한 구조들은 다양한 알고리즘과 데이터 처리 문제에서 기본적인 도구로 사용됩니다.