'BFS' 태그의 글 목록

DFS (Depth-First Search)정의DFS는 깊이 우선 탐색(Depth-First Search)으로, 그래프나 트리에서 출발 노드에서 시작해 한 방향으로 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식스택(Stack) 자료구조를 기반으로 작동하며, 재귀적으로 구현하는 경우도 많음특징탐색 방식특정 경로로 갈 수 있을 때까지 계속 탐색자료구조스택(재귀 호출 포함)활용 예시경로 탐색, 조합 생성, 순열 생성장점경로 탐색 및 백트래킹 문제에 적합메모리 사용량이 적은 경우도 있음(특히 그래프가 얕은 경우)단점경로가 매우 길거나 무한 루프의 가능성이 있는 경우, 스택 오버플로우 발생 가능최단 경로를 보장하지 않음시간 복잡도O(V + E)V는 노드(정점)의 개수, E는 간선의 개수.모든 노드와 간..

CS/알고리즘 2025. 1. 16. 17:22

이전 1 다음