DFS와 BFS
비선형적인 탐색 알고리즘
DFS(깊이우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 → 스택 또는 재귀함수로 구현
BFS(너비우선탐색) : 현재 정점에 연결된 가까운 점들부터 탐색
→ 큐를 이용하여 구현
DFS appendix - 백트래킹 Backtracking
후보를 구축해 나아가다 가능성이 없는 후보를 포기(Backtrack)해 정답을 찾아가는 범용 알고리즘
경로를 탐색하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다.
갔다 되돌아오기를 반복 : 운이 좋으면 시행착오를 덜 거칠 수 있지만 최악의 경우에는 모든 경우를 다 거친 다음에 도착할 수 있다.
주로 재귀로 구현
- 제약 충족 문제 Constraint Satisfactions Problems 에 유용함
시간복잡도
기본적으로 모든 노드를 탐색한다는 점에서 시간 복잡도는 동일하다.
N : 노드, E : 간선
👨🏻💻 인접 리스트 : $O(N+E)$ 인접 행렬 : $O(N^2)$일반적으로 간선의 크기가 에 비해 상대적으로 작기에 인접 리스트 방식이 효율적이다.
DFS와 BFS의 문제 유형/응용
- 그래프의 모든 정점을 방문하는 문제
단순히 모든 정점을 방문하는 문제라면 DFS, BFS 두 가지 방법 아무거나 사용해도 문제 없다.
- 경로의 특징을 저장해둬야 하는 문제
예를 들어 각 정점에 숫자가 있고 a부터 b까지 가는 경로를 구하는데 경로에서 특정 숫자가 있으면 안 된다는 문제 등 같은 경우는 DFS를 사용해야 한다. (BFS는 경로의 특징을 가지지 못함!!)
- 최단거리 문제
미로 찾기 같은 최단 거리 문제는 BFS가 유리하다.
DFS의 경우 처음에 깊게 들어간 경로가 최단 거리가 아닐 가능성이 매우 높지만, BFS는 현재 노드에서 가까운 곳부터 검색하기 때문에 BFS가 유리함
Appendix)
- 검색 대상 그래프가 매우 클 경우 DFS를 우선적으로 고려
- 규모가 상대적으로 크지 않고 검색 시작 지점부터 목적지가 멀지 않다면 BFS
Pseudo code
DFS 재귀
DFS(G, v)
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)DFS 스택
DFS-iterative(G, v)
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)BFS 큐
BFS(G, start_v)
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)Binary Search(이진 탐색)
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
핵심은 리스트가 먼저 정렬이 되어있어야 한다는 것이다.
→ 재귀와 반복문으로 구현할 수 있다.
시간복잡도
시간이다. ( 시간임)
- 단계마다 탐색 범위를 반으로 줄이므로 위 시간이 된다.
Python에서는 이진 탐색을 쉽게 구현하기 위해 bisect라는 내장 모듈을 지원한다.
Binary Search 문제 유형/응용
- 가장 흔한 유형은 숫자가 존재하는지 여부
- 나무, 전선 자르기 : min을 0으로, max를 리스트의 최대값으로 잡고 좁혀나가기
- 공유기 설치 : 주어진 개수만큼의 공유기를 최대한 거리가 멀게 설치하는 유형. 거리를 min = 0, max를 리스트의 최대값으로 잡음
- K번째 수 같은 이진 탐색인지 파악하기 어려운 유형도 있음.
- 풀이해보자면 배수인 점을 이용해서 count를 파악하고 binary search를 하면 됨.
TIP
문제 조건이 10억을 넘어가면 이분 탐색으로 풀 수 밖에 없다.
Pseudo code
재귀 버전
BinarySearch(A[0..N-1], value, low, high) {
if (high < low)
return -1 // x가 배열에 없을 때
mid = (low + high) / 2 // 중간 요소 설정
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1) // 오른쪽 배열 버리고 다시 이진 탐색 (recursive)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high) // 왼쪽 배열 버리고 다시 이진 탐색 (recursive)
else
return mid // 위치값 리턴
}반복문 버전
binarySearch(A[0..N-1], value) {
low = 0
high = N - 1 // 시작(low)과 끝(high)값 설정
while (low <= high) {
mid = (low + high) / 2 // 중간 요소 설정
if (A[mid] > value)
high = mid - 1 // 오른쪽 배열 버리고 다시 이진 탐색 (while문)
else if (A[mid] < value)
low = mid + 1 // 왼쪽 배열 버리고 다시 이진 탐색 (while문)
else
return mid // found k
}
return -1 // not found k
}DP(Dynamic Programming)
큰 문제를 작은 문제로 나누어 푸는 문제를 말한다.
분할 정복과 비슷하지만 차이점은 작은 문제의 반복이 일어나는지 안일어나는지이다. 분할 정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어푸는 방법이고 DP는 작은 부문들이 반복되는 것을 이용해 풀이하는 방법이다.
DP의 조건
- 작은 문제의 반복이 일어나는 경우
- 같은 문제는 구할 때마다 정답이 같음
Memoization(메모이제이션)
메모이제이션은 작은 문제들이 반복되고 이 결과값이 항상 같으므로 이를 저장해놓고 재사용을 하는 것을 Memoization이라고 한다.
가장 대표적인 예시는 피보나치 수열이다.
- 작은 문제들이 반복된다.
- 같은 문제는 구할때마다 정답이 같다.
Pseudo code
Bottom-up : 작은 문제부터 큰 문제로 구해 나아가는 방법
def fibonacci_bottom_up(n):
if n <= 1:
return n
a = 0
b = 1
for i in range(0, n-1):
next = a + b
a = b
b = next
return nextTop-down : 재귀 함수로 구현하는 경우가 대부분 이 방식이다. 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그 때 작은 문제를 해결한다.
def fibonacci_top_down(n):
if memo[n] > 0:
return memo[n]
if n <= 1:
memo[n] = n
return memo[n]
else:
memo[n] = fibonacci_top_down(n - 1) + fibonacci_top_down(n - 2)
return memo[n]Bottom-up vs Top-down?
둘을 단순 비교한다면 우위가 없다. 일반적으로 top-down 방식이 가독성이 좋고 bottom-up 방식의 경우 풀기 쉽지만 가독성이 떨어진다고 이야기를 한다. 그냥 편한 방식으로 풀자!
DP 문제 유형/응용
- Coin Change Problem : 거스름 돈 거슬러줄 때 동전의 갯수를 최소화하는 문제
- KnapSack : 배낭 채우기 문제
- LCS(Longest Common Subsequence) : 최장 공통 문자열
- LIS(Longest Increasing Subsequence) : 최장 증가 부분 수열
- Edit Distance : 편집 거리 알고리즘, 두 문자열의 유사도를 판단하는 알고리즘
- Matrix Chain Multiplication : 연쇄행렬 최소곱셈 알고리즘
유형별 정리는 각자 하이퍼링크를 달아두었으니 참고하시길 바랍니다😁
재귀 방식은 별로 적합하지 않음
