TIL 7/11

학습내용

오늘은 dfs와 bfs를 공부했다. dfs, bfs는 탐색 알고리즘이다. dfs는 깊이 우선 탐색으로 모든 노드의 마지막 리프 노드까지 탐색하고 나와서 옆의 노드로 이동한다. bfs는 너비 우선 탐색으로 같은 레벨에 있는 노드를 우선적으로 탐색한다. dfs와 bfs의 특징을 조금 더 살펴보면 dfs는 리프노드까지 들어가기 때문에 모든 노드를 완전히 탐색한다는 특징이 있다. 그리고 깊게 들어갈때 재귀를 이용한다. 그렇게 재귀를 사용하다보니 스택을 얼마나 사용하게 될지 알기가 어려운 단점도 있다. bfs는 너비를 탐색하기 때문에 완전하게 탐색하기 전에 끝나는 경우가 많다. 단계적인 레벨로 탐색하기 때문에 최단경로를 찾는데 좋다. 그리고 bfs는 옆의 같은 레벨의 노드를 모두 검색하기 때문에 다음에 어디를 탐색하러 가야하는지 알기 위해서 자료구조 queue를 사용하는 것이 특징이다. 재귀보다는 queue를 이용한 반복문으로 탐색한다.

느낀점

알고리즘이 아직 익숙해지지 않는다. 알고리즘은 정말 많이 풀고 경험해봐야 하는 것 같다. 아직도 응용문제를 풀기에는 어렵다. 바로 아이디어를 떠올리지 못한다. 아이디어보다도 탐색을 구현하는 부분이 아직 익숙치 않다. 어떻게 모두 탐색하게 할 수 있는지를 고민하고 있는 것을 보면 아직 제대로 이해하지 못한 부분이 많은 것 같다. 머리속에 있는 방법을 코드로 표현하는 연습을 많이 해야될 것 같다. 다음에 다시 공부할 때는 조금더 이해가 될 수 있었으면 좋겠다.