정보처리기사 2008년 1회 (시행일 : 4월 20일) [배점 : 30점]
제시된 [그림]은 최소비용 그래프 G의 각 정점에 연결된 N-1개의 간선들의 가중치를 모두 합하여 정점1에서 N까지 이동에 소요되는 총 가중치의 합을 출력하는 순서도이다. <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항 보기>에서 선택하여 해당 번호 (1)~(5)에 마크하시오.
정점 1에서 N까지 이동하는 가중치 그래프 G가 있다.
정점 1에서 N까지 이동하는 가중치 그래프 G의 모든 간선의 개수는 X이며, 모든 간선에는 가중치가 주어져 있다. 각 간선들이 가중치를 정점과 정점 사이의 이동에 필요한 소요비용이라고 할 때. N개의 정점들에 연결된 총 K개의 간선의 가중치 Selection Sort를 이용하여 오름차순 정렬하고 정렬되어 있는 순서대로 가장 가중치가 작은 간선부터 사이클 없이 N-1개를 삽입하여 연결하면 최소비용 그래프 G를 완성할 수 있다.
<처리조건>
- 그림의 순서도에 제시되어있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 설계 시 유의하시오.
- 정점의 개수는 N이고, 간선의 총 개수는 X이다.(단, N>5, X>7)
- 배열 "Cost(X)"는 X개의 각 간선들의 가중치 값이 저장된다고 가정한다. (단, 가중치 값 중 동일 값은 없다고 가정한다.)
- 배열 "Cycle(X)"은 X개의 각 간선들 삽입에 따른 그래프의 사이클 여부를 체크한 값이 저장되어 있는 배열로서 간선 삽입 시 사이클이 형성될 경우는 1, 형성되지 않을 경우는 0의 값이 자동적으로 저장되어 있다고 가정한다.
![](https://img1.daumcdn.net/relay/cafe/original/?fname=http%3A%2F%2Fcfs15.tistory.com%2Fupload_control%2Fdownload.blog%3Ffhandle%3DYmxvZzM1MTA0QGZzMTUudGlzdG9yeS5jb206L2F0dGFjaC8wLzkuanBn)
정보처리기사 실기 알고리즘 기출문제 다운로드 : http://cafe.daum.net/gunsystem/1GN6/80
알고리즘 기출문제 파일은 효율적 관리를 위해 건시스템정보처리학원 카페에 등록 및 관리합니다.