17P Quiz
1. 문제를 풀기 위한 단계적인 절차는 알고리즘이다.
2. 알고리즘을 기술하기 위한 방법에는 자연어,흐름도,의사코드,프로그래밍 언어가 있다.
3. 알고리즘이 되기위한 조건이 아닌 것은? 4. 반복성
21P Quiz
1. 자료형 객체(object)와 이 객체간의 함수(operation)의 집합으로 정의된다.
2. ADT자료형(abstract data type)은 객체와 연산들의 명세가 구현으로부터 분리된 자료형을 말한다.
3. Nat_No 추상 자료형에 is_greater(x,y) 연산을 추가하여 보자.
is_greater(x,y) ::= if(x>y) return TRUE;
else return FALSE;
1) 2개의 정수를 서로 교환하는 알고리즘을 의사 코드로 작성해보자.
swap(a, b)
temp <- a
a <- b
b <- temp
return (a, b);
2. 사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사코드로 작성해보자.
max(a, b)
if a > b then
return a;
else
return b;
3. 1부터 n까지의 합을계산하는 알고리즘을 의사 코드로 작성해보자.
sum(n)
n * (n + 1) / 2; // 시그마 공식
4. Set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라.
Create, Insert, Remove, Is_In, Union, Intersection, Difference
Create: 집합을 생성하고 반환한다.
Insert: 집합에 원소를 추가한다.
Remove: 집합에 원소를 제거한다.
Is_In: 집합에 해당 원소가 있는 지 확인한다.
Union: 두 집합의 합집합을 구한다.
Intersection: 두 집합의 교집합을 구한다.
Difference: 두 집합의 차집합을 구한다.
5. Boolean 추상 자료형을 정의하고 다음과 같은 연산자들을 포함시켜라.
And, Or, Not, Xor
And(A1, A2)
if A1 = 1 and A2 = 1 then return 1;
else return 0;
Or(A1, A2)
if A1 = 0 and A2 = 0 then return 0;
else return 1;
Nor(A)
if A = 0 return 1;
else return 0;
Xor(A1, A2)
if (A1 = 1 and A2 = 1) or (A1 = 0 and A2 = 0) return 0;
else return 1;
6. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(int i; i < n; i*=2)
printf("Hello");답: O(log 2)
7. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 0; i < n; i++)
for(j = 1; j < n; j*=2)
printf("Hello");답: O(n log n)
8. 시간 복잡도 함수 n^2 + 10n + 8을 빅오 표기법으로 나타내면?
(1) O(n)
(2) O(n log_2n)
(3) O(n^2)
(4) O(n^2 log_2n)
답: (3) O(n^2)
9. 시간 복잡도 함수가 \( 7n+10 \)이라면 이것이 나타내는 것은?
(1) 연산의 횟수
(2) 프로그램의 수행 시간
(3) 프로그램이 차지하는 메모리의 양
(4) 입력 데이터의 총 개수
답: (1) 연산의 횟수
10. O(n^2)의 시간복잡도를 가지는 알고리즘에서 입력의 개수가 2배가 되었다면 실행시간은 어떤 추세로 증가하는가?
(1) 변함없다.
(2) 2배
(3) 4배
(4) 8배
답: (3) 4배
11. f(n)에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?
(1) 빅오메가
(2) 빅오
(3) 빅세타
(4) 존재하지 않는다.
답: (2) 빅오
12. 다음의 빅오표기법들을 수행시간이 적게 걸리는 것부터 나열하여라.
O(n), O(1), O(log n), O(n^2), O(nlong n), O(n!), O(2^n)
답: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
13. 두 함수 30n+4와 n^2를 여러 가지 n값으로 비교하라. 언제 30n+4가 n^2 보다 작은 값을 갖는지를 구하여라. 그래프를 그려보라.
답: n ≥ 31 이면 30n + 4 < n^2
14. 다음은 실제로 프로그램의 수행시간을 측정하여 도표로 나타낸 것이다. 도표로부터 이 프로그램의 시간복잡도를 예측하여 빅오 표기법으로 나타내라.
| 입력의 개수(n) | 수행시간 (초) |
| 2 | 2 |
| 4 | 8 |
| 8 | 25 |
| 16 | 63 |
| 32 | 162 |
답: O(n log n)
15. 빅오표기법의 정의를 사용하여 다음을 증명하라.
5n^2 + 3 = O(n^2)
답: n ≥ 1 인 경우 5n^2 + 3 ≤ 1000n^2이면 O(n^2) 이다.
16. 빅오 표기법의 정의를 이용하여 6n^2+3n이 O(n)이 될 수 없음을 보여라.
답: n > n0 일때 6n^2 + 3n < c*n을 만족하는 n0과 c를 찾을 수 없다.
17. 배열에 정수가 들어 있다고 가정하고 다음의 작업의 최악, 최선의 시간복잡도를 빅오 표기법으로 말하라.
(1) 배열의 n번째 숫자를 화면에 출력한다.
(2) 배열안의 숫자 중에서 최소값을 찾는다.
(3) 배열의 모든 숫자를 더한다.
답
(1) 최선: O(1), 최악: O(1),
(2) 최선: O(1), 최악: O(n),
(3) 최선: O(n), 최악: O(n)
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 2장 핵심정리를 가져오도록 하겠습니다.