5월 셋째주 공부 기록서 - DFS,BFS

5월 20일

어제는 석가탄신일, 그 전까지는 몸이 안좋아 컨디션 관리를 좀 했다.

포스팅은 하진 않았지만 공부는 하고있다. 현재 하고있는 부분은 알고리즘 공부인데, 이전에 알고리즘 수업을 두번이나 들어 어떤 알고리즘인지는 모두 알고있어 진도가 빨리 나가는 편이다. 다만 문제에 적용하는 부분, 파이썬 코드로 짜는 부분은 아직 익숙하지 않다. 원래는 C를 하다 C++로, JAVA로, DART로 넘어가 공부하다 파이썬을 하니 머리가 혼미한느낌이다. 어차피 큰틀은 같긴하지만... 

 

현재 이것이 취업을 위한 코딩테스트다의 챕터 5의 DFS/BFS까지 공부했다. 

https://covenant.tistory.com/132

DFS BFS란? 백준 문제추천

도움이 되어 가져왔다. 아무래도 설명이 좀더 필요한것같아 찾아봤다. 왜 이책은 상하좌우에서 상이 -1,0이고 하가 1,0일까.. 0,1이랑 0,-1이여야지... 나중에 다시봐야겠다 잘못본걸수도 있으니까.

아무튼 결론은 

⭕ DFS 장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있습니다.

❌ DFS 단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용합니다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문입니다.

 

 

⭕ BFS 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

❌ BFS 단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

이고,

 

• DFS는 스택(혹은 재귀), BFS 큐를 사용합니다.
• BFS는 재귀적으로 동작하지 않습니다.

 

But 문제를 푸는 입장에서는 다음과 같은 구분점이 필요합니다.

• 최단 거리 문제를 푼다면 BFS를 사용합니다.
• 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.

라는 점이다. 핵심을 알아야 삽질 안하고 빨리 팔수있다는게 내 생각이다.