알고리즘 기초 홍릉과학 출판사 4장 솔루션

소개

홍릉출판사 알고리즘 4장 2,3,7,10,12,13,19,22,26,28,29,35,37 솔루션

목차

없음

본문내용

10. 컴퓨터 네트워크에서 어떤 두 컴퓨터도 서로 연결될 수 있다고 가정하자. 각 링크간의 추정 비용이 주어진 상태에서 프림 알고리즘을 사용할지, 아니면 크루스칼 알고리즘을 사용할 지를 판정하시오. 그리고 왜 그런 답이 나오는지를 설명하시오.
프림 알고리즘을 사용한다. 왜냐하면 프림 알고리즘은 크루스칼의 알고리즘에서 요구되는 사이클의 조사가 필요 없다는 장점이 있다. 프림 알고리즘의 복잡성은 O(n×max(G))이다. 여기서 max(G) 는 한 노드에 연결된 최대 아크의 수이다. 만약, 최악의 경우인 완전 그래프를 대상으로 한다면, 복잡성은 O(n2) 이다.

<중 략>

35. 0-1 배낭 채우기 문제를 푸는 동적계획 알고리즘을 작성하시오.
최적의 원칙이 적용된다면 동적계획법으로 0-1 배낭채우기 문제를 풀 수 있다. A를 nro 아이템들 중에서 최적을 이루는 부분집합이라고 하면 A가 item을 포함하는 경우와 포함하지 않는 경우의 두 가지 경우로 나눌 수 있다. 만약 A가 item을 포함하고 있지 않다면, A는 처음 n-1개 아이템들 중에서 최적을 이루는 부분집합과 같다. 만약 A가 item을 포함하고 있다면, A에 속한 아이템들의 총 이익은 총 무게가 W-wn을 초과할 수 없다는 제약조건하에서 처음 n-1개 중에서 아이템들을 선택할 때 얻는 최적의 이익에다 pn을 더한 것과 같다. 따라서 최적의 원칙이 적용된다.

참고자료

· 없음