알고리즘에 대한 설명으로 가장 옳지 않은 것은? | [서울시 연구사 컴퓨터공학] 20년 1회차 기출문제 상세 페이지

1[서울시 연구사 컴퓨터공학] 20년 1회차
알고리즘에 대한 설명으로 가장 옳지 않은 것은?
1
Dijkstra 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최장 경로를 찾는 방법이다.
2
Prim의 알고리즘은 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법이다.
3
Kruskal 알고리즘은 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다.
4
Floyd 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단경로를 한 번에 모두 찾는 방법이다.
해설

Dijkstra 알고리즘은 최장 경로가 아니라 한 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이므로 옳지 않다.

음수 가중치가 없는 그래프에서 아직 확정되지 않은 정점 중 거리가 가장 짧은 정점을 하나씩 확정해 나가는 탐욕적 방법이다.

  • Prim 알고리즘: 시작 정점에서 출발해 트리에 붙은 간선 중 최소 가중치 간선을 골라 신장트리를 한 정점씩 확장한다 — 옳은 설명.
  • Kruskal 알고리즘: 간선을 가중치 순으로 보며 사이클이 생기지 않는 최소 간선을 고르는 탐욕(greedy) 알고리즘이다 — 옳은 설명.
  • Floyd 알고리즘: 동적 계획법으로 모든 정점 쌍 사이의 최단 경로를 한 번에 구한다 — 옳은 설명.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[서울시 연구사 컴퓨터공학] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요서울시 연구사 컴퓨터공학 기출문제 암기장 전체 보기