이전 영상의 내용이 개인적으로 너무 좋아서 해당 채널을 둘러보다가 보인 키워드!
해당 내용을 들어본 이유는 DFS/BFS가 코딩테스트에서 많이 출제되는 문제라는
이야기는 여러 커뮤니티에서 많이 들었다.
(웹개발 공부를 시작한지 얼마되지 않았을 때 들어볼 정도로..)
항해에서 이후에 배울 내용이지만 영상이 있어 한번 들어보았다.
여기서도 개인적으로 많은 것을 얻었다고 생각했다.
DFS = 하나를 몰아본다. => 깊이 우선 탐색
BFS = 여러 개를 한번에 본다. => 너비 우선 탐색
DFS/BFS의 대표적인 문제 유형
1. 경로탐색(최단거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형(모든 조합 만들기)
=> 프로그래머스의 (타켓 넘버, 네트워크 단어변환, 여행경로) <=문제 등을 보고
DFS/BFS를 떠올렸다면 시간단축과 방향성을 잘 잡은 것.
DFS는 한놈만 팬다. ->(재귀함수 사용)
재귀를 타고 타고 타서 탈출 조건에 먼저 도달하고 그 다음에 파라미터를 바꿔가면서
정답을 찾는 방식으로 구현하게 된다.
BFS는 여러 놈의 한대씩 때리면서 간다. ->(Queue/LikedList) 를 사용
- 영상에서 설명한 개발자는 DFS를 선호한다고 했다.
그 이유는 둘다 탐색을 하는 알고리즘이고 어떤 것을 써도 정답은 나오기 때문.
자신있고, 손에 익은 알고리즘을 사용하면 됨- DFS는 동작 검증이 쉬워 일일이 비교하기 때문에 선호한다
- BFS는 여러 조합을 한 칸 한 칸씩 만들다보니 조합이 완성되어서 정답과 비교하는 시점에
정확히 언제 이렇게 생성되었는지 파악하기가 어렵다
근본적으로 우리는 코딩테스트를 준비하는 사람이다.
코테는 곧 시간싸움이며 짧은 시간 내에 알고리즘을 검증해야한다.
이를 위해 DFS가 적합하며, 재귀함수를 익히면 코드가 보다 간결하고
버그 가능성도 근본적으로 더 작다고 한다
- DFS가 한 놈만 패는 경우인데 시간이 오래걸리면 시간이 초과될 수 있다.
DFS는 수행 시간 관점에 볼 때는 복불복이다. 운이 좋으면 첫번째 조합에서 최적의 답.
최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비할 가능성이 있다.
반면에 BFS는 모든 경우의 수를 한 걸음씩 나가기 때문에 초반에는 느릴 수 있으나
하나의 정답을 찾고자 할 때도 시간 복잡도가 낮다.
- 대부분의 TC(Test Case)들은 프로그래머스에서는 효율성 TC라고 해서
너무 단순하게 생각하면 시간 초과로 실패한다.
그러니 문제 순서와 난이도를 고려해서
앞쪽의 쉬운 문제라면 = DFS
뒤쪽의 어려운 문제라면 = DFS로 시간이 오래걸릴 것 같다면 처음부터 BFS 권장.
- DFS/BFS의 대표유형은 경로탐색,네트워크, 조합만들기
DFS 는 재귀함수로 간단하게
BFS 는 Queue / Likedlist로 활용하여 구현