최소신장트리(MST: Minimum Spanning Tree)를 구하는 알고리즘

제116회4교시SW공학/프로젝트관리신규

컴퓨터시스템응용기술사 제116회 4교시 27번 문항으로, 과목은 SW공학/프로젝트관리입니다.

원문 문제

컴퓨터시스템응용기술사 제116회 27번. 최소신장트리(MST: Minimum Spanning Tree)를 구하는 알고리즘

  1. 가. 크루스컬(Kruskal) 알고리즘
  2. 나. 프림(Prim) 알고리즘

핵심 키워드

  • 최소 신장 트리
  • 크루스컬 알고리즘
  • 프림 알고리즘
  • 탐욕 기법
  • Union-Find
  • 우선순위 큐

고득점 가이드 — 1. 개요

최소 신장 트리(MST)는 연결 가중 그래프에서 모든 정점을 사이클 없이 연결하면서 간선 가중치 합을 최소화하는 부분 그래프이며, 네트워크 인프라 설계에서 회선 비용 최소화의 표준 모델로 활용된다. 탐욕 기법을 적용한 대표 알고리즘으로 크루스컬과 프림이 있으며, 접근 방식·핵심 자료구조·시간 복잡도가 상이해 그래프 특성에 따라 선택한다. 두 알고리즘의 핵심 비교는 [표 1] 참조.

로그인하면 하루 1편은 무료로 전문을 볼 수 있어요

  • 변형 문제
  • 답안 골격
  • 고득점 가이드 전문
로그인하고 하루 1편 무료로 보기

출제 이력

  • 최소 신장 트리기출 1문항
  • 크루스컬 알고리즘기출 1문항
  • 프림 알고리즘기출 1문항
  • 탐욕 기법기출 1문항
  • Union-Find기출 1문항
  • 우선순위 큐기출 1문항

다른 회차에서 같은 키워드가 나온 문항이 아직 없어요.

같은 과목 문항

SW공학/프로젝트관리 기출 전체 보기 →

AI 생성 골격 · 미검수