01. 2개의 정수를 서로 교환하는 알고리즘을 의사 코드로 작성해보자.
swap(a, b)
temp <- a
a <- b
b <- temp
return (a, b);
02. 사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사 코드로 작성해보자.
max(a, b)
if a > b then
return a;
else
return b;
03. 1부터 n까지의 합을 계산하는 알고리즘을 의사 코드로 작성해보자.
sum(n)
n * ( n + 1) / 2;
04. set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라.
Create, Insert, Remove, Is_In, Union, intersection, Difference.
Create:= 집합을 생성하고 반환한다.
Insert(S, item):= 원소 item을 집합 S에 저장한다.
Remove(S, item):= 원소 item을 집합 S에서 삭제한다.
Is_In(S, item):= 집합 S에 item이 있는지 검사한다.
Union(S1, S2):= S1과 S2의 합집합을 구한다.
Intersection(S1, S2):= S1과 S2의 교집합을 구한다.
Difference(S1, S2):= S1과 S2의 차집합을 구한다.
05. Boolean 추상 자료형을 정의하고 다음과 같은 연산자들을 포함시켜라.
And, Or, Not, Xor
객체정의: 0 과 1
연산정의
And(a1, a2)
if a1 = 1 and a2 = 1 then return 1;
else return 0;
And(a1, a2) := a1이 1이고 a2가 1이면 1을 반환하고 아니면 0을 반환한다.
Or(a1, a2)
if a1 = 0 and a2 = 0 then return 0;
else return 0;
Or(a1, a2) := a1이 0이고 a2가 0이면 0을 반환하고 아니면 1을 반환한다.
Nor(a1)
if a1 = 0 return 1;
else return 0;
Nor(a1) := a1이 0이면 1을 반환하고 아니면 0을 반환한다.
Xor(a1, a2)
if (a1 = 0 and a2 = 0) or (a1 = 1 and a2 = 1) return 0;
else return 1;
Xor(a1, a2) := a1이 0이고 a2가 0이거나 a1이 1이고 a2가 1이면 0을 반환하고 아니면 1을 반환한다.
06. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 1; i < n; i*= 2))
printf("Hello");
O(log n)
i *= 2 이므로 n = 2^t 라고 가정할 수 있다.
총 t번의 연산을 하게 되므로
t=log2_n이 된다.
그러므로 O(log n)이 된다.
07. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 0; i < n' i++)
for(j = 1; j <n j *= 2)
printf("Hello");
O(n log n)
1. 안쪽 for문
안쪽 for문의 경우 j *= 2 이므로 n = 2^t 라고 가정할 수 있다.
따라서 총 t 번의 연산이 필요하므로
t = log2_n이 된다.
2. 바깥쪽 for문
i++ 이므로 총 n번의 연산이 필요하다
총 n번, log2_n번 연산을 진행하므로
O(n log n)이 된다.
08. 시간 복잡도 함수 n^2 + 10n + 8을 빅오표기법으로 나타내면?
(1) O(n) (2) O(n log2_n) (3) O(n^2) (4) O(n^2 log2_n)
(3) O(n^2)
빅오표기법은 가장 큰 차수에 영향을 받는 표기법이다. 가장 큰 차수가 n^2이므로
O(n^2)가 된다.
09. 시간 복잡도 함수가 7n + 10 이라면 이것이 나타내는 것은 무엇인가?
(1) 연산의 횟수 (2) 프로그램의 수행시간 (3) 프로그램이 차지하는 메모리의 양 (4) 입력 데이터의 총 개수
(1) 연산의 횟수
시간복잡도 함수는 연산의 수를 입력의 개수 n의 함수로 나타낸 것을 말한다.
10. O(n^2)의 시간 복잡도를 가지는 알고리즘에서 입력의 개수가 2배로 되었다면 실행시간은 어떤 추세로 증가하는가?
(1) 변함없다. (2) 2배 (3) 4배 (4) 8배
(3) 4배
O(n^2)이므로
입력의 개수가 n개일 경우는 n^2 연산이 필요하다.
입력의 개수가 2n일 경우는 4n^2 연산이 필요하다.
따라서 4배가 된다.
11. f(n)에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?
(1) 빅오메가 (2) 빅오 (3) 빅세타 (4) 존재하지 않는다.
(2) 빅오
빅오표기법: 가장 큰 차수에 영향을 받는 표기법
빅오메가표기법: 가장 작은 차수에 영향을 받는 표기법
빅세타표기법: 가장 큰 차수와 작은 차수에 영향을 받는 표기법
12. 다음의 빅오표기법들을 수행시간이 적게 걸리는 것부터 나열하라.
O(1) O(n) O(log n) O(n^2) O(n log 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 > 30, n < -30
14. 다음은 실제로 프로그램의 수행시간을 측정하여 도표로 나타낸 것이다. 도표로부터 이 프로그램의 시간 복잡도를 예측하여 빅오 표기법으로 나타내라.
| 입력의 개수 n | 수행시간 (초) |
| 2 | 2 |
| 4 | 8 |
| 8 | 25 |
| 16 | 63 |
| 32 | 162 |
O (n log n)
| 입력의 개수 n | 수행시간 (초) |
| 2 | 2 x 1 = 2 |
| 4 | 4 x 2 = 8 |
| 8 | 8 x 3 ≒ 25 |
| 16 | 16x 4 ≒ 63 |
| 32 | 32x 5 ≒ 162 |
이므로 O(n log n)이 된다.
15. 빅오표기법의 정의를 사용하여 다음을 증명하라.
5n^2 + 3 = O(n^2)
n > 1일 때, 다음이 성립한다.
0 ≤ 5n^2 + 0n + 3 ≤ 5n^2 + n^2 + 3n^2 ≤ 9n^2
따라서 5n^2 + 3 ∈ O(n^2) 이다.
16. 빅오표기법의 정의를 이용하여 6n^2 + 3n이 O(n)이 될 수 없음을 보여라.
17. 배열에 정수가 들어 있다고 가정하고 다음의 작업의 최악, 최선의 시간 복잡도를 빅오 표기법으로 말하라.
(1) 배열의 n번째 숫자를 화면에 출력한다.
(2) 배열 안의 숫자 중에서 최소 값을 찾는다.
(3) 배열의 모든 숫자를 더한다.
(1) 최선: O(1) 최악: O(1)
(2) 최선: O(1) 최악: O(n)
(3) 최선: O(n) 최악: O(n)
'컴퓨터교육 > C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 1장 자료구조와 알고리즘 간단 정리 (0) | 2023.02.03 |
|---|
댓글