퀴즈 / 알고리즘 / 문제

알고리즘에서 '크루스칼(Kruskal)' 알고리즘과 '프림(Prim)' 알고리즘의 공통점과 차이점은?

보통 freeCodeCamp
보기 및 정답
A 둘 다 최소 신장 트리(MST)를 구하지만, 크루스칼은 간선을 정렬하여 추가하고, 프림은 정점에서 확장한다
B 크루스칼은 두 정점 간의 최단 경로를 구하는 알고리즘이고, 프림은 최소 신장 트리를 구한다
C 프림은 전체 간선을 가중치 순서로 정렬하여 추가하는 방식이고, 크루스칼은 임의의 정점에서 확장한다
D 크루스칼과 프림은 내부 동작 원리와 시간 복잡도가 완전히 동일하며, 같은 결과를 같은 방식으로 산출하는 알고리즘이다

해설

크루스칼과 프림 모두 그리디 알고리즘으로 최소 신장 트리를 구합니다. 크루스칼은 모든 간선을 가중치 순으로 정렬한 후 사이클이 생기지 않는 간선을 순서대로 추가합니다(Union-Find 활용). 프림은 하나의 정점에서 시작하여 연결된 간선 중 최소 가중치를 선택하며 트리를 확장합니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

관련 문제

셸 정렬(Shell Sort)의 핵심 아이디어는?
알고리즘
알고리즘에서 '힙 정렬(Heap Sort)'이 퀵 정렬과 다른 핵심 특징은?
알고리즘
허프만 코딩(Huffman Coding)의 핵심 원리는?
알고리즘
'스택(Stack)' 자료구조의 대표적인 활용 예에 해당하지 않는 것은?
알고리즘
알고리즘에서 '유니온-파인드(Union-Find, 서로소 집합)' 자료구조의 주된 용도는?
알고리즘
START THE LOOP · CHOOSE

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.

한 번의 결과에 기대지 않고 다시 만들 수 있도록, 문제 발견부터 제작·배포·수익화까지 이어지는 전체 흐름을 익혀보세요.

TTJ CLASS에서 다음 구조 고르기 →
처리 중...