탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘.
주어진 데이터의 성질(정렬/비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요.
실제 모든 코딩 테스트 문제의 기본이 되는 알고리즘.
깊이 우선 탐색 (DFS : Depth First Search)
완전 탐색 기법 중 하나.
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘.
- 특징 : 재귀 함수로 구현, 스택 자료구조 이용
- 시간 복잡도 : O(V + E), 노드수 V, 에지 수 E
스택으로 구현하는 것보다 재귀가 더 간단하다.
개념은 간단하다.
- 탐색을 시작할 노드를 설정하고 해당 노드와 인접한 노드를 계속해서 따라간다.
- 이때, 해당 노드를 탐색한 적이 있다면 지나친다.
재귀 함수로 구현하면 함수 호출 자체가 인접 노드 추적의 의미를 갖는다.
스택으로 구현하면 인접 노드를 추적하는 행위를 스택으로 관리해야 하기 때문에 스택이 상대적으로 복잡하다.
너비 우선 탐색 (BFS : Breadth First Search)
그래프를 완전 탐색하는 방법 중 하나.
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.
- 특징 : FIFO 탐색, Queue 자료구조 이용
- 시간 복잡도 : O(V + E), 노드수 : V, 에지 수 : E
DFS와 BFS 구현
/**
* Depth First Search (Recursive)
* @param lla 탐색 대상
* @param al 탐색 결과
* @param value 탐색 시작 노드
*/
public static void dfsRecursive(LinkedList<Integer>[] lla, ArrayList<Integer> al, int value) {
al.add(value); // 탐색한 노드 배열에 노드 추가
for (int i : lla[value]) { // 해당 노드에 인접한 노드 확인
if (al.contains(i) == false) dfsRecursive(lla, al, i); // 인접한 노드를 탐색한 적이 없다면 재귀 호출
}
}
/**
* Depth First Search (Stack)
* @param lla 탐색 대상
* @param value 탐색 시작 노드
*/
public static void dfsStack(LinkedList<Integer>[] lla, int value) {
ArrayList<Integer> al = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
stack.add(value); // 탐색 시작점이 되는 노드를 스택에 추가
while (stack.isEmpty() == false) { // 스택에 값이 없을때까지 반복
int node = stack.pop();
if (al.contains(node) == false) { // 스택에 저장된 노드를 탐색한 적이 없다면
al.add(node); // 해당 노드를 탐색한 노드 배열에 추가
for (int i : lla[node]) {
if (al.contains(i) == false) stack.add(i); // 스택에서 꺼낸 노드의 인접 노드를 스택에 추가
}
}
}
System.out.println(al.toString());
}
/**
* Breadth First Search 1
* @param lla 탐색 대상
* @param value 탐색 시작 노드
*/
public static void bfsQueue1(LinkedList<Integer>[] lla, int value) {
ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
ll.add(value);
while (ll.isEmpty() == false) {
int node = ll.pollFirst();
if (al.contains(node) == false) {
al.add(node);
for (int i : lla[node]) {
if (al.contains(i) == false) ll.add(i);
}
}
}
System.out.println(al.toString());
}
/**
* Breadth First Search 2
* @param lla 탐색 대상
* @param value 탐색 시작 노드
*/
public static void bfsQueue2(LinkedList<Integer>[] lla, int value) {
ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
al.add(value);
ll.add(value);
while (ll.isEmpty() == false) {
int node = ll.pollFirst();
for (int i : lla[node]) {
if (al.contains(i) == false) {
al.add(i);
ll.add(i);
}
}
}
System.out.println(al.toString());
}탐색 대상이 아래와 같을 때
- 1 -> 2, 3
- 2 -> 1, 5
- 3 -> 1, 4
- 4 -> 3, 5
- 5 -> 2, 4
결과는 아래와 같다
- dfsRecursive -> [3, 1, 2, 5, 4]
- dfsStack -> [3, 4, 5, 2, 1]
- bfsQueue1 -> [3, 1, 4, 2, 5]
- bfsQueue2 -> [3, 1, 4, 2, 5]
유의 사항
- DFS는 재귀 구현과 스택 구현의 결과가 다르다.
- 코드를 자세히 보면 알겠지만 dfsStack과 bfsQueue1 함수는 내부의 자료구조(Stack / Queue)의 차이만 있고 코드는 동일하다.
- dfsStack과 bfsQueue1을 외우는게 편할 것 같다.
- bfsQueue1과 bfsQueue2는 약간의 코드 차이가 있지만 완전히 동일하게 동작한다.
이진 탐색
이진 탐색(Binary Search)은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
- 시간 복잡도 : O(logN)
이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복.
- 현재 데이터셋의 중앙값(Median)을 선택.
- 중앙값 > 타겟일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택.
- 중앙값 < 타겟일 때 중앙값 기준 오른쪽 데이터셋을 선택.
- 타겟을 찾을때 까지 1~3을 반복.
/**
* Binary Search
* @param arr 탐색 대상 (정렬됨)
* @param target 탐색 값
*/
public static void BS(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int median = (start + end) / 2;
int medianValue = arr[median];
if (medianValue == target) {
System.out.println("target이 arr 배열에 [존재]합니다.");
return;
} else if (medianValue > target) {
end = median - 1;
} else {
start = median + 1;
}
}
System.out.println("target이 arr 배열에 존재하지 않습니다.");
}