deque

- 데크 (double-ended queue): 양 쪽에서 삽입 및 삭제 가능 - ADT는 이중연결리스트로 구현 641. design circular deque - 이중 연결 리스트로 구현(빈 head, tail) * 배열은 첫 인덱스에 삽입 시 O(n) - 우선순위 큐: 특정 조건에 따른 우선순위가 가장 높은 순으로 추출 (ex. 최댓값 추출) -> 정렬 알고리즘으로 구현 가능 - 다익스트라 알고리즘이나 힙 자료구조와 관련이 깊음 23. merge k sorted lists - 파이썬 heapq 모듈 (최소 힙): 이진 트리 기반 1. 원소들이 정렬된 상태(키 기준)로 삽입, 삭제 2. 가장 작은 원소가 첫 인덱스에 위치 3. 모든 원소들은 자식 원소들보다 작거나 같게 위치 * 두번째로 작은 값 확인하..
- 스택: lifo, 큐: fifo - 파이썬 리스트는 스택과 큐의 모든 연산 수행 가능 - 그러나 성능을 고려한다면 큐는 데크를 사용해야 좋음 - 스택 ADT에서는 차곡차곡 쌓이지만, 실제 연결리스트로 구현 시 무작위로 배치되고 포인터로 처리 ※ 참고: 클래스의 메소드에서 self는 인스턴스 자체, 인스턴스로 메소드 호출하면 자동으로 인스턴스(self) 인자로 넣음 20. valid parentheses - 딕셔너리 활용 - 스택에 왼 괄호 쌓기 316. remove duplicate letters - 재귀(분리 가능하냐로 접근) - 스택에 문자 쌓으면서 비교 - collections.Counter() 739. daily temperatures * [0] * len(T) - 스택에 인덱스 쌓으면서 온도..