[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 5장 탐색

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

5.1 깊이 우선 탐색 (DFS ; Depth First Search)

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

• 재귀함수로 구현
• 스택 자료구조 활용
• 단절점 찾기, 단절선 찾기,사이클 찾기,위상 정렬 등에 사용가능.

- 시간 복잡도 (노드 수 : v, 에지 수 : e) : O(v+e)
- 코드로 구현하기

void dfs(int v) 
{
	if (visited[v]) return;
	
	visited[v] = true;
	for (int i : arr[v]) if (visited[i] == false) dfs(i);
}

 
 

5.2 너비 우선 탐색 (BFS ; Breadth First Search)

-  그래프 완전 탐색 기법
- 그래프의 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드들을 먼저 방문하면서 탐색하는 알고리즘
- 특징

• FIFO 탐색
• queue 자료구조 이용
• 목표 노드에 도착하는 최단 경로 보장

- 시간복잡도 (노드 수 : v, 에지 수 : e) : O(v+e)
- 코드로 구현하기

void bfs(int s)
{
	queue<int> q;
	q.push(s);
	visited[s] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cout << now << " ";
		for (int i : arr[now]) {
			if (!visited[i]) {
				visited[i] = true;
				q.push(i);
			}
		}
	}
}

 
 

5.3 이진 탐색

- 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
- 시간 복잡도 : O(logN)
- 탐색 과정

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