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

소개

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

목차

2. 등식 (3.1)을 기초로 하여 이항계수 문제(알고리즘 3.1)를 ... 증명하시오.
4. 알고리즘 3.2(동적계획법으로 이항계수 구하기)를 ... 수정하시오.
5. 최단경로 문제를 푸는 플로이드 알고리즘2(알고리즘 3.4)를 사용하여 ... 단계별로 보이시오.
6. 최단경로출력 알고리즘(알고리즘 3.5)을 사용하여 ... 단계별로 보이시오.
13. 다음 행렬들의 곱인 ... 구하시오.
15. 본문의 식 (3.5)를 기초로 작성한 ... 증명하시오.
17. 다음 등식이 성립하도록 유도하시오.
20. 임의의 양의 정수 d에 대해서 각 행렬의 크기가 또는 ... 표시하시오.
22. 다음 아이템에 대해서 최적 이분검색트리를 ... 나타낸다.
26. 검색키가 트리에 없을 수도 있는 경우도 포함하도록 최적 이분검색트리 알고리즘(알고리즘 3.9)을 ... 표기하시오.
28. 다음과 같이 행렬 W로 표현되어 있는 가중치포함 방향그래프에서 ... 보이시오.
36. n개의 원소로 구성된 이분검색트리의 ... 증명하시오.

본문내용

알고리즘 기초

3장. 동적 프로그래밍

문제 2. 을 계산하기 위한 항의 개수는 이라고 가정한다.

이항계수를 구하는데 통상 다음의 재귀 관계식을 이용한다.

해당 식에 따르면 를 계산하기 위한 항의 총 개수는 을 계산하기 위한 총 개수, 를 계산하기 위한 항의 총 개수 그리고 이들을 더하기 위한 항 개수 1이다. 즉, = 문제 4.

index i,j; int B[0...k]; B[0]=1; //첫 인덱스는 항상 값이 1이다 for(i=0;i<=n;i++) { for(j=min(i,k);j>=0;j--) { if(j==i) B[j]=1; else B[j]=B[j]+B[j-1]; } return B[k]; } //그렇지 않으면 이전값을 이용해 새로운 값을 저장한다 //끝 원소이면 1을 입력한다 //2차원일 때는 앞에서 작업하였으나 1차원은 뒤에서 시작한다 = 이 나온다.

= 기존 2차원 배열을 사용했을 때 윗 행의 데이터를 불러와 새로운 행에 데이터를 쓰는 방식이었다. 1차원 배열의 경우에는 행이 1개만 존재하기 때문에 그러한 작업을 할 수 없다. 이러한 경우 새로운 행에 데이터를 쓰는 것이 아닌 기존의 행에 데이터를 덮어쓰는 방식이다. 맨 앞의 원소 B[0]는 1이므로 초기에 바로 1을 입력해준다(값이 변하지 않음). 나머지는 B[j]=B[j]+B[j-1]을 통해 값을 더하고 새로운 값을 저장한다. 만일 순서를 앞에서 하는 경우 이전에 저장된 값이 사용되기 전 덮어써지기 때문에 앞에서 진행하는 방식은 사용할 수 없다.

문제 5. 행렬을 작성하는 방법은 다음과 같다. 행렬을 작성하는 경우 요소 는 이다.
행렬 D 완성 위 과정을 토대로 업데이트 된 항목을 찾아 행렬 P를 작성할 수 있다.

문제 6. 5번에서 구한 행렬 P는 다음과 같다.

정점에서 으로 가는 것을 찾기 위해서는 위 행렬을 참고한다.

→ 5가 나온 사실을 기억하며 다음 탐색에 활용한다. → 4가 나온 사실을 기억하며 다음 탐색에 활용한다. → 0이 나왔으며 더이상 탐색을 할 수 없다. 이 결과를 0을 제외 후 역순으로 배치하면 최단 경로를 구할 수 있다. 따라서 경로는 → → → 이다.

참고자료

· 없음