*길* 스토어

*길*

개인인증

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

10개
전체 판매량

940개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 10개

알고리즘 기초 탐욕 알고리즘 연습문제 레포트 평가A+최고예요

2015/1 『알고리즘』 과제 보고서학번이름제출일자제목4장 탐욕 알고리즘 연습문제2. 프림 알고리즘(알고리즘 4.1)을 이용하여 다음 그래프의 최소비용 신장트리를 구하시오. 그리고 수행되는 절차를 단계별로 보이시오.v1v3v4v5v6v7v8v9v10v232*************2528612초기 W행렬v1v2v3v4v5v6v7v8v9v10v1032∞17∞∞∞∞∞∞v2320∞∞45∞∞∞∞∞v3∞∞018∞∞5∞∞∞v417∞18010∞∞3∞∞v5∞45∞10028∞∞25∞v6∞∞∞∞280∞∞∞6v7∞∞5∞∞∞059∞∞v8∞∞∞3∞∞5904∞v9∞∞∞∞25∞∞4012v10∞∞∞∞∞6∞∞120초기 distance 행렬을 모두 1로 초기화 시킨다.처음 정점은 v1에서 시작한다. v1에서 인접한 정점인 v2 , v4 중에 가장 짧은 거리인 v4를 택하고, distance 행렬을 v1에서 v4를 거쳐 가는 거리와 v1에서 곧바로 가는 거리 중 최솟값으로 갱신 시킨다. 그렇게 생신된 정점에서의 거리가 가리가 가장 낮은 정점을 택하여 위의 방식을 반복한다. 그렇게 해서 얻어진 경로는 아래와 같다.v1v3v4v5v6v7v8v9v10v2*************23. 다음 배열을 보고 아래 물음에 답하시오.12345610∞725090352∞7*************00∞779045073∞060*************06359040800->12345610∞725090352∞*************10∞779045070∞060*************0635759040800-> 책에 나와 있는 배열에서 2번의 행과 2번의 열의 입력과정에서 (2,2) 성분에 0을 넣지 않고 2번 열을 입력 했다고 판단되어 나름대로 오류를 수정하여 시행하였다.(a) 마디 v4 에서 시작하여 프림 알고리즘을 적용하여 위 배열이 표현하는 그래프의 최소비용 신장 트리를 찾으시오.초기 distance 배열12345645073∞06040가장 가까운 4번 정점을 선택. 4번 정점을 추가 시켜 distance 배열 갱신하고 4번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.12345645073130-16040가장 가까운 6번 정점을 선택. 6번 정점을 추가 시켜 distance 배열 갱신하고 6번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.12345645073130-160-1가장 가까운 1번 정점을 선택. 1번 정점을 추가 시켜 distance 배열 갱신하고 1번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.1234564-173122-160-1가장 가까운 5번 정점을 선택. 5번 정점을 추가 시켜 distance 배열 갱신하고 1번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.1234564-173122-1-1-1가장 가까운 2번 정점을 선택. 2번 정점을 추가 시켜 distance 배열 갱신하고 1번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.1234564-1-1122-1-1-1가장 가까운 3번 정점을 선택. 3번 정점을 추가 시켜 distance 배열 갱신하고 3번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.1234564-1-1-1-1-1-1그렇게 해서 얻어진 신장트리는 다음과 같다.v2v3v5v4v6v15070726040(b) 최소비용 신장 트리를 이루는 이음선의 집합을 보이시오.E` = { (v1 , v3) , (v1 , v4) , (v2 , v4) , (v4 , v5) , (v4 , v6) }(c) 최소비용 신장 트리의 비용은 얼마인가?72 + 50 + 40 + 60 + 70 = 29212. 다익스트라 알고리즘(알고리즘 4.3)을 사용하여 연습문제 3의 배열이 나타내는 그래프에서 마디 v5에서 다른 모든 마디로 가는 최단경로를 구하시오. 그리고 수행되는 절차를 단계별로 보이시오.초기 distance 배열1234*************0가장 가까운 5번 정점을 선택. 5번 정점을 추가 시켜 distance 배열 갱신하고 5번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.123456590737760-180가장 가까운 4번 정점을 선택. 4번 정점을 추가 시켜 distance 배열 갱신하고 4번 정점에 대한 값을-1로 변환 시켜 더 이상 접근하지 못하도록 설정.1234565907377-1-180위와 같은 작업을 반복 수행 하여 얻어진 결과최단경로는 다음과 같다.v2v3v5v4v6v19080737760v5 정점에서 출발하는 경우 어느 정점 하나 거치지 않고 모두 v5 정점에서 가도록 되어있다.총 거리는 (90 + 73 + 77 + 80) * 2 + 60 = 700(v5 정점에서 어느 한 정점을 들렸다가 다시 v5 정점으로 돌아와 다시 다른 정점을 들리기를 반복하고 마지막에 가장 최단경로의 정점으로 가면서 종료)19. 다음 작업과 작업시간을 가지고, 4.3.1 절에 있는 알고리즘을 사용하여 시스템에서 소요된 총 시간을 최소화 하시오.작업작업시간172331045소요된 총 시간을 최소화 시키기 위해선 작업시간이 가장 낮은 작업에 대해서 우선순위를 높게 준다.즉 작업의 순서를 2 -> 4 -> 1 -> 3 순으로 수행한다. 이때 작업시간은3 + (3 + 5) + (3 + 5 + 7) + (3 + 5 + 7 + 10) = 51 이다.22. 다음 작업, 마감시간, 보상을 가지고, 마감시간이 있는 스케줄 짜기 알고리즘(알고리즘 4.4) 을 사용하여 총 보상을 최대화하시오.작업마감시간보상*************2*************5먼저 보상이 가장 높은 순으로 배열을 다시 작성한다.작업마감시간보상3**************************0이렇게 작성된 배열에서 보상순으로 작업을 입력하는데, 마감시간이 곂치지 않도록 선택한다.즉 보상이 가장 높고 마감시간이 3인 작업 3을 선택하고, 그다음으로 마감시간이 1이면서 보상이 가장 높은 작업 7 , 마감시간이 2이면서 보상이 가장 높은 작업 1 , 마지막으로 마감시간 4인 작업 2를 선택한다. 즉, 최종 선택된 작업의 집합은 S = { 3 , 7 , 1 , 2 } 가 되고, 이 작업의 적절한 순서는마감시간 순으로 작업7 -> 작업1 -> 작업3 -> 작업2 가 된다.26. 허프만의 알고리즘을 사용하여 다음 표에 있는 글자들에 대한 최적 이진전치 코드를 구축하시오,글자 :ABIMSXZ빈도수 :1271810952빈도수에 따른 우선순위큐를 만든다.글자 :ZXBSMAI빈도수 :2579101218여기서 앞의 두 개의 배열을 뽑아서 빈도수를 합친 뒤 트리를 만들고 새로운 우선순위큐를 갱신한다.글자 :BZ+XSMAI빈도수 :779101218752갱신된 큐를 이용하여 반복한다.글자 :SMAZ+X+BI빈도수 :*************52글자 :AZ+X+BIS+M빈도수 :*************147752글자 :IS+MA+Z+X+B빈도수 :*************75210919글자 :A+Z+X+BI+S+M빈도수 :*************2글자 :A+Z+X+B+I+S+M빈도수 :63101837919A263714B7XZMS19I3728. 연습문제 26의 이진코드를 사용하여 각 비트문자열을 복코드화 하시오.(a) *************0-> 0110/00/10/10/10/10-> ZAIIII(b) 10001000001010-> 10/00/10/00/00/10/10-> IAIAAII(c) 11100100111101-> 111/00/10/0111/10/1(?)-> MAIXI(1?)(d) 10000100011100-> 10/00/010/00/111/00-> IABAMA35. 0-1 배낭 채우기 문제를 푸는 동적계획 알고리즘을 작성하시오.알고리즘 확인을 위해 책 4.5.1 절에 있는 예제를 이용하였다.#includevoid knapsack(){int W[4] = { 0, 5, 10, 20 };int P[4] = { 0, 50, 60, 140 };int p[4][31];int w[4] = { 0, 0, 0, 0 };int i, j;for (i = 0; i

공학/기술| 2015.07.13| 9페이지| 1,000원| 조회(1,120)

알고리즘, 홍릉과학출판사, 알고리즘 기초, 도경구, Richard Neapoli..

미리보기

닫기
알고리즘 기초 합병정렬과 이진탐색을 이용한 배열 탐색 레포트

C 소스 코드#define _CRT_SECURE_NO_WARNINGS#include "stdio.h"int low = 0;int high = 50;void merge2(int low, int mid, int high, int S[]){int i, j, k, l, b[50];i = l = low;j = mid + 1;while ((l <= mid) && (j <= high)){if (S[l] == S[j]){b[i] = S[l];b[i + 1] = S[j];l++; j++; i++;}else if (S[l] < S[j]){b[i] = S[l];l++;}else if (S[l] > S[j]){b[i] = S[j];j++;

공학/기술| 2015.07.13| 4페이지| 1,000원| 조회(223)

알고리즘, 홍릉과학출판사, 알고리즘 기초, 도경구, Richard Neapoli..

미리보기

닫기
알고리즘 기초 분할정복 연습문제 레포트 평가B괜찮아요

2015/1 『알고리즘』 과제 보고서학번이름제출일자제목2장 분할정복 연습문제2. 좀 비현실적이기는 하지만 이분검색(알고리즘 2.1) 알고리즘을 사용하여 원소가 7억 개인 배열을 검색한다고 가정해보자. 특정 원소를 찾기 위해서 비교를 최대로 몇 번해야 할까? 특정 원소가 배열에 있을 수도 있고 없을 수도 있다.- 알고리즘 2.1을 사용하였다 는 것으로 보아 배열이 정렬 되었다고 가정한다.워스트 케이스로 계산시 W(n) = lg(n)의 하한 + 1 이므로lg9억 = 29.7453497605 이기 때문에 하한은 29 이고 +1 을 해주면 30 이다.결국 최대 30번의 수행을 하면 된다.결론 : 이진탐색은 정렬된 배열에서 아주 좋은 효율을 보여준다.6. 원소가 n개인 정렬된 배열을 원소가 n/3개인 배열 3개로 분할(즉, 거의 같은 크기로 분할)하여 검색하는 알고리즘을 작성하시오. 이 알고리즘은 분할한 세 배열 중에서 찾을 원소가 있을만한 배열에서 원소를 검색하는데, 이 배열을 다시 거의 같은 크기의 배열 3개로 분할한다. 원소를 찾거나, 원소가 배열에 없음이 확실할 때까지 이 과정을 되풀이한다. 이 알고리즘을 분석하고, 분석결과를 차수 표기법으로 답하시오.int low = 0, high = n, S[n]; (n은 임의의 수)mergesort(int low, int high, int S[]){int onebythree = (low + high) / 3;int twobythree = (low + high) * 2 / 3;mergesort(low , onebythree,S);mergesort(onebythree +1 , twobythree, S);mergesort(twobythree +1 , high, S);merge(low, onebythree, twobythree, high, S);}merge(int low, int onebythree, int twobythree, int high,int S[]){int i,j,k,l;int B[high];i = low; j= onebythree+1; k=twobythree+1; z=0;while(i

공학/기술| 2015.07.13| 8페이지| 1,000원| 조회(1,713)

알고리즘, 홍릉과학출판사, 알고리즘 기초, 도경구, Richard Neapoli..

미리보기

닫기
알고리즘 기초 분기한정법 연습문제 레포트 평가A+최고예요

2015/1 『알고리즘』 과제 보고서학번이름제출일자제목6. 분기한정법 연습문제 풀이4. 알고리즘 6.2 (0-1 배낭 채우기 문제를 푸는 분기한정 가지치기 최고우선검색 알고리즘)를 사용하여연습문제 1의 문제 사례에 대한 이익을 최대화 하시오. 알고리즘 수행 절차를 단계별로 보이시오ipiwipi/wiW = 131$ 202102$ 30563$ 35754$ 12345$ 3131. 마디 (0.0)(뿌리마디)를 방문한다.(a) 이익과 무게를 $0과 0으로 놓는다.(b) 한계값을 계산하면, $80이 된다.(c) maxprofit을 0 으로 놓는다.2. 마디 (1.1)을 방문한다.(a) 이익과 무게를 계산하면 $20과 2가 된다.(b) 무게 2는 W의 값 13보다 작거나 같고, 이익 $20 은 $0 보다 크므로 maxprofit의 값을 $20(c) 한계값은 $80 이 된다.3. 마디 (2.1)을 방문한다.(a) 이익과 무게를 계산하면 $50 과 7이 된다.(b) 무게 7은 W의 값 13보다 작거나 같고, 이익 $50 은 $20 보다 크므로 maxprofit의 값을 $50(c) 한계값은 $80 이 된다.4. 마디 (3.1)은 W의 값 13을 초과 하므로 유망하지 않다.5. 마디 (2.2)를 방문한다.(a) 이익과 무게를 계산하면 $20과 2가 된다.(b) 이익 $20은 현재 maxprofit의 값인 $50보다 작으므로 maxprofit 값 유지(c) 한계값은 $70 이 된다.6. 마디 (3.3)을 방문한다.(a) 이익과 무게를 계산하면 $55과 9가 된다.(b) 무게 9는 W의 값 13보다 작거나 같고, 이익 $55 은 $50 보다 크므로 maxprofit의 값을 $55(c) 한계값은 $70 이 된다.7. 마디 (4.5)를 방문한다.(a) 이익과 무게를 계산하면 $67과 12가 된다.(b) 무게 12는 W의 값 13보다 작거나 같고, 이익 $67 은 $55 보다 크므로 maxprofit의 값을 $67(c) 한계값은 $70 이 된다.8. 마디 (5.9)를 방문한다.(a) 이익로 가지친다.11. 더 이상 방문할 노드가 없어 현재 구해진 maxprofit 값인 70이 최대 이득이다.5. 알고리즘 6.2를 구현하는 프로그램을 작성하고, 연습문제 1의 문제 사례로 실행시켜 보시오.#include#include#define MAX_ELEMENT 10int W = 13;int n = 5;int p[6] = { 0, 20, 30, 35, 12, 3 };int w[6] = { 0, 2, 5, 7, 3, 1 };typedef struct{int level;int profit;int weight;int path;float bound;}node;typedef struct{node heap[MAX_ELEMENT];int heap_size;}HeapType;void insert(HeapType *h, node item){int i;h->heap_size++;i = h->heap_size;while ((i != 1) && (item.bound > h->heap[i / 2].bound)){h->heap[i] = h->heap[i / 2];i /= 2;}h->heap[i] = item;}node delete(HeapType *h){int parent, child;node item, temp;item = h->heap[1];temp = h->heap[(h->heap_size)];h->heap_size--;parent = 1;child = 2;while (child heap_size){if ((child < h->heap_size) && (h->heap[child].bound) < (h->heap[child + 1].bound))child++;if (temp.bound >= h->heap[child].bound) break;h->heap[parent] = h->heap[child];parent = child;child *= 2;}h->heap[parent] = temp;return item;}bool empty(HeapType *h){bool switch_;sw02$808$00$69아이템2 [$30,5] 3$507$804$202$70아이템3 [$35,7] 9$507$655$559$70아이템4 [$12,3] 6$6712$70아이템5 [$3,1] 7$7013$707. 알고리즘 6.3(외판원 문제를 푸는 분기한정 가지치기 최고우선검색 알고리즘)을 사용하여 아래 그래프에 대하여 최적 여행경로와 그 경로의 길이를 구하시오.알고리즘 수행 절차를 단계별로 보이시오.v1v2v3v4v5v6v7v*************27(교재의 그래프에서 v7->v4 가중치가 7과 3으로 표현되어 있는 것 중에 3을 생략하였다.)#include#include#define MAX_ELEMENT 20#define m 100int n = 8;int W[9][9] = { m, m, m, m, m, m, m, m, m,m, 0, 5, 8, m, m, m, m, m,m, m, 0, 4, m, 4, m, m, m,m, m, m, 0, 2, m, m, 5, m,m, m, m, m, 0, m, m, m, 7,m, 1, m, m, m, 0, m, m, m,m, m, 6, m, m, 2, 0, m, m,m, m, m, m, 7, m, 8, 0, m,m, m, m, m, m, m, 5, 4, 0 };typedef struct{int level;int path[10];int bound;}node;typedef struct{node heap[MAX_ELEMENT];int heap_size;}HeapType;void insert(HeapType *h, node item){int i;h->heap_size++;i = h->heap_size;while ((i != 1) && (item.bound < h->heap[i / 2].bound)){h->heap[i] = h->heap[i / 2];i /= 2;}h->heap[i] = item;}node delete(HeapType *h){int parent, child,i;node item, temp;item = h->heap[1];t true;return switch_;}void init(HeapType *h){h->heap_size = 0;}int bound(node u){int result_bound = 0;int min = m;int i, j;int check[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };if (u.level == 0){for (i = 1; i v5->v1 length = 363. v1->v3->v4->v8->v7->v6->v2->v5->v1 length = 404. v1->v3->v7->v4->v8->v6->v2->v5->v1 length = 39이므로 첫 번째 경로인 v1->v2->v3->v4->v8->v7->v6->v5->v1 이 가장 최적의 경로이다.9. 알고리즘 6.3에서 사용한 함수 length 와 bound를 작성하시오.int bound(node u){int result_bound = 0;int min = m;int i, j;int check[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };if (u.level == 0){for (i = 1; i 까지 확정이고 거리는 W[v1][v5] + W[v5][v3] + W[v3][v2] 이 확정된다. 그리고 v2 는 선택된 정점 v5, v3을 제외하고 시작정점인 v1을 제외한 나머지 정점간의 거리 중 가장 가까운 정점을 선택하여 거리를 계산하고, 선택되지 않은 정점들은 이미 선택된 v5, v3, v2를 제외한 나머지 정점간의 거리의 최솟값을 합한다.※ length 함수는 선택된 경로의 길이를 구해준다. 여기서는 끊어진 경로가 많아서 마지막 정점까지 경로가 구해져야 비로소 minlength 이하 값으로 도달한다.14. 예제 6.4에서 질병들이 조건부 확률이 높은 것부터 차례로 정렬되어 있다면, 검사하는 마디의 수가 15가 아니고, 23이 됨을 보이시오.p(d_4 ) = 0.008 이고,p(d_4 ,``d_1 )`=`0.007 이라고 가정한다.1. 마디를 방문한다. (count = 1nt = 6)(a) p(d2|S) = 0.15 bound = 0.5(b) bound = 0.5 인 큐- 오른쪽 마디 (count = 7)(a) p(?|S) = 0.1 bound = 90(b) bound = 90 인 큐5. bound = 90 디 큐- 왼쪽 마디 (count = 8)(a) p(d3|S) = 0.1 bound = 0- 오른쪽 마디 (count = 9)(a) p(?|S) = 0.1 bound = 06. bound = 0.9 디 큐 (count = 10)- 왼쪽 마디(a) p(d1,d2|S) = 0.1 = bound = 0.3(b) bound = 0.3 인 큐- 오른쪽 마디 (count = 11)(a) p(d1|S) = 0.4 bound = 0.9(b) bound = 0.9 인 큐7. bound = 0.9 디 큐- 왼쪽 마디 (count = 12)(a) p(d1,d3|S) = 0.001 bound = 0- 오른쪽 마디 (count = 13)(a) p(d1|S) = 0.4 bound = 08. bound = 0.8 디 큐- 왼쪽 마디 (count = 14)(a) p(d4,d1|S) = 0.65 bound = 0.7(b) best = 0.65(c) bound = 0.7 인 큐- 오른쪽 마디 (count = 15)(a) p(d4|S) = 0.6 bound = 0.8(b) bound = 0.8 인 큐9. bound = 0.8 디 큐- 왼쪽 마디 (count = 16)(a) p(d4,d2|S) = (알 수 없음) bound = (알 수 없음)(b) bound = (알 수 없음) 인 큐- 오른쪽 마디 (count = 17)(a) p(d4|S) = 0.6 bound = 0.8(b) bound = 0.8 인 큐10. bound = 0.8 디 큐- 왼쪽 마디 (count = 18)(a) p(d4,d3|S) = (알 수 없음) bound = 0- 오른쪽 마디 (count = 19)(a) p(d4|S) = 0.6 bound = 011. bound = 0.7 디 큐- 왼쪽 이고,

공학/기술| 2015.07.13| 15페이지| 1,000원| 조회(1,088)

알고리즘, 홍릉과학출판사, 알고리즘 기초, 도경구, Richard Neapoli..

미리보기

닫기
알고리즘 기초 동적계획 연습문제 레포트 평가A좋아요

2015/1 『알고리즘』 과제 보고서학번이름제출일자제목3장 동적계획 연습문제2 . 등식 (3.1)을 기초로 하여 이항계수문제(알고리즘 3.1)을 푸는 분할정복 알고리즘은 nCk 를 구하는데 2*nCk ? 1 개의 항을 계산함을 n에 관한 귀납법으로 증명하시오.먼저 n = 1 인 경우 1Ck = 2 * 1Ck ? 1 임 을 증명하면 된다.1Ck 인 경우 k는 0 또는 1 인데 두 가지 경우 다 1 을 나타내므로 위에 등식은1 = 2 ? 1 이 되므로 성립한다.다음으로 nCk 에 대하여 2*nCk ?1 개의 항을 계산 한다고 가정 하였으므로(n+1)Ck 에 대하여 2*(n+1)Ck ?1 이 성립 되는지 알아보면 된다.여기서 이항계수 성질 중에 nCk = (n-1)C(k-1) + (n-1)Ck 라는 식이 성립 되므로우리는 nC(k-1) 을 구하기 위한 항의 갯수와 + nCk 을 구하기 위한 항의 갯수에 두개의 항을 더하기 위한 항의 갯수 1 을 더하는 횟수를 구하면 된다. 그럼 여기에 가정을 대입하면nC(k-1) = 2 * nC(k-1) - 1 , nCk = 2 * nCk - 1 이므로(n+1)Ck = 2 * nC(k-1) -1 + 2 * nCk ?1 +1 이 성립되어야 한다.이것을 계산하면 2 * ( n!/(k-1)!(n-k+1)! + n!/k!(n-k)! ) -1= 2 * ( (n!k + n!(n-k+1)) / k!(n-k+1)! ) - 1= 2 * ( n!(k + n ? k + 1) / k!(n-k+1)! ) - 1= 2 * ( (n+1)! / k!(n-k+1) ) - 1= 2 * (n+1)Ck ? 1이것으로 n+1 에 대해서도 성립된다는 것이 증명이 되었다.3 . 이항계수문제를 푸는 두 알고리즘(알고리즘 3.1과 3.2)을 모두 구현하는 프로그램을 작성하고, 다양한 문제 사례를 가지고 성능을 비교하시오.#include int minimum(int n, int k){if (n < k) return k;else return n;}int bin(int n, int k){if (k == 0 || n == k)return 1;elsereturn bin(n - 1, k - 1) + bin(n - 1, k);}int bin2(int n, int k){int i, j;int B[500][500];for (i = 0; i

공학/기술| 2015.07.13| 12페이지| 1,000원| 조회(1,031)

알고리즘, 홍릉과학출판사, 알고리즘 기초, 도경구, Richard Neapoli..

미리보기

닫기