Search.md

탐색

깊이 우선 탐색(DFS)

• 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없을 때 가장 최근 갈림길로 돌아와 다른 길을 선택하여 다시 진행하는 방법
• 가능한 모든 경로를 탐색
• 스택 또는 재귀함수(가장 보편적이고 코드가 짧음) 이용
• 시간 복잡도는 %O(V + E)$, V: 정점 수, E: 간선 수

DFS의 탐색 방법

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기
   • 인접 리스트로 그래프 표현하기
   • 방문 배열 초기화하기
   • 시작 노드 스택에 삽입하기
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
3. 스택 자료구조에 값이 없을 때까지 반복하기

너비 우선 탐색(BFS)

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법
• 큐를 이용하여 구현
• 재귀로 동작하지 않음

BFS의 탐색 방법

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   • 인접 리스트로 그래프 표현하기
   • 방문 배열 초기화하기
   • 시작 노드 큐에 삽입하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

이진 탐색

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

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

탐색 과정

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