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

소개

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

목차

2. 좀 비현실적이기는 하지만 이분검색(알고리즘 2.1) 알고리즘을 사용하여 원소가 7억 개인 ... 없을 수도 있다.
4. n이 2의 거듭제곱이어야 한다는 제한을 풀면, 이분 검색(알고리즘 2.1) ... 같음을 증명하시오.
6. 원소가 n개인 정렬된 배열을 원소가 n/3개인 배열 3개로 분할(즉, 거의 같은 크기로 분할)하여 검색하는 알고리즘을 ... 분석결과를 차수 표기법으로 답하시오.
8. 합병정렬 알고리즘 2.2와 2.4를 사용하여 ... 단계별로 보이시오.
9. 연습문제 8에서 재귀 호출을 나무구조로 그리시오.
11. 재귀 호출이 없는 합병정렬(알고리즘 2.2와 2.4) 알고리즘을 작성하시오.
15. 아래 solve(알고리즘)을 살펴보자...
17. 하노이탑(Towers of Hanoi) 문제를 푸는 분할정복 알고리즘을 작성하시오...
18. 분할정복 알고리즘이 크기가 n인 문제의 입력사례를 n/c 크기로 분할할 때...
20. 연습문제 19의 실행과정에서 재귀 호출 나무구조를 그리시오.
28. 쉬트라쎈의 방법(알고리즘 2.8)을 사용하여 두 개의 64 X 64 행렬 ... 횟수는?
30. 알고리즘 2.10(큰 정수 곰셈 2)을 사용하여 1,253과 23,103의 곱을 구하시오.
37. 분할정복을 사용하여 n!을 계산하는 재귀 알고리즘을 작성하시오 ... 1을 위배하는가?
43. 다음 문제를 풀어보자...

본문내용

문제 2.
현재 문제에서는 원소가 배열에 있을 수도 있다고 하지만 없을 수도 있다고 한다.
즉, 최악의 상황을 가정해야 한다 = 원소가 배열에 존재하지 않는다..

<중 략>

문제 6.
문제: 원소가 n개인 정렬된 배열 S에 값 x가 어디에 있는가?
입력: 양의 정수 n, 비내림차순 정렬 배열 S(1부터 n까지), 검색대상 x
출력: location, S에서 x가 있는 위치(x가 없는 경우 0을 반환)

ndex location(index low, index high) {
index mid1, mid2;
if (low > high)
return 0; //찾지 못한경우 0을 반환
else {
mid1 = ; //나눈 3부분 중 첫 번째의 끝부분
mid2 = 2 * ; //나눈 3부분 중 두 번째의 끝부분
if (x == S[mid1]) //만약 1/3부분에서 값을 찾으면
return mid1; //위치를 알려준다.
else if (x == S[mid2]) //만약 2/3부분에서 값을 찾으면
return mid2; //위치를 알려준다.

참고자료

· 없음