알고리즘에 대한 설명으로 가장 옳지 않은 것은? | [서울시 연구사 컴퓨터공학] 20년 1회차 기출문제 상세 페이지
1[서울시 연구사 컴퓨터공학] 20년 1회차
알고리즘에 대한 설명으로 가장 옳지 않은 것은?
1
Dijkstra 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최장 경로를 찾는 방법이다.
2
Prim의 알고리즘은 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법이다.
3
Kruskal 알고리즘은 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다.
4
Floyd 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단경로를 한 번에 모두 찾는 방법이다.
해설
Dijkstra 알고리즘은 최장 경로가 아니라 한 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이므로 옳지 않다.
음수 가중치가 없는 그래프에서 아직 확정되지 않은 정점 중 거리가 가장 짧은 정점을 하나씩 확정해 나가는 탐욕적 방법이다.
- Prim 알고리즘: 시작 정점에서 출발해 트리에 붙은 간선 중 최소 가중치 간선을 골라 신장트리를 한 정점씩 확장한다 — 옳은 설명.
- Kruskal 알고리즘: 간선을 가중치 순으로 보며 사이클이 생기지 않는 최소 간선을 고르는 탐욕(greedy) 알고리즘이다 — 옳은 설명.
- Floyd 알고리즘: 동적 계획법으로 모든 정점 쌍 사이의 최단 경로를 한 번에 구한다 — 옳은 설명.
오류나 개정된 내용이 보이면 알려주세요
이어서 풀어보기
[서울시 연구사 컴퓨터공학] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- 대추나무빗자루병에대한설명으로옳은것은? {"answer":4,"content":[{"content":"균류에의해전반된다.\n","url":""},{"co17년-1회차-산림기사-필기
- 호두나무잎벌레에대한설명으로옳은것은? {"answer":3,"content":[{"content":"1년에1회발생하며,알로월동한다.\n","url":""20년-3회차-산림기사-필기
- 알츠하이머병에관한설명으로틀린것은? {"answer":2,"content":[{"content":"신경인지장애의가장흔한유형이다.\n","url":""},17년-3회차-임상심리사2급-필기