Do it 알고리즘 코딩테스트 하루코딩 5장 탐색 이론

# 14 깊이우선탐색(DFS)

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

 

기능	특징	시간복잡도
그래프 완전탐색	LIFO 재귀함수 또는 Stack으로 구현	O(V+E)

 

 // 재귀함수 구현시 스택 오버 플로우 유의

A{

   A();

}

 

응용 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬

 

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

원본 그래프, 인접 리스트로 그래프 표현, 방문배열 1에 T, 스택에 1

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접노드를 스택에 삽입

 

3. 스택에 값이 없을 때까지 반복

이미 다녀간 노드는 재방문X

 

pop() 하면서 탐색 순서에 기록,

인접 노드를 방문 배열에서 체크후 push()

 

# 15 너비우선탐색 BFS

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

 

기능	특징	시간복잡도
그래프 완전 탐색	FIFO Queue	O(V+E)

 

응용 최단경로

 

1. BFS를 시작할 노드를 정한후 사용할 자료구조 초기화

원본 그래프, 인접 리스트로 그래프 표현, 방문배열 1에 T, 큐에 1

 

2. 큐에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 큐에 삽입

 

3. 큐에 값이 없을 때까지 반복

이미 다녀간 노드는 재방문X

 

poll()하면서 탐색 순서에 기록,

인접노드를 방문 배열에서 체크후 add()

 

# 16 이진 탐색 (Binary Search)

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

대상 데이터의 중앙값과 찾고자 하는 값을 비교해서 데이터의 범위를 절반으로 줄이면서 찾는다.

 

기능	특징	시간복잡도
타겟 데이터 탐색	중앙값 비교를 통한 축소 방식	O(logN)

 

조건

정렬되어 있는 상태

과정

1. 현재 데이터셋의 중앙값 median을 선택

2. 비교 하여 찾고자하는 데이터 < 중앙값이면 오른쪽 버리고 왼쪽 선택

3. 비교 하여 찾고자하는 데이터 > 중앙값이면 왼쪽 버리고 오른쪽 선택

3. 2, 3과정 반복하여 찾고자하는 데이터 == 중앙값 이면 종료