← SO25 객관식 전체 목차

Graphdefinitionen, Breitensuche, Tiefensuche, DAG und topologische Sortierung

그래프 정의, BFS, DFS, DAG, 위상 정렬

중요한 독일어·영어 용어는 유지하되 설명과 학습 동선은 한국어 중심으로 제공합니다.

이 챕터의 문항별 독립 학습 페이지

단원 페이지에는 개요와 학습 순서만 둡니다. 각 문항의 용어·비유·수식·단계별 풀이·실제 채점은 아래 독립 페이지에서 이어집니다.

  1. II-9 · 2개 선택

    그래프(Graph)에 관한 설명 중 참인 것을 고르시오. 복기상 exactly two 섹션이지만 이 문항은 표기 검토가 필요하다.

    독립 개념 강의와 실제 채점 열기 →

  2. II-10 · 2개 선택

    그래프 알고리즘 및 관련 자료구조 설명 중 정확히 두 개를 고르시오.

    독립 개념 강의와 실제 채점 열기 →

  3. II-11 · 2개 선택

    BFS와 DFS에 관한 설명 중 정확히 두 개를 고르시오.

    독립 개념 강의와 실제 채점 열기 →

30초 핵심 요약

30초 핵심

그래프(graph)는 \(G=(V,E)\)G=(V,E)이다. 방향 그래프(directed graph)에서는 E ⊆ V × V이고, 무방향 그래프(undirected graph)에는 대칭성이 추가된다. 너비 우선 탐색(BFS)은 큐로 층을 만들며 가중치 없는 최단 간선 수를 구한다. 깊이 우선 탐색(DFS)은 스택·재귀와 발견·종료 시각을 이용해 간선 분류와 위상 정렬의 근거를 만든다.

핵심 수식·규칙

인접 리스트에서 BFS·DFS·위상 정렬·Kosaraju는 \(O(|V|+|E|)\)O(|V|+|E|)이다. 위상 순서에서는 모든 간선 (u,v)에 대해 u가 v보다 앞에 와야 한다.

시험에서 알아볼 신호

E := V × V, 필요충분조건(iff) 대칭성, 무가중(unweighted), 큐(Queue), 스택, Rückwärtskante, Kreuzkante, terminiert, stets를 먼저 표시한다.

시험 연결

복기 원문 문항
  • II-9
  • II-10
  • II-11
선택 규칙

섹션 II는 정답이 정확히 두 개인 형식\((\text{exactly}_{\text{two}})\)(exactly(two))으로 복원되었다. II-9는 출처 문구를 글자 그대로 검증하면 참인 보기가 하나뿐이므로 검토 필요\((\text{needs}_{\text{review}})\)(needs(review))상태로 보존한다.

다른 문제로 옮겨 쓰는 목표

정답 라벨을 외우는 대신 동일·부분집합, 방향·대칭, 큐·스택, DAG·사이클, 국소·전역 순서를 판정하는 절차를 훈련한다.

먼저 알아야 할 용어와 전제

개념 강의

한국어 직관 설명

BFS는 물결처럼 가까운 층부터 퍼지고, DFS는 한 갈래를 끝까지 따라갔다 돌아온다. 위상 정렬(topological sorting)은 DAG에서 선후관계를 한 줄로 세우는 작업이다.

정의

방향 그래프(directed graph)는 G=(V,E), E ⊆ V × V이다. 무방향 그래프(undirected graph)는 간선 관계가 대칭이다. BFS(Breitensuche)는 FIFO 큐를 사용하고, DFS(Tiefensuche)는 재귀·스택을 사용한다. DAG는 방향 비순환 그래프(directed acyclic graph)이다.

선수 개념
  • 유한 집합(finite set)
  • 순서쌍과 대칭 관계의 차이
  • 큐와 스택
불변식과 성질

BFS 큐는 감소하지 않는 거리(dist) 순서로 정점을 처리한다. DFS의 회색(GRAY) 정점은 재귀 스택에 있으며, 역방향 간선(back edge)은 방향 사이클의 존재를 뜻한다. 무방향 DFS에서는 강의 규약에 따라 트리 간선과 역방향 간선만 남는다.

실행시간과 공간 복잡도

인접 행렬은 \(\Theta(|V|^2)\)Θ(|V|²) 공간을 사용하고 인접 리스트는 \(\Theta(|V|+|E|)\)Θ(|V|+|E|) 공간을 사용한다. 인접 리스트에서 BFS, DFS, DFS 기반 위상 정렬, Kosaraju는 \(O(|V|+|E|)\)O(|V|+|E|)에 실행된다.

주요 경우와 경계 사례

유한 그래프에는 무한한 간선 집합이 있을 수 없다. \(E = V\)E = V × V는 완전 관계를 뜻한다. BFS의 최단 경로는 가중 최단 경로가 아니다. 사이클이 있는 방향 그래프에는 위상 순서가 없지만, 올바른 알고리즘은 그래도 종료하거나 실패를 보고한다.

시험에서 주의할 표현
  • immer
  • nur
  • jede
  • keine
  • stets
  • unweighted
  • weighted
  • Queue
  • Stack
  • \(E := V x V\)E := V x V
  • DAG
  • terminiert
직접 해 보는 실험실

BFS·DFS·DAG 그래프 실험실

다음 상태를 먼저 예측한 뒤 한 단계 실행하여 확인하세요.

준비됨

새 문장 판별 체크리스트

능동 회상

구두시험 질문

시험 직전 요약

핵심

그래프의 V와 E는 유한하다. 방향 그래프는 E ⊆ V × V이며 대칭성이 필요 없다. 무방향 그래프는 대칭 관계이지만 반드시 완전 관계일 필요는 없다.

경계와 복잡도

인접 리스트의 BFS·DFS·위상 정렬·Kosaraju는 \(O(|V|+|E|)\)O(|V|+|E|)이다. 행렬 공간은 \(\Theta(|V|^2)\)Θ(|V|²), 리스트 공간은 \(\Theta(|V|+|E|)\)Θ(|V|+|E|)이다.

경계 사례

II-9를 문자 그대로 E := V × V로 읽으면 D는 거짓이다. E ⊆ V × V와 대칭성을 의도했다면 D는 참이 될 수 있다.

판정 절차

먼저 조건 단어를 읽는다. 무가중, 방향, 무방향, DAG, 큐, 스택, terminiert, stets를 표시한다.

출처

AI 후속 학습 프롬프트

마지막 생성: 2026-08-03 03:24