Ch.7 그래프

챕터7 종합퀴즈 — 그래프 완전 정복

그래프의 기본 개념과 표현 방법을 종합적으로 점검한다DFS, BFS, 위상정렬, Union-Find의 선택 기준을 판단한다면접 실전 문제에 적절한 알고리즘을 매칭한다

그래프 챕터 총정리 시간

그래프의 기초부터 면접 실전까지 달려왔습니다. 이제 배운 모든 것을 종합 퀴즈로 점검합니다.

DFS? BFS? 위상정렬? Union-Find? 어떤 상황에 뭘 써야 하지?

문제의 키워드를 보고 자동으로 알고리즘을 선택할 수 있다면, 그래프 마스터입니다.

article

핵심 내용

무방향 그래프에서 노드 A와 B를 연결할 때, 인접 리스트에 추가해야 하는 횟수는?

노드 V개, 엣지 E개인 그래프에서 인접 리스트의 공간 복잡도는?

가중치가 없는 그래프에서 A에서 B까지 최단 거리를 구하려면?

DFS를 반복문으로 구현할 때 사용하는 자료구조는?

BFS에서 list.pop(0) 대신 deque.popleft()를 쓰면 시간이 O(n)에서 O(1)로 개선된다

Kahn's Algorithm에서 사이클을 감지하는 방법은?

Union-Find에서 find(3) == find(7)이 True라면 이것이 의미하는 바는?

Union-Find에서 경로 압축 없이 최악의 경우 find의 시간 복잡도는 O(n)이다

Number of Islands에서 visited 대신 사용하는 트릭은?

"작업에 선행 조건이 있고, 모든 작업을 완료할 수 있는 순서를 구하라" 이 문제에 적합한 알고리즘은?

Clone Graph에서 해시맵(old_to_new)이 없으면 사이클이 있는 그래프에서 무한 루프에 빠진다

Pacific Atlantic Water Flow에서 역방향 탐색을 하는 이유는?

그래프 마스터 달성!

edit_note

정리 노트

그래프 완전 정복

알고리즘 선택 가이드

경로/연결 요소
→ DFS (재귀 4줄 패턴)
최단거리/레벨
→ BFS (deque + popleft)
순서/의존 관계
→ 위상정렬 (Kahn's)
그룹 합치기/판별
→ Union-Find (경로 압축 + 랭크)

시간 복잡도

DFS / BFS
O(V + E)
위상정렬
O(V + E)
Union-Find
O(α(n)) ≈ O(1) per operation

면접 필수 4문제

Number of Islands
2D DFS + 원본 수정 트릭
Clone Graph
해시맵 DFS + visited 겸용
Course Schedule
위상정렬 + 사이클 감지
Pacific Atlantic
역방향 DFS + 교집합
★

그래프 = DFS/BFS가 기본 무기. 키워드로 알고리즘 자동 선택을 연습하세요!

check_circle

핵심 정리

  • 1그래프 = 노드 + 엣지, 인접 리스트가 기본 표현
  • 2DFS(스택/재귀) + BFS(큐) = 탐색의 양대 무기
  • 3위상정렬: 순서 문제 + 사이클 감지
  • 4Union-Find: 그룹 합치기/판별을 거의 O(1)로
  • 5면접 필수 4문제를 패턴으로 암기

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작