[Algorithm] 탐색

DFS: 깊이 우선 탐색

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

실제 구현 시 재귀함수를 이용하므로 스택오버 플로우(깊이가 너무 깊어질 때)에 유의해야한다. 

핵심: 한번 방문한 노드를 다시 방문하면 안된다 = 노드 방문 여부를 체크할 배열이 필요하다.

시간 복잡도: O(V+E) (노드 수: V, 간선 수: E)

1. 왼쪽 분기로 계속 들어가면서 Visit Array에 방문한 노드를 표기한다.
2. 왼쪽 분기가 존재하지 않는다면 이전 노드의 오른쪽 분기로 넘어간다.
3. 1,2 과정을 반복

 

BFS: 너비 우선 탐색

그래프의 시작노드에서 가장 가까운 노드로 탐색한다.

큐를 이용한 FIFO 방식을 활용하며 O(V+E)의 시간복잡도를 가진다.

Queue에 접근한 노드의 자식노드를 추가한다.

1. 0에 접근했을 때: Queue = [ 1, 2 ]
2. 1에 접근했을 때: Queue = [ 2. 3. 4 ]
3. 2에 접근했을 때: Queue = [ 3, 4, 5, 6 ] 
4. 3부터는 더 이상 추가할 노드가 없으므로 전부 탐색하면 된다.

 

Binary Search: 이진 탐색

데이터가 정렬된 상태에서 원하는 값을 찾는 알고리즘으로 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

O(logN)의 시간 복잡도를 가진다.

1. 정렬된 배열의 크기 10의 중간인 5에 접근한다.
2. 5를 기준으로 7이 더 크기 때문에 뒤쪽 절반의 중간인 8에 접근한다.
3. 8보다 작기 때문에 6,7에서 값을 찾는다.