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

소개글

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

목차

1. n개의 수로 구성된 ... 알고리즘을 작성하시오.
3. n개의 원소로 구성된 집합에서 3개의 원소를 ... 알고리즘을작성하시오.
5. 정수 2개의 ... 알고리즘을 작성하시오.
7. 거의 완전한 이진트리(almost complete binary tree)가 ... 알고리즘을작성하시오.
12. k를 양의 정수라고 하자. n개의 서로 다른 정수로 ... 알고리즘을 작성하시오.
14. 입력 크기가 n인 문제를 푸는 Alg1과 Alg2라는 두 개의 알고리즘이 있다. Alg1의 실행시간은 마이크로세컨드(1백만 분의 1초)이고... 몇 번 Alg2로 돌려야 개발을 정당화(개발비를 복구)할 수 있을까?
15. f(n)=n^2+3n^3 ... 모두 속함을 증명하시오.
18. p(n)=a_kn^k ... 증명하시오.
22. 다음 함수를 복잡도 카테고리별로 묶으시오.
25. 입력 크기가 n=1,000인 문제를 푸는데 1분이 ... 다음과 같을 때 각각 어떻게 될까?
28. 시간복잡도가 Ɵ(2^n)인 알고리즘 A를 사용하여 ... 이 문제를 해결할 수 있으리라 생각합니까?
34. 아래 중첩루프(nested loop)의 시간복잡도 T(n)은? ... 즉, 어떤 양의 정수 k에 대해서, n=2^k이다.
40. f(n)과 g(n)은 점근적으로 양의 함수라고 가정하고 다음을 증명하시오.

본문내용

문제 1.
문제 : 수가 n개인 배열 S에서 가장 큰 수를 찾으시오.
입력 : 정수 n(>0), 수의 배열 S(인덱스의 범위는 1부터 n까지)
출력 : ans, 배열 S에서 가장 큰 수

number max(int n, const number S[])
{
index i;
number ans = S[1];
for (i = 1; i <= n; i++)
if (S[i] > ans)
ans = S[i];
return ans;
}

<중 략>

문제 7.
문제 : 이진트리가 힙인지 확인하는 알고리즘
입력 : 이진 트리 S(인덱스는 1부터 n까지)
출력 : ans, 이진 트리가 힙인 경우 참을, 그렇지 않은 경우 거짓 출력

bool check(const keytype S[])
{
number a, count;
bool ans;
int num = node_count(S);
for (a = 1; a <= num; a++)
{
if (S[a] == NULL)
{
ans = false;
return ans;
}
//완전이진트리는 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있고
//마지막 레벨의 노드들은 가능한 왼쪽부터 채워져 있는 구조를 말한다.
//즉, 이 경우 배열의 처음부터 노드의 개수까지 NULL이 존재할 수 없으며
//있는 경우 이는 완전 이진 트리가 아니라는 것을 의미하며, 거짓을 바로 출력한다.

참고 자료

없음