728x90
함께 푼 문제
스택
- 후입선출(LIFO)
- 깊이 우선 탐색에 효과적
- 후입선출 개념은 재귀 함수 알고리즘 원리와 일맥상통함
satck = []
#삽입
stack.append(1)
stack.append(2)
stack.append(3)
#제거
stack.pop() #3 #후입선출
큐
- 선입선출(FIFO)
- 넓이 우선 탐색에서 자주 사용
from collections import deque
queue = deque()
#삽입
queue.append(1)
queue.append(2)
queue.append(3)
#제거
queue.popleft() #1 선입선출
- popleft는 제일 왼쪽에 있는걸 삭제한 뒤 빈공간을 채우기 위해 뒤쪽에 있는 요소들을 한칸씩 왼쪽으로 땡겨야한다. 따라서 list로 구현하면 시간복잡도가 크기 때문에 deque를 사용하여 큐를 구현한다.
파이썬 우선순위 큐 사용법
선언
from queue import PriorityQueue
Q = PriorityQueue()
삽입
Q.put(5)
Q.put(2)
Q.put(3)
- 숫자가 작은 것이 앞에 저장된다.
제거
Q.get() #2
Q.get() #3
Q.get() #5
- 우선순위큐는 일반 큐와 다르게 append, pop을 사용하지 않고 put, get을 사용한다.
정렬 기준 적용
삽입
Q.put((1, -6)) # (우선순위, 값)
Q.put((3, 3))
Q.put((2, 2))
Q.put((1, 1))
- (우선순위, 값) 형태로 삽입할 수 있다.
- 우선순위를 나타내는 수가 작을수록 앞에 저장된다. (숫자가 작을수록 우선순위가 크다.)
- 우선순위가 같은 경우 값이 작을수록 앞에 저장된다.
제거
while not Q.empty():
print(Q.get()[1])
#-6
#1
#2
#3
- Q.get()을 할 경우 (1, -6) 형태로 출력된다. 값만 출력하고 싶은 경우 Q.get()[1]을 하면 값만 출력된다.
반응형
'알고리즘 > Do it! 알고리즘 코딩테스트 (파이썬)' 카테고리의 다른 글
[9일차] 05 탐색 : 05-3 이진 탐색 (1) | 2024.04.01 |
---|---|
[8일차] 05 탐색 : 05-1 깊이 우선 탐색, 05-2 넓이 우선 탐색 (0) | 2024.04.01 |
[7일차] 04 정렬 : 04-5 병합 정렬, 04-6 기수 정렬 (1) | 2024.04.01 |
[6일차] 04 정렬 : 04-3 삽입 정렬, 04-4 퀵 정렬 (0) | 2024.04.01 |
[5일차] 04 정렬 : 04-1 버블 정렬, 04-2 선택 정렬 (0) | 2024.03.24 |