스택이란?
위의 그림 처럼 후입선출로
간단하게 생각 하면
책과 너비가 같은 박스에 책을 넣는 방식이라고 생각하면 좋을거같다
큐 란?
스택과 다르게 선입선출로 먼저 들어온 자료가 먼저 나가는 형식이다.
롤에서 랭크 게임을 매칭할 때 "큐를 돌린다"라고 표현하죠. 게임 시작 버튼을 먼저 누른 사람이 먼저 게임을 할 수 있도록 처리해줍니다. 큐는 이처럼 요청이 들어온 순서대로 일을 처리할 때 사용합니다.
그래프 탐색이란
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
- Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
- 쉽게말해 하나하나 다 살펴보는것이다.*완전탐색
깊이 우선 탐색(DFS, Depth-First Search)
깊이 우선 탐색이란
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
- 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.