SW 전공

시험 직전 요약장

판단 기준과 헷갈리는 개념, 대표 예제를 짧게 확인하세요.

과목단원

그래프 탐색, 최단경로와 최소신장트리

Kruskal은 간선 중심, Prim은 정점 집합 확장 중심이다.

도식좌우로 이동해 전체 내용을 확인하세요. 키보드: ←·→, Home·End
Kruskal: 간선 정렬→작은 간선부터 → 서로 다른 집합이면 채택Prim: 임의 시작→현재 트리에서 밖으로 나가는 최소 간선 채택

MST는 모든 정점을 최소 총비용으로 연결한다. 특정 시작점에서 각 정점까지 거리를 최소화하는 최단경로 트리와 목적이 다르다.

알고리즘	대상	음수 간선	핵심
BFS	무가중치·동일 가중치	해당 없음	큐로 레벨 탐색
Dijkstra	한 출발점	불가	가장 가까운 미확정 정점 선택
Bellman-Ford	한 출발점	가능	모든 간선 반복 완화, 음수 사이클 탐지
Floyd-Warshall	모든 정점 쌍	가능*	중간 정점을 하나씩 허용하는 DP

현재 브라우저의 연습 채점 기록에서 공개된 단원과 연결된 오답을 확인합니다.

오답 기록을 확인하고 있습니다.