면접 예상 질문 - 알고리즘

1. DFS와 BFS의 차이

DFS(Depth First Search: 깊이 우선 탐색) - 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

 

1. 모든 노드를 방문하고자 하는 경우 이 방법을 선택

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS) 좀 더 간단하다

3. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다 

 

DFS의 특징

자기 자신을 호출하는 순환 알고리즘의 형태

그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함 그렇지 않을 경우 무한 루프에 빠질 수 있음 

 

BFS(Breadth First Search : 너비 우선 탐색) - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 사용 

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다