DFS와 BFS의 차이를 말해주세요
DFS (Depth-First Search, 깊이 우선 탐색)
동작 방식: 한 경로를 끝까지 탐색한 후 돌아와 다른 경로를 탐색합니다.
자료구조: 스택 또는 재귀 함수를 사용합니다.
특징
최단 경로를 보장하지 않지만, 메모리 사용량이 비교적 적습니다.
백트래킹이 가능해 미로 탐색, 완전 탐색(예: 모든 경우의 수 찾기)에 적합합니다.
BFS (Breadth-First Search, 너비 우선 탐색)
동작 방식: 같은 레벨의 노드를 모두 탐색한 후 다음 레벨로 넘어갑니다.
자료구조: 큐를 사용합니다.
특징
최단 경로를 보장합니다 (예: 가중치 없는 그래프).
메모리 사용량이 많지만, 노드 간 거리가 균일할 때 효율적입니다.
꼬리 질문 대비
Q: DFS와 BFS 중 어떤 상황에서 어떤 알고리즘을 선택하나요?
BFS: 최단 경로 탐색 (예: 네트워크 라우팅), 연결된 구성요소 전체 탐색.
DFS: 경로 존재 여부 확인, 사이클 탐지, 백트래킹이 필요한 문제 (예: 스도쿠 풀이).
그래프(Graph)와 트리(Tree)의 차이점
그래프
정의: 노드(정점)와 간선(Edge)으로 구성된 비선형 자료구조입니다.
특징
순환(Cycle)이 가능합니다.
방향성/무방향성 모두 가능합니다.
계층 구조가 없으며, 루트 노드 개념이 없습니다.
트리
정의: 그래프의 특수한 형태로, 계층적 관계를 표현합니다.
특징
순환이 없으며(DAG), 부모-자식 관계가 명확합니다.
모든 노드가 연결되어 있고(Connected), 루트 노드가 존재합니다.
노드 간 단 하나의 경로만 존재합니다.
꼬리 질문 대비
Q: 트리가 그래프의 하위 개념이라면, 모든 트리는 그래프인가요?
A: 네, 트리는 **사이클이 없는 연결된 그래프(Connected Acyclic Graph)**입니다.
Q: 그래프와 트리의 실제 사례를 들어 설명해주세요.
그래프: SNS 친구 관계 (순환 가능).
트리: 파일 시스템 디렉토리 구조 (계층적).
'내일배움캠프 TIL' 카테고리의 다른 글
(BigO),(정렬의 종류) 본캠프 TIL 02/19 (0) | 2025.02.19 |
---|---|
nest 같은 매서드 순서의 문제 본캠프 TIL 02/14 (0) | 2025.02.14 |
(Arrow Function), (Hoisting) 본캠프 TIL (0) | 2025.02.12 |
(async/await), (Hoisting) 본캠프 TIL (0) | 2025.02.11 |
(var, let, const), (Promise) 본캠프 TIL 02/10 (0) | 2025.02.10 |