알고리즘 기초 연습문제 4장 해설

소개글

1. 본 파일의 정답 및 해설은 공식 정답이 아닌 직접 풀어서 작성한 것이며 오타, 오답 및 프로그램에 버그가 존재할 수 있으므로 반드시 확인하시길 바랍니다.
2. 간단한 문제는 해설이 생략되었을 수 있습니다.
3. 프로그램의 설명은 주석을 참조하시길 바랍니다.
4. 작성자가 과제로 지정된 문제의 해설만을 작성한것으로 일부 문제가 누락되었을 수 있습니다. 본문내용의 포함된 문제를 반드시 확인하시길 바랍니다.

목차

2. 프림 알고리즘(알고리즘 4.1)을 이용하여 ... 보이시오.
3. 다음 배열을 보고 아래 물음에 답하시오.
7. 크루스칼 알고리즘(알고리즘 4.2)을 사용하여 ... 보이시오.
10. 컴퓨터 네트워크에서 어떤 두 컴퓨터도 서로 ...설명하시오.
12. 다익스트라 알고리즘(알고리즘 4.3)을 사용하여 ... 보이시오.
13. 다익스트라 알고리즘(알고리즘 4.3)을 사용하여 ... 가정하시오.
19. 다음 작업과 작업 시간을 가지고, 4.3.1절에 있는 알고리즘을 ... 최소화하시오.
22. 다음 작업, 마감시간, 보상을 가지고, 마감시간이 있는 ... 최대화하시오.
26. 허프만의 알고리즘을 ... 구축하시오.
28. 연습문제 26의 이진코드를 ... 복코드화하시오.
29. 연습문제 27의 이진코드를 ... 코드화하시오.
35. 0-1 배낭 채우기 ... 작성하시오.
37. n명의 작업자를 n개 작업에 배치했다고 ... 그 결과를 차수표기법을 사용하여 표시하시오.

본문내용

문제 7.
크루스칼 알고리즘은 프림 알고리즘과는 다르게 시작점이 설정되어있지 않다.
전체적으로 보고 그 중에서 비용이 가장 적은 간선을 선택해 계속 연결하며 이때 사이클을 형성하지 않게 하고 간선의 개수가 n-1개이면 종료한다.

문제 10.
프림 알고리즘이 적합하다고 생각한다.
컴퓨터 네트워크에서 사용되는 통신은 송신자와 수신자가 명확하게 정해져 있다.
송신자 노드를 기반으로 프림 알고리즘을 이용하여 만들어 냄으로써 송신자 위치에서 시작하여 빠른 루트(=간선)들을 선택할 수 있다. 또한, 현재 사용되는 네트워크에는 무수히 많은 컴퓨터가 연결되어 있다. 다른 말로 현세대 네트워크는 상당히 복잡하다는 의미이다.
크루스칼 알고리즘은 적은 숫자의 간선을 가지는 희소 그래프에 적합하며 프림 알고리즘은 그래프에 간선이 많이 존재하는 밀집 그래프에 적합하다.
따라서 수많은 노드와 간선이 존재하는 네트워크에서는 프림 알고리즘이 적합하다.

문제 12.
연습문제 3의 배열이 나타내는 그래프는 다음과 같다:
단계별로 진행하는 과정은 다음과 같다:

참고 자료

없음