Algorithm & Data Structure1

• 

  DFS & BFS 그래프 탐색 방법은 크게 DFS(깊이 우선 탐색)와 BFS(넓이 우선 탐색)이 있다. 그래프(Graph)란 Node(정점)와 Edge(간선)로 이뤄진 자료구조이며 Node(정점)들은 Edge(간선)로 이어져있다.그래프를 탐색한다는 건 한 노드를 시작으로 간선을 통해 모든 노드들을 한번씩 방문하는 것을 의미한다. 1. DFS (Depth-First Search) : 일단 최대한 깊게 탐색 후 옆으로 탐색루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 (자식들을 우선적으로 탐색하는 방법)스택 또는 재귀함수로 구현 (자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다)한 노드에서 제일 마지막 자식까지 탐색하고 돌아오는 과정을 .. Algorithm & Data Structure 2024. 7. 14.