목록dfs (1)

초보 개발자의 기록

알고리즘 개념 - 깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)깊이 우선 탐색DFS (Depth-first search)은 그래프 완전 탐색 기법 주 ㅇ하나그래프의 시작 노드에서 출발하여 탐색한 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 노드 개수:V에지 개수:E기능특징시간 복잡도 (노드 수: V, 에지 수:E)그래프 완전 탐색- 재귀 함수로 구현- 스택 자료구조 이용O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 함.깉이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등 DFS는 한번 방문한 노드를 다시 방문하면 안되느모 노드 방문 여부를 체크할 배열이 필요..
Study/Coding Test 2025. 8. 18. 22:22
이전 Prev 1 Next 다음