T I L / 6월 16일

stack

스택과 큐 둘 다 선형 자료구조이며, 스택은 후입선출(Last In Fisrt Out)구조다. 나중에 들어간 것이 가장 빨리 나온다. 원소가 탑 처럼 쌓인다고 상상하면 된다.

Queue

파이썬에서 큐 쓸 때 :

from collections import deque

큐는 기본적으로 선입선출(First In Fist Out)의 구조를 띄고 있고, 요즘 BFS 풀 때 활용하고 있다.

DFS / BFS 비교

DFS (깊이우선탐색) : 모든 노드를 방문하고자 할 때 이 자료구조를 사용한다. 재귀 함수를 사용해서 구현하며 그래서 무한루프에 빠지지 않게 주의해야 한다. 그래서 어떤 노드에 방문했는지 꼭 알고 있어야 한다. 모든 경우의 수를 탐색하기 때문에 너비우선탐색보다 시간이 오래 걸린다.

BFS (너비우선탐색) : 시작 노드부터 가까운 곳부터 탐색한다. 주로 최단 경로를 찾을 때 사용한다. 시작점 부터 그 다음 스탭으로 점점 나아가는 구조이기 때문에, 큐를 활용하기도 한다.

article

• 재능과 반복