탐색(Search)

탐색이란?

• 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘.
• 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요.

깊이 우선 탐색(Depth First Search)

• 그래프 완전 탐색 기법 중 하나.

• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여
  다시 탐색을 수행하는 알고리즘.

• 재귀 함수로 구현.

• 스택 자료구조 이용.

• 시간 복잡도: O(V+E) V는 노드수, E는 엣지 수

• 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야함.

• 사용처: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등

  핵심 이론

  • 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요함.
  1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화.
  2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기.
  3. 스택 자료구조에 값이 없을 때까지 반복하기.

너비 우선 탐색(Breadth First Search)

• 그래프 완전 탐색 기법 중 하나.

• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.

• Queue 자료구조 이용

• 시간 복잡도: O(V+E) V는 노드수, E는 엣지 수

• 가까운 노드를 우선하여 탐색하므로, 목표 노드에 도착하는 경로가 여러 개 일때 최단 경로를 보장.

  핵심 이론

  1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화.
  2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기.
  3. 큐 자료구조에 값이 없을 때까지 반복하기.

이진 탐색(Binary Search)

• 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘.

• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음.

• 시간 복잡도 : O(nlogn)

  이진 탐색 과정

  1. 현재 데이터셋의 중앙값(median)을 선택한다.
  2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
  3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
  4. 과정 i~iii 를 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.