티스토리 뷰
안녕하십니까 유건아빠입니다.
오늘은 기사기출-알고리즘-선택정렬(최소비용신장트리)에 대하여 알아보도록 하겠습니다.
우선 기출문제 풀이에 앞서 오름차순정렬에 대하여 알아보겠습니다.
100, 70, 90, 80, 90 숫자가 나열되어 있을경우 오름차순으로 정렬시 70,80,90,90,100 이렇게 정렬을 시키는것을 말합니다.
이렇게 정렬할때 우리는 100부터 비교를 오른쪽으로 해보면서 100보다 70이 크므로 우측으로 이동하고 또 90보다 크므로 우측으로 이동하고 이렇게 해서 100이 가장 우측에 큰값으로 정렬이 됨을 알수 있습니다.
이렇게 숫자를 비교하고 위치를 바꿀때 프로그램에서 사용하는 방법은 TEMP변수를 사용한다는 것입니다.
사과상장와 배상자가 있을경우 이 두 가지를 바꿔서 넣어야 할경우 빈상자를 한나 준비하고 사과를 빈상자에 넣고 그다음 배를 원래 사과상자에 넣고 빈사장에 있던 사과를 배상자에 넣으면 위치를 바꿀수 있게 됩니다. 이때 사용하는 빈상자를 TEMP변수로 생각하시면 됩니다.
마지막으로 기출 문제를 풀기위한 최소비용신장트리를 이해해야 하는데 아래 그림과 같이 점과 선이 서로 연결되어 있는 그림을 최소 비용신장트리로 만든 그래프는 왼쪽그림처럼 가중치가 가장 작은 간선들을 사이클이 이루지 않도록 연결한 그래프 가 되겠습니다. (간선의 수 = 정점의 수 -1)
2008년 1회 기출문제
제시된 [그림]은 최소 비용 그래프 G의 각 정점에 연결된 N-1개의 간선들의 가중치를 모두 합하여 정점1에서 N까지 이동에 소요되는 총 가중치의 합을 출력하는 순서도이다. <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항 보기>에서 선택하여 해당 번호 (1)~(5)에 마크하시오.
정점 1에서 N까지 이동하는 가중치 그래프 G가 있다.
정점 1에서 N까지 이동하는 가중치 그래프 G의 모든 간선의 개수는 X이며, 모든 간선에는 가중치가 주어져 있다.
각 간선들이 가중치를 정점과 정점 사이의 이동에 필요한 소요비용이라고 할 때, N개의 정점들에 연결된 총 X개의 간선의 가중치 Selection Sort를 이용하여 오름차순 정렬하고 정렬되어 있는 순서대로 가장 가중치가 작은 간선부터 사이클 없이 N-1개를 삽입하여 연결하면 최소비용 그래프 G를 완성할 수 있다.
<처리조건>
- 그림의 순서도에 제시되어 있는 미 완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 설계 시 유의하시오.
- 정점의 개수는 N이고, 간선의 개수는 X이다. (단, N>5, X>7)
- 배열 “Cost(X)”는 X개의 간선들의 가중치 값이 저장된다고 가정한다. (단, 가중치 값 중 동일 값은 없다고 가정한다.)
- 배열 “Cycle(X)”은 X개의 간선들 삽입에 따른 그래프의 사이클 여부를 체크한 값이 저장되어 있는 배열로서 간선 삽입 시 사이클이 형성될 경우는 1, 형성되지 않을 경우는 0의 값이 자동적으로 저장되어 있다고 가정한다.
글로 이해가 되지 않으신 분은 아래 영상을 보시면 좀더 이해하시는데 도움이 되실것 같습니다.
제 포스팅이 도움이 되셨다면
로그인이 필요없는 ↓♡공감↓ 꾸~욱 부탁드려요^^
더 나은 포스팅에 큰 힘이 됩니다.