알고리즘 문제
list[-1] 의 경우 리스트가 비어있으면 에러가 난다.
if not stack:
stack.append('No')
elif stack[-1] == '(':
stack.pop()
두개의 순서를 바꿔서 실행하니 해결됨.큐 Queue
First In First Out
먼저 온 자료가 먼저 나감
deque 은 양쪽 모두 in, out이 가능하기 때문에 스택과 큐를 모두 구현할 수 있음.
따라서 코드 구현 시에도 deque 이용.
from collections import deque # 으로 덱을 가져와야 함.
queue = deque() #큐를 생성
queue.append() #원소를 추가
queue.popleft() #가장 먼저 온 원소를 빼내기 위해 왼쪽에서 pop힙 Heap
우선 순위 큐: 우선 순위가 가장 높은 자료가 가장 먼저 꺼내지는 자료 구조 → heap을 이용해 구현
힙: 가장 큰 원소를 찾는데 최적화된 형태의 이진 트리 (직접 구현 X 내장됨)
규칙:
- 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상 → 따라서 root 는 트리에서 가장 큰 원소가 된다.
- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 하고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져있어야 함
최대 힙 (Max Heap): 루트 노드 - 가장 큰 값
최소 힙 (Min Heap): 루트 노드 - 가장 작은 값
힙에서 삭제하는 법 - 루트 노드를 삭제하고 마지막 노드를 루트 노드의 위치로 이동한 후 값을 비교하면서 자리를 바꾸고 확정.
import heapq
#배열을 선언해줌
pq = [4, 1, 2]
#heapify는 평범한 배열을 힙으로 만들어주는 함수
heapq.heapify(pq) #하면 [1, 2, 4] 또는 [1, 4, 2]가 된다
heapq.heappush(pq, 3) #하면 [1, 2, 3, 4] 가 됨
heapq.heappop(pq) # 하면 가장 작은 원소가 나오면서 삭제됨. [2, 3, 4]
#가장 작은 항목을 삭제하지 않고 보려면
pq[0] #으로 확인하여야 함.
# 파이썬에서는 default가 최소힙.
# 최대힙으로 쓰려면 원소에 -를 붙여서 사용한다.
#최대힙 예시: 1,2,3 중에 가장 큰 값을 찾으려면
pq =[]
heapq.heappush(pq, -1)
heapq.heappush(pq, -2)
heapq.heappush(pq, -3)
# 그러면 [-3, -2, -1]
print(-heapq.heappop(pq)) # -3에 다시 -를 붙여 나오면서 최댓값이 됨.
발전 중...