[Do it! 알고리즘 코딩테스트 with C++] 3장. 탐색

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 3장. 탐색

3-1. 깊이 우선 탐색
3-2. 너비 우선 탐색
3-3. 이진 탐색

---

📌 3-1. 깊이 우선 탐색

* 깊이 우선 탐색
- 시작 노드에서 출발해서 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 다시 탐색을 수행하는 알고리즘
- 기능: 그래프 완전 탐색
- 특징: LIFO, 재귀 함수로 구현 or 스택 자료구조 이용
- 시간 복잡도: O(V+E)

* 깊이 우선 탐색 동작 원리
1. 그래프를 인접 리스트로 표현
2. 방문 배열 초기화, 시작 노드 선택
3. 방문 배열 체크 후 인접 노드 중 미방문 노드 탐색 - 재귀 or 스택 활용
4. 탐색 순서 기록

---

📌 3-2. 너비 우선 탐색

* 너비 우선 탐색
- 시작 노드에서 출발해서 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색을 수행하는 알고리즘
- 기능: 그래프 완전 탐색
- 특징: FIFO, 큐 자료구조 이용
- 시간 복잡도: O(V+E)

* 너비 우선 탐색 동작 원리
1. 그래프를 인접 리스트로 표현
2. 방문 배열 초기화, 시작 노드 선택
3. 방문 배열 체크 후 인접 노드 중 미방문 노드 탐색 - 큐 활용
4. 탐색 순서 기록

---

📌 3-3. 이진 탐색

* 이진 탐색
- 정렬된 데이터에서 원하는 값을 찾아내는 알고리즘
- 기능: 타깃 데이터 검색
- 특징: 중앙값 비교를 통한 데이터 대상 축소 방식
- 시간 복잡도: O(logN)

* 이진 탐색 동작 원리
1. 현재 데이터셋의 중앙값을 선택
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋 선택
4. 1~3번을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

---