탐색 알고리즘

1. 선형 탐색

• 배열 처럼 요소가 직선 모양으로 늘어선 자료구조에서 순회하는 것을 말한다.
• 순차적으로 요소를 방문하기 때문에 순차검색이라고도 한다.
• 시간 복잡도: o(n)

2. 이분 탐색(binary search)

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식
• 시간 복잡도: o(logN)
• 알고리즘

  • 우선 정렬을 해야 함
    left right로 mid값 설정
    mid와 내가 구하고자 하는 값과 비교
    구할 값이 mid보다 높으면: left = mid + 1, 구할 값이 mid 보다 낮으면 right = mid -1
    left > right가 될 때까지 계속 반복하기

3. 깊이 우선 탐색(Depth First Search)

DFS 개념

• 루트 노드(혹은 다른 임의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
• 갈 수 있는데까지 계속 진행하다가 더이상 진행할 수 없으면 뒤로 돌아와 다시 탐색한다. 
  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 탐색을 진행하는 방법과 유사하다.
  • 그래프에서 모든 노드를 방문하고자 할 때 더 선호되는 편이다.

DFS 특징

• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
  • 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• 깊이 우선 탐색은 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 가지고 있다.

DFS의 과정

1. 그래프의 시작 노드에서 출발하여 먼저 시작 노드 v를 방문하고 방문하였다고 표시한다.
2. v에 인접한 노드들 중에서 아직 방문하지 않은 노드 u를 선택한다.
3. 만약 그러한 노드가 없다면 탐색은 종료한다.
4. 만약 아직 방문하지 않은 노드 u가 있다면 u를 시작 노드로 하여 깊이 우선 탐색을 다시 시작한다.
5. 이 탐색이 끝나게 되면 다시 v에 인접한 노드들 중에서 아직 방문이 안 된 노드를 찾는다.
6. 없을 경우 종료하고, 있다면 다시 그 노드를 시작 노드로 하여 깊이 우선 탐색을 다시 시작한다. 

DFS 구현 방법

• 재귀함수 또는 스택(방문한 노드들을 스택에 저장하였다가 다시 꺼내어 작업하는 것)을 통해 구현한다.
• 모든 경로를 방문해야 할 경우에 적합

DFS 시간 복잡도(V: 정점, E: 간선)

• 인접 행렬: O(V^2)
• 인접 리스트: O(V+E)

4. 너비 우선 탐색(Breadth First Search)

BFS 개념

• 너비 우선 탐색(Breadth First Search)은 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법이다.
• 한 정점에서 갈 수 있는 곳을 동시에 가면서 탐색한다.
  • 예를 들어, a 노드에서 시작한다고 했을 때, BFS는 a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

BFS 특징

• BFS는 DFS와 달리 재귀적으로 동작하지 않는다.
• BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 큐(queue)를 사용한다.

BFS 과정

1. 먼저 시작 노드인 0을 방문한 다음, 큐에 삽입한다.
2. 노드 0의 인접 노드인 {1,2,4}를 차례대로 방문한 다음, 큐에 삽입한다.
3. 큐에 삽입된 {1,2,4} 순으로 큐에서 삭제하면서 인접한 노드에 방문 가능한지 확인한다. 
4. {1}의 인접한 노드 {0,2}는 이미 방문했으므로 큐에서 삭제한다.
5. {2}의 인접한 노드 {1,0,3,4}에서 방문하지 않는 {3}을 방문한 후 큐에서 삭제한다.
6. 앞의 순서와 마찬가지로 모든 노드를 방문하고, 탐색을 종료한다.

BFS 구현 방법

구현 방법으로는 자료 구조 큐(queue)를 이용하는 것이다.