위 책을 토대로 궁금한 점을 추가 리서치 후 기술하였다.
스택
LIFO (Last In, First Out)
기존의 리스트 자료구조와 같지 않나 생각이 들었다. 하지만, python에서는 대체로 collections.deque 라이브러리를 이용해 구현했다. 그 이유가 궁금했다.
Q. 리스트 vs 배열
- 리스트: 적은 요소
- 배열: 매우 큰 요소를 저장하거나 수학적 연산이 필요할 경우
arr (배열) | list (리스트) | |
선언 필요성 | O | X |
값 정의 | array.module, numpy | 대괄호로 감싸주기만 하면 됨 |
사칙연산 | 쉬움 | 어려움 |
데이터 크기 (자료형?) | 같아야함 | X, 리스트 중첩 가능 |
Q. 리스트 vs 덱
- deque (덱): Double Ended Queue
deque (덱) | list (리스트) | |
양방향에서 삽입과 삭제가 일어나는 자료구조 | random access에 최적화된 자료구조 | |
데이터 삽입 / 삭제 (자료 양끝 한정) |
O(1) |
O(N) 지우고 나서, 한칸씩 앞으로 당겨주는 연산 |
인덱싱 | O(N) | O(1) 고정된 사이즈의 메모리를 가지므로 |
슬라이싱 | X | O |
기타 | maxlen 설정으로 오히려 메모리 오버 사용될 될 수도 있음 | 만약 stack 용도로 쓴다면 당겨주는 연산이 불필요해서 deque 보다 빠름 |
collections.deque 를 이용해 심플하게 예외 처리하기
실습코드
그 외 꿀팁
- stack; top >= bottom 등 pop, push 할 때 규칙; 말로 혹은 그림으로 정리해봐도 좋을 듯
- 고민; 언제 stack 구조를 써야할까?
- 세로로 쌓고 빼는 그림이 이해하기 쉬움
큐
FIFO (Firt In, First Out); 은행창구 대기, 스프링글스 통, 뱀의 움직임
- (dequeue) < front < (enqueue) < rear; 가로로 쌓고 빼는 그림이 이해하기 쉬움
- 배열, 링버퍼 (나머지 연산자 % 사용 주의) 등으로 구현 가능하지만, deque 모듈 권장
- stack과 사용법은 동일하되, append, popleft 메소드를 사용해서 단방향으로 추가 및 제거
Q. collections.deque vs queue.Queue 모듈 차이점?
- collections.deque : 단일 쓰레드 환경
- queue.Queue
우선순위 큐
우선 3가지 자료구조가 자칫 비슷해보일 수 있을 것 같아 차이점을 명시해보았다.
자료구조 | 삭제되는 요소 |
스택(Stack) | 가장 최근에 들어온 데이터 |
큐 (Queue) | 가장 먼저 들어온 데이터 |
우선순위큐 (Priority Queue) | 가장 우선순위가 높은 데이터 |
- 우선순위와 함께 인큐 / 디큐할 때 우선순위가 높은 데이터를 꺼내는 방식
- 구현 시 heapq 모듈 사용; hea은 완전이진트리 구조이므로 삽입&삭제 연산을 위해 h=log(n+1) 시간만 들이면 된다.
- priority queue (thread-safe) vs heapq(non-safe); thread-safe 검증을 위해 시간이 더 걸리므로
그럼 heap은 무엇인가?
- 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조
- 완전이진트리이면서 (최대힙) key(root) ≥ key(child), (최소힙) key(root) ≤ key(child)
- 작동 원리 실습, 우선은 heapq 이용하기
위 특성을 응용해 우선순위큐를 구현할 수 있다.
[실습코드 in 백준]
https://www.acmicpc.net/source/82681827
'2️⃣ 개발 지식 B+ > 코딩 테스트' 카테고리의 다른 글
[백준/python] DP 유형 - 배낭(Knapsack) 문제 (0) | 2024.08.26 |
---|---|
[백준/python] DP 유형 - LIS & LDS 그리고 LCS (0) | 2024.08.26 |
[백준/python] stack 유형 모음집 및 접근 컨셉 (0) | 2024.08.21 |
[알고리즘/python] 위상정렬 (0) | 2024.08.19 |
코테 시간초과 분석 방법 (0) | 2024.08.14 |