스택(stack)
삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조
- LIFO(Last In Frist Out)
- 가장 마지막에 삽입된 데이터가 가장 먼저 나오는 구조
- 삽입과 삭제가 한쪽에서만 일어남
💡 파이썬 스택(stack) 연산
- s.append(n): top 위치에 새로운 데이터(n)를 삽입
- s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인
- s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산
큐(Queue)
삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조
- FIFO(First In First Out)
- 가장 먼저 삽입된 데이터가 가장 먼저 나오는 구조
- 삽입과 삭제가 양방향에서 이뤄짐
💡 파이썬 큐(queue) 연산
- s.append(n): rear 위치에 새로운 데이터(n)를 삽입
- s.popleft(): front 위치에 현재 있는 데이터를 삭제하고 확인
- s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인하는 연산
우선순위 큐(priority queue)
값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
- 큐 설정에 따라 front에는 항상 최댓값 또는 최솟값이 위치
- 일반적으로 트리 종류 중 하나인 힙(heap)을 이용해 구현
from queue import PriorityQueue💡 파이썬 우선순위 큐(priorityqueue) 연산
- q = PriorityQueue(maxsize=10): 비어있는 우선순위 큐를 초기화(maxsize: 최대 크기)
- q.put(n): 우선순위 큐에 데이터(n) 추가
- q.get(): 우선순위 큐에서 최솟값을 삭제한 뒤에 반환
힙(heap)
모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리
- 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본트리로 함
- 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙(기본)
- 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
- 키 값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 성립하지 않음
import heapq💡 파이썬 힙(heap) 연산
- heapq.heappush(heap, item): heap을 유지하면서 item을 heap에 추가
- heapq.heappop(heap): heap에서 최솟값을 삭제한 뒤에 반환
- heapq.heapify(arr): 값이 들어 있는 리스트를 힙으로 변환
스택 연산 수행 방법
- 현재 수열 값 >= 자연수이면 스택에 자연수를 append
- 현재 수열 값 < 자연수이면 pop 연산으로 스택에 있는 자연수를 꺼냄
n = int(input())
numlist = [int(input()) for _ in range(n)] # 수열을 이루는 n개의 수
answer = '' # push, pop 연산 과정
stack = []
i = 1
for num in numlist:
# num보다 작은 수는 모두 stack에 추가
while i <= num:
stack.append(i)
answer += '+'
i += 1
# 스택의 마지막 원소와 num이 같으면 pop
if stack and stack[-1] == num:
stack.pop()
answer += '-'
continue
# 스택에 수가 존재하면 불가능한 경우이므로 NO 출력
if stack:
print('NO')
else:
for a in answer:
print(a)
스택에 새로 들어오는 수(a)가 스택의 top에 존재하는 수(stack[-1][1])보다 크면 그 수는 오큰수
n = int(input())
A = list(map(int, input().split()))
nge = [-1 for _ in range(n)] # 오큰수를 저장할 배열
stack = []
for i, a in enumerate(A):
# 스택의 마지막 원소보다 a가 크면 pop 연산 및 오큰수 저장
while stack and stack[-1][1] < a:
idx, value = stack.pop()
nge[idx] = a
stack.append((i, a)) # (인덱스, 원소) 형식으로 추가
print(*nge)
- popleft(): 제일 위에 있는 카드를 버림
- rotate(-1): 남은 카드 중 제일 위에 있는 카드를 제일 밑으로 이동시킴
- 1개의 카드가 남을 때까지 위 과정을 반복
from collections import deque
n = int(input()) # n장의 카드
queue = deque([i for i in range(1, n+1)])
for _ in range(n-1):
queue.popleft() # 제일 위에 있는 카드를 버림
queue.rotate(-1) # 남은 카드 중 제일 위에 있는 카드를 제일 밑으로 이동
print(queue[0])
정렬은 기준은 절댓값이므로 단순히 힙만을 구현해서는 안됨
- 데이터 삽입: (절댓값, 실제값)
- 절댓값을 기준으로 오름차순 정렬할 수 있도록 해줌
- 절댓값이 같으면 음수가 먼저 위치하도록 정렬해주어야 함
import sys
import heapq
input = sys.stdin.readline
n = int(input()) # n장의 카드
heap = []
for _ in range(n):
x = int(input())
if x != 0: # x가 0이 아니면 (절댓값, 실제값)으로 추가
heapq.heappush(heap, (abs(x), x)) # 1. 절댓값 정렬 2. 같으면 실제값 기준 정렬
else: # x가 0이면 절댓값이 가장 작은 값을 출력
if heap:
print(heapq.heappop(heap)[1])
else: # 배열이 비여있으면 0을 출력
print(0)
반응형