탐색 알고리즘

탐색알고리즘은 배열에 대해 탐색하는 선형 탐색 알고리즘과 트리나 그래프에 대해 탐색 알고리즘이 있다.

 

선형 탐색알고리즘에 선형 탐색과 이진 탐색 방법이 있다

 

선형 탐색

 

선형 탐색 방식은 배열의 시작부터 마지막 요소까지 순차적으로 탐색하여 요소를 찾는 방식이고

 

선형탐색

 

이진 탐색

 

이진 탐색 방법은 정렬이 보장되어있는 배열에서 배열의 중간 위치에서 시작해 탐색 하려는 요소가 중간 위치의 요소보다 작으면 왼쪽, 크면 오른쪽을 탐색하는 방법으로 이 과정을 반복하며 찾는 방법이다. 이진 탐색의 시간 복잡도는 O(logN)만큼을 가진다.

 

이진탐색

 

트리/그래프 탐색 알고리즘에는 DFS, BFS 방식이 있는데

 

DFS

 

DFS는 깊이 우선 탐색으로 그래프에서 분기점이 있을 경우 모두 탐색 후 다음 분기 탐색하는 방식 가장 깊은 위치부터 탐색하여 재귀와 스택 방식을 이용하여 구현 할 수 있다 해당 분기점을 방문했는지 안 했는지에 대한 플래그를 가지게 된다.

 

# DFS 장/단점

• 장점
  • 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.
  • 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능)

 

BFS

 

BFS는 너비 우선 탐색으로 큐 방식을 사용하여 그래프에서 시작 위치부터 해당 노드를 큐에 넣고 제거하고 붙어있는 노드들 다시 큐에 집어넣어 가장 높은 위치부터 탐색하는 방식이다.

 

# BFS 장/단점

• 장점
  • 너비를 우선으로 탐색하므로 답이 되는 경로가 여러 개인 경우에도 최단경로를 얻을 수 있다.
  • 경로가 무한히 깊어져도 최단경로를 반드시 찾을 수 잇다.
  • 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.
• 단점
  • DFS와 달리 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다.

 

DFS/BFS