Day 6 - 2022/10/24
💡 새롭게 알게된 점
자료구조와 알고리즘
BFS(너비 우선 탐색)
그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
BFS의 특징은 무엇이 있을까?
Queue를 이용하여 구현 가능
시작 정점에서 가까운 정점부터 탐색
V가 정점의 수, E가 간선의 수일 때 O(V+E)의 시간복잡도를 가짐
DFS(깊이 우선 탐색)
그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘
DFS의 특징은 무엇이 있을까?
Stack을 이용하여 구현 가능
시작 정점에서 깊은 정점부터 탐색
V가 정점의 수, E가 간선의 수일 때 O(V+E)의 시간복잡도를 가짐
그리디
매 선택에서 지금 이 순간 가장 최적의 답을 선택하는 알고리즘으로 최적해를 보장해주지 않음
그리디 알고리즘의 특징은 무엇이 있을까?
보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음
크루스칼, 다익스트라 알고리즘 등에 사용됨
직관적 문제 풀이에 적합
BFS vs DFS
그렇다면 언제 BFS를 사용하고 언제 DFS를 사용해야 할까?
트리의 깊이가 깊지 않고 답이 root에서 멀리 떨어져 있지 않다는 것을 안다면 BFS를 사용한다.
상당히 깊은 깊이를 가진 트리에서 답이 몇 개밖에 없을 때 DFS를 사용한다면 깊이를 전부 다 서치하므로 엄청난 시간이 소요되기 때문이다.
반면 상대적으로 넓이가 깊이에 비해 큰 경우 BFS를 사용한다면 상당한 메모리를 사용하기 때문에 비효율적이다.
즉, 상대적으로 봤을 때 트리가 깊은 경우 BFS, 넓은 경우 DFS를 사용하자!
조금 더 구체적으로 알아보자
DFS는 주로 모든 경로를 탐색해야 하는 경우, 경로 탐색에 조건이 있는 경우에 사용한다. 일반적으로 모든 경우를 탐색하기 때문에 재귀나 백트래킹을 사용해 구현한다.
BFS는 주로 두 정점 사이의 최단 경로를 찾는 경우, 두 정점 사이의 임의의 경로를 찾는 경우에 사용한다. 이는 탐색 범위를 단계적으로 확장하면서 탐색하기에 처음 발견하는 경로가 최단 경로가 되는 특징을 갖기 때문이다.
백트래킹?
문제에 대한 해를 찾는 과정에서 현재 노드가 해와 관련이 없다는 것을 알게 된다면 중단하고, 그 전 단계로 돌아가 다른 루트를 탐색하는 것을 의미한다. 즉, 해가 될 수 있는 노드들에 대해서만 부분 탐색을 수행하는 것을 의미한다.
❗️ 느낀점
DFS와 BFS는 익숙하지 않아서 코딩 테스트 문제를 풀 때마다 다시 참고하게 되는 알고리즘이다..
다른 유형의 문제들처럼 많이 풀어봐서 어떤 상황에 DFS, BFS를 써야 최적인지 알 수 있도록 문제를 많이 풀어봐야겠다.
시험기간과 겹쳐서 집중력이 좀 떨어지긴 했지만 핑계삼지 말고 더 열심히 굴러야지😢
오늘도 고생했다👊