안녕하세요? 조재환 회원님

정보처리 자격시험 온라인 강의, 최강! 기사친구 입니다.

회원님 질문에 답변 드리겠습니다.

최소비용 그래프 G의 가중치 합을 출력하는 알고리즘입니다.

먼저 이 문제의 정답부터 말씀드리면,

(1) - 7
(2) -24
(3) - 38
(4) - 11
(5) - 30 입니다.

그럼 알고리즘 설명을 하겠습니다.

이 알고리즘은 크게 두부분으로 구분되는데요?

첫번째는 간선의 가중치를 Selection Sort로 정렬하는 것이고,

두번째는 정렬된 간선의 가중치를 Cycle여부를 조사하며 가중치를 합하고 출력하는 것입니다.

( 중첩 반복문이 종료된 이후 부터 )

그런데 첫번재 간선의 가중치를 Selection Sort하는 것은

회원님께서도 충분히 유추하여 맞힐 수 있는 부분이라.

저는 회원님께서 의문을 가지는 두번째 가중치를 합하고 출력하는 부분만 설명드리겠습니다.

중첩 반복문 이후 분기문에 대해 설명해 드리면

먼저 L <= (n - 1)의 역할은 간선의 가중치를 더할때 종료조건으로 이용되는 분기문입니다.

L이 현재 누적한 간선의 가중치 개수를 나타내기 때문에 n개의 노드를 연결하려면

간선의 개수가 n-1개가 있어야하고, 따라서 L <= (n-1) 에서 no 로 분기된다는 말은

가중치를 모두 다 더했다는 말이 됩니다.

다음 CYCLE(k) = 0 은 사이클 여부를 조사하는 분기문입니다.

만약 간선이 CYCLE을 만든다면( CYCLE(k) = 1 ). 그 간선의 가중치는

아무리 COST가 낮더라도 가중치 누적연산에서 제외( no 로 분기 )되게 됩니다.

하지만 CYCLE을 만들지 않는다면( CYCLE(K) = 0, yes로 분기 )

가중치를 누적하고 연결된 간선의 개수를 1증가 합니다.

따라서 간선의 가중치를 누적해야 하므로 Min_tot = Min_tot + COST(K) 이고,

그러면 누적한 가중치 개수 L 은 1 증가 돼야 하기 때문에 L = L + 1 입니다.

마지막으로 K = K + 1이 되는 이유는 정렬된 가중치(COST(K))를 순서대로

CYCLE 여부를 체크하고 누적해야 하기 때문에 입니다.

이상 알고리즘 해설을 마치겠습니다.

그리고 추가로 이 알고리즘은 최단경로를 구하는 대표적인 알고리즘 중

Kruskal 알고리즘이라고 하는 것입니다. 기억해 두시면 나중에 도움이 될것입니다.

글로써 설명해서 좀 난해할 수도 있습니다. 의문점이 생기면 다시 글 남겨 주시기 바랍니다.^^

열공하시구요..

학습에 성실히 임하셔서 꼭 좋은 결과 있기를 기원하겠습니다. ^^

08년 1회 기사 기출문제를 보니 지금까지 배우지 않았던 가중치 그래프가 문제로 출제가 되었네요!

보는 순간 황당했습니다.

일단 순서도를 보고 1 , 2 은 유출했지만  3 , 4 , 5 번은 모르겠더라구요

그래서 일단 문제와 순서도만 계속 보고 머리를 굴리면서 풀어볼라구 했는데 전혀 모르겠네요~~~

샘 좀 알려주세요!!

머리에 속속 들어오게 가르쳐 주세요~~~

제가 지금 DB 강좌를 청취하면서 하루에 기출문제 3회씩 풀고 있거든요 앞으로 모의고사도 풀어야

합니다. 이제 28일 남았네요~~~

샘 부탁합니다.