Algorithm - Search
Search
Search(탐색) 알고리즘은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말합니다.
이번 포스트에서는 대표적인 탐색 알고리즘 세 가지에 대해서 알아보고 직접 구현하여 문제를 해결해보겠습니다.
- DFS(깊이 우선 탐색)
- BFS(너비 우선 탐색)
- Binary Search(이진 탐색)
DFS
DFS(깊이 우선 탐색, depth-first search)는 그래프 완전 탐색 기법 중 하나입니다. DFS는 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다.
- 특징
- 재귀 함수로 구현
- 스택 자료구조 이용
- 시간 복잡도(노드 개수: V, 간선 개수: E)
- $O(V + E)$
DFS는 구현 시 재귀 함수를 이용하기 때문에, 백준에서 파이썬으로 문제 풀이 시에 RecursionError가 발생할 수 있습니다. 이는 파이썬의 기본 재귀 깊이를 넘어가서 생기는 문제로 한계 재귀 깊이를 보다 깊게 설정하는 방법과 재귀를 사용하지 않고 스택 자료구조를 이용하여 해결하는 방법이 있습니다.
한계 재귀 깊이를 늘리는 방법
1
2
import sys
sys.setrecursionlimit(본인이 원하는 재귀 깊이 입력) # 기본 설정은 1000
위 코드를 제출할 코드 맨 위에 작성하면 한계 재귀 깊이를 본인이 원하는 재귀 깊이만큼 깊게 설정할 수 있습니다.
단, pypy를 이용하여 제출할 경우 재귀 깊이를 너무 깊게 설정하게 되면 메모리 초과가 발생할 수 있음에 주의해야합니다.
DFS 예시
DFS pesudo code
재귀를 이용한 DFS pesudo code
1
2
3
4
5
6
7
procedure DFS(G, v) is
label v as discovered # v를 탐색된 것으로 표시
# v와 인접한 간선에 포함된 모든 w에 대해서
for all directed edges from v to w that are in G.adjacentEdges(v) do
# w가 탐색되었다고 표시되어 있지 않다면
if vertex w is not labeled as discovered then
recursively call DFS(G, w) # 재귀적으로 DFS 호출
스택 자료구조를 이용한 DFS pesudo code
1
2
3
4
5
6
7
8
9
10
11
procedure DFS_iterative(G, v) is
let S be a stack # S를 스택 자료구조로 선언
S.push(v) # S에 v를 삽입
while S is not empty do # S에 남은 노드가 없을 때까지 반복
v = S.pop() # S의 최상위 노드를 v에 대입
# 만약 v가 탐색되었다고 표시되어 있지 않다면
if v is not labeled as discovered then
label v as discovered # v를 탐색된 것으로 표시
# v와 인접한 간선에 포함된 모든 w에 대해서
for all edges from v to w in G.adjacentEdges(v) do
S.push(w) # S에 w를 삽입
DFS 구현
C++
재귀 이용
1
2
3
4
5
6
7
8
9
void DFS(vector<vector<int>>& Graph, int& v, vector<bool>& Visited) {
Visited[v] = true;
for (int w: Graph[v]) {
if (!Visited[w]) {
DFS(Graph, w, Visited);
}
}
}
스택 이용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DFS_iterative(vector<vector<int>>& Graph, int& v, vector<bool>& Visited) {
stack<int> S;
S.push(v);
while (!S.empty()) {
int v = S.top();
S.pop();
if (!Visited[v]) {
Visited[v] = true;
for (int w: Graph[v]) {
S.push(w);
}
}
}
}
Python
재귀 이용
1
2
3
4
5
6
def DFS(Graph, v, Visited):
Visited[v] = True
for w in Graph[v]:
if not Visited[w]:
DFS(Graph, w, Visited)
스택 이용
1
2
3
4
5
6
7
8
9
10
11
def DFS_iterative(Graph, v, Visited):
S = list()
S.append(v)
while len(S) != 0:
v = S.pop():
if not Visited[v]:
Visited[v] = True
for w in Graph[v]:
S.append(w)
- 장점
- 현재 경로상의 노드들만 기억하면 되므로 메모리 효율이 비교적 좋다
- 목표 노드가 깊이 존재할 경우, 해를 빨리 구할 수 있다
- 단점
- 해가 없는 무한한 경로에 깊이 빠질 가능성이 있다
- 목표 노드까지 가는 경로가 최단 경로가 된다는 보장이 없다
BFS
BFS(너비 우선 탐색, breadth-first search)는 그래프 완전 탐색 기법 중 하나입니다. BFS는 그래프의 시작 노드에서 출발하여 인접한 노드를 먼저 탐색하는 알고리즘입니다.
- 특징
- 큐 자료구조 이용
- DFS와 다르게 큐에 노드를 삽입하기 전 방문 체크
- 시간 복잡도(노드 개수: V, 간선 개수: E)
- $O(\vert V \vert + \vert E \vert)$
큐 자료구조 이용 방법
BFS는 DFS와 달리 큐 자료구조를 이용하여 구현하게 됩니다. 파이썬에서 큐 자료구조를 이용하기 위해선 collections 모듈 내부의 deque를 이용하여야 합니다. 아래 코드를 파일 맨 위에 적고 따라해주세요.
1
2
from collections import deque
Q = deque()
BFS 예시
BFS pesudo code
큐 자료구조를 이용한 DFS pesudo code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure BFS(G, root) is
let Q be a queue # Q를 큐 자료구조로 선언
label root as explored # root 노드를 탐색되었다고 표시
Q.enqueue(root) # Q에 root 노드를 삽입
while Q is not empty do # Q에 남은 노드가 없을 때까지 반복
v := Q.dequeue() # Q에서 제일 앞 노드를 제거하고 그 값을 v에 대입
if v is the goal then # 만약 목표 노드가 v라면
return v # 그 값을 리턴
for all edges from v to w in G.adjacentEdges(v) do # v와 인접한 모든 노드 w에 대해
if w is not labeled as explored then # 만약 w가 탐색되었다고 표시되어 있지 않다면
label w as explored # w를 탐색되었다고 표시
w.parent := v # w의 부모 노드에 v를 대입
Q.enqueue(w) # Q에 w를 삽입
BFS 구현
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(vector<vector<int>>& Graph, int& root, vector<bool>& Visited) {
queue<int> Q;
Visited[root] = true;
Q.push(root);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
for (int w: Graph[v]) {
if (!Visited[w]) {
Visited[w] = true;
Q.push(w);
}
}
}
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
def BFS(Graph, root, Visited):
Q = deque()
Visited[root] = True
Q.append(root)
while Q:
v = Q.pop()
for w in Graph[v]:
if not Visited[w]:
Visited[w] = True
Q.append(w)
- 장점
- 그래프에 가중치가 없다면, 시작 노드에서 목표 노드까지 최단 경로를 보장한다
- 단점
- 경로가 매우 긴 경우, 탐색 가지가 급격히 증가하여 많은 기억 공간을 필요로 하게 된다
Binary Search
이진 탐색(Binary search)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 탐색 알고리즘입니다. 처음 중간 값을 임의의 값으로 선택하여, 그 값과 목표 값의 크고 작음을 비교하는 방식으로 탐색을 진행합니다. 처음 선택한 중간 값이 만약 목표 값보다 크다면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됩니다.
- 시간 복잡도
- $O(logN)$
Binary Search 예시
Binary Search pseudo code
1
2
3
4
5
6
7
8
9
10
11
12
13
A를 정렬된 리스트, n을 리스트의 요소 개수, T를 목표 값이라고 할 때
procedure binary_search(A, n, T) is
L := 0 # L에 0을 대입
R := n - 1 # R에 n - 1을 대입
while L <= R do # L이 R보다 작거나 같은 때까지 반복
m := floor((L + R) / 2) # m에 L과 R의 중간 값을 대입
if A[m] < T then # 만약 A의 m번째 요소가 T보다 작다면
L := m + 1 # L에 m + 1을 대입(새로운 최솟값)
else if A[m] > T then # 만약 A의 m번째 요소가 T보다 크다면
R := m - 1 # R에 m - 1을 대입(새로운 최댓값)
else: # 둘 다 아니고 A의 m번째 요소가 T라면
return m # m을 리턴
return unsuccessful # 반복하는동안 목표 값을 찾지 못했다면 실패
Binary Search 구현
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_search(int[]& A, int& n, int& T) {
int L = 0;
int R = n - 1;
while (L <= R) {
int m = (L + R) / 2
if (A[m] < T) {
L = m + 1;
}
else if (A[m] > T) {
R = m - 1;
}
else {
return m;
}
}
return -1 * (INT_MAX - 1);
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search(A, n, T):
L = 0
R = n - 1
while L <= R:
m = (L + R) // 2
if A[m] < T:
L = m + 1
elif A[m] > T:
R = m - 1
else:
return m
return -999999999
- 장점
- 로그 시간에 목표 값을 찾을 수 있다
- 단점
- 정렬된 리스트에서만 사용 가능하다