👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.
1. 스택
스택은 삽입과 삭제 연산이 후입선출(리포 LIFO)로 이뤄지는 자료구조입니다.
삽입과 삭제가 한 쪽에서만 일어난다고 보시면 됩니다.
- top: 삽입과 삭제가 일어나는 위치를 뜻함
- s.append(data): top 위치에 새로운 데이터 삽입
- s.pop(): top 위치에 있는 데이터를 삭제하고 확인
- s[-1]: top 위치에 있는 현재 데이터를 단순 확인
스택은 깊이 우선 탐색(DFS), 백트래킹 유형의 문제에 효과적입니다.
그 이유는, LIFO는 그 개념 자체가 재귀 함수 알고리즘 원리와 동일하기 때문입니다.
직접 보여드리기 위해 재귀함수를 하나 만들어왔습니다.
예시 코드와 출력 결과를 보면, 처음 출력될때는 3, 2, 1, 0 으로 출력되지만 다시 재귀 함수 호출! 문구와 함께 출력되는 수는 0, 1, 2, 3 으로 거꾸로 출력되는걸 볼 수 있습니다.
2. 큐
큐는 삽입과 삭제 연산이 선입선출(피포 FIFO)로 이뤄지는 자료구조입니다.
스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다. 그래서 삽입과 삭제가 양방향에서 이뤄집니다.
deque() 를 이용하여 큐를 구현합니다.
- rear: 큐에서 가장 끝(최신) 데이터 영역
- front: 큐에서 가장 앞(예전) 데이터 영역
- s.append(data): rear 부분에 새로운 데이터를 삽입
- s.popleft(): front 부분에 있는 데이터를 삭제하고 확인
- s[0]: 큐의 맨 앞에 들어와 있는 데이터를 확인
이것도 코드로 한 번 확인해봅시다.
from collections import deque텍스트로 먼저 저희가 쓸 친구를 불러옵니다.
그 후에, 큐에 0~4까지 차곡차곡 쌓은뒤,
pop()으로 팝팝 쳐주니 오른쪽(front)에 있는 4를 퉤하고 뱉었습니다.
이어서 popleft()로 리버샷 팝팝하니까 왼쪽(rear)에 있는 0을 뱉어내는군요.
이것으로 큐는 선입선출 뿐만 아니라 양방향으로 값을 뱉어낼 수 있다는 사실을 알아냈습니다.
나중에 다룰 '우선순위 큐'
우선순위 큐는 값이 들어간 순서와 상고나 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.
큐 설정에 따라 front에 항상 max값, 또는 min값이 위치합니다.
우선순위 큐는 일반적으로 heap을 이용해 구현하는데, 이것은 트리 종류중 하나이므로 나중에 다뤄보겠습니다.
