[코딩테스트/ Python] 자료구조

thingzoo·2023년 4월 10일
0

코딩테스트

목록 보기
2/3
post-thumbnail

스택(Stack)

  • FILO(First In, Last Out) 구조를 띄고 있는 자료구조로, 삽입과 삭제 연산이 동일한 한군데에서 발생
  • 삽입과 삭제 연산에 있어 시간복잡도가 O(1)
  • 이전에 활용한 데이터를 역으로 추적하거나, 나중에 들어온 데이터가 빨리 나가야할때 사용
  • Python에서는 LifoQueue라는 구현체가 있으나, List의 pop을 활용하면 스택처럼 사용 가능

큐(Queue)

  • FIFO(First In, First Out) 구조를 띄고 있는 자료구조로, 삽입과 삭제 연산이 서로 다른 곳에서 발생
  • 삽입과 삭제 연산에 있어 시간복잡도가 O(1)
  • 맨 앞을 front, 맨 뒤를 rear, 삽입 연산을 enqueue, 삭제 연산을 dequeue라고 함
  • 주로 순차적으로 진행되는 일을 스케쥴링할때 사용
  • Python에는 Queue가 있으나, 효율성 측면에서 주로 deque를 사용

큐의 구현

List 😵

  • 끝 원소 삭제 : O(1)
  • 임의의 원소 삭제: O(n) - 삭제후 모든 원소를 이동시켜야함
    👉🏻 그러니 리스트로 큐처럼 사용하지 말것!
list = []
list.append(x) # 데이터 추가: O(1)
list.pop(0)    # 데이터 삭제: O(n)

Queue 😔

  • 데이터 추가/삭제: O(1)
  • 인덱스 접근 불가
  • 멀티스레드 환경에 최적화되어있음
from queue import Queue
q = Queue()
q.put(x) 
q.get()  # 데이터 추가/삭제: O(1)

deque 🤩

  • 큐와 스택의 구조를 합친 자료구조로 양쪽에서 삽입과 삭제 가능
  • 데이터 추가/삭제: O(1)
  • 인덱스 접근 가능
    👉🏻 코딩테스트 환경에서는 덱을 쓰는것이 적합
from collections import deque
q = deque([0])
q.appendleft(1); q.append(2)
q.popleft();     q.pop()     # 데이터 추가/삭제: O(1)
q.rotate(1)  # q.appendleft(q.pop())
q.rotate(-1) # q.append(q.popleft())

PriorityQueue

  • 데이터 추가/삭제: O(log n)
  • 기본 정렬은 첫번째 요소에 대한 오름차순
from queue import PriorityQueue
pq = PriorityQueue(maxsize=8) # 데이터 추가/삭제: O(logn)
pq.put(4)
pq.put(1) 
pq.put(7) 
pq.put(3)
print(que.get())  # 1 (기본: 오름차순)
que.put((3, 'A')) # 순위 직접 집어넣기(첫번째요소로 정렬)
que.put((1, 'B'))
que.put((2, 'C'))
print(que.get()[1])  # B
print(que.get()[1])  # C
print(que.get()[1])  # A

Reference

🔗 https://github.com/VSFe/Algorithm_Study

profile
공부한 내용은 바로바로 기록하자!

0개의 댓글