1. DFS(깊이 우선 탐색)
'탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동해 다시 탐색하는 알고리즘'
DFS(Depth-First Search), 깊이 우선 탐색은 그래프를 '완전' 탐색할 때 활용된다. 즉, 그래프의 모든 정점을 방문하는 데 사용되는 알고리즘이다. 주로 Recursion 및 Stack 자료 구조를 활용하여 구현하며, 시간복잡도는 O(V+E)로 표현된다.
**노드 수 = V, 에지 수 = E
DFS는 대부분 재귀 함수를 이용하여 구현하기 때문에, Stack Overflow를 조심해야 한다. 이는 특정 함수가 계속 자신을 호출하여 계속 재귀적으로 함수가 호출되는 현상을 말한다.
DFS는 보통 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에서 주로 활용된다.
DFS 핵심이론
DFS는 한 번 방문한 노드를 다시 방문하면 안 되기 때문에, 노드 방문여부를 체크할 배열이 필요하다. 보통 처음에 ArrayList로 그래프를 표현하고, 이 방문 배열을 초기화한 후에 DFS 구현을 시작한다. 방문한 노드는 방문배열에 체크하여 다시 꼭 방문하지 않도록 설정해주어야 한다.
2. BFS(너비 우선 탐색)
'시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘'
BFS(Breadth-First Search), 너비 우선 탐색 또한 그래프를 완전 탐색하는 알고리즘 방법이다. FIFO 탐색을 시행하며, 이를 바탕으로 Queue 자료구조를 주로 사용하여 구현한다. 시간복잡도는 동일하게 O(V+E)이다. 목표 노드에 도착하는 경로가 여러 개일때 최단 경로를 보장한다.
- BFS가 최단 경로를 보장하는 이유
BFS 핵심이론
DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않아야 하기에 방문배열이 필요하다. 또한 그래프를 ArrayList로 구현하는 것 또한 동일하다. 구현 방식은 다음과 같다
- 시작할 노드 정하고, 사용할 자료구조 초기화
- Queue에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 Queue에 삽입(방문 배열 체크, 꺼낸 노드 탐색 순서 기록)
- Queue에 남은 노드가 없을때 까지 반복
3. Binary Search(이진 탐색)
'대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 알고리즘'
이진 탐색은 앞의 두 가지 그래프 완전 탐색과는 다른, 타깃 데이터를 탐색하는, 정렬된 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 시간 복잡도는 O(logN)이다.
이진 탐색 핵심 이론
이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.
이진 탐색은 꼭 '데이터가 정렬되있어야 한다는 점'을 기억해야 한다.
