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(a)
return a(a+1)/2
4. Set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라.
create: 집합을 생성
insert: 집합에 원소추가
remove: 집합에 원소제거
is_in: 집합에 있는지 검사
union: 두 집합의 합집합
intersection: 두 집합의 교집합
difference: 두 집합의 차집합
6. 다음과 같은 코드의 시간 복잡도는? 여기 n이 프로그램의 입력이라고 가정하자
for(i = 1; i < n; i*= 2)
printf("hello");
O ( Log(n) )
i가 *2 만큼 증가하므로 log(n)
7. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자
for(i = 0; i < n; i++
for(j = 1; j < n; j*= 2)
print("hello");
O(n*log(n))
8. 시간 복잡도 함수 n^2 + 10n + 8을 빅오 표기법으로 나타내면?
(1) O(n)
(2) O(n * log_2 * n)
(3) O(n^2)
(4) O(n^2 * log_2 * n)
3번
n^2에 대해서 10n과 8의 입력이 시간복잡도계산에 큰 영향을 끼치지 않음.
입력값이 작으면 영향을 끼치지만 입력값이 클경우엔 미미함.
9. 시간 복잡도 함수가 7n+10 이라면 이것이 나타내는 것은 무엇인가?
(1) 연산의 횟수
(2) 프로그램의 수행시간
(3) 프로그램이 차지하는 메모리의 양
(4) 입력 데이터의 총 개수
(1) 연산의 횟수
10. O(n^2)의 시간복잡도를 가지는 알고리즘에서 입력의 개수가 2배로 되었다면 실행시간은 어떤 추세로 증가하는가?
(1) 변함없다
(2) 2배
(3) 4배
(4) 8배
기존 n^2에서 입력값이 2배가 되었으니 (2n)^2이 되었으므로 = 4 * (n^2) 으로 볼 수 있다.
답: (3) 4배
11. f(n)에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?
(1) 빅오메가
(2) 빅오
(3) 빅세타
(4) 존재하지 않는다.
(2) 빅오
12. 다음 빅오 표기법들을 수행시간이 적게 걸리는 것 부터 나열하라.
1.O(1)
2.O(n)
3.O(log_n)
4.O(n^2)
5.O(n*log_n)
6.O(n!)
7.O(2^n)
1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6
13. 두 함수 30n+4와 n^2를 여러가지 n값으로 비교하라. 언제 30n+4가 n^2보다 작은 값을 갖는지 구하라. 그래프를 그려보라.
그래프는 못그리지만 31부터 작은 값을 갖게 됩니다.
n=30 일때
30*30+4 = 904
30*30=900
n=31일때
31*30 + 4 = 930+4 = 934
31*31 = 961
14. 다음 실제로 프로그램의 수행시간을 측정하여 도표로 나타낸 것 이다. 도표로부터 이프로그램의 시간복잡도를 예측하여 빅오 표기법으로 나타내라.
| 입력의 개수 n |
수행시간 (초) |
| 2 |
2 |
| 4 |
8 |
| 8 |
25 |
| 16 |
63 |
| 32 |
162 |
n*log_n
초반엔 n^2 이였지만 뒤로 갈수록 n^2보단 작은 값으로 나타나기 때문에 n*log_n으로 예측할 수 있다.
15. 빅오표기법의 정의를 사용하여 다음을 증명하라.
5n^2 + 3 = O(n^2)
입력이 충분할때 가장 큰 항이 성능에 가장 큰 영향을 끼친다.
5(n^2) +3 < C(n^2)이 성립되면 n^2이 가장 큰 항이기에 이때 C=6을 대입하면
5(n^2)+3 <= 6(n^2)이 된다. 즉 n^2이 성능에 가장 큰 영향을 끼치므로 나머지 항은 버리게되어 O(n^2)으로 표기될 수 있다.
16. 빅오표기법의 정의를 이용하여 6(n^2)+3n이 O(n)이 될 수 없음을 보여라.
6(n^2)+3n <= C * n 을 만족하는 C가 있어야한다.
양 변을 n으로 나누면 6n +3 <= C 가된다,
이때 N이 매우 커지면 6n이 C보다 커질 수 밖에 없으므로 O(n) 이 성립될 수 없다.
17. 배열에 정수가 들어 있다고 가정하고 다음의 작업의 최악, 최선의 시간복잡도를 빅오 표기법으로 말하라.
(1) 배열의 n번째 숫자를 화면에 출력한다.
최선: O(1) 최악: O(1)
=> 출력은 입력과 무관하므로 한번의 연산으로 끝.
(2) 배열안의 숫자중에서 최소값을 찾는다.
최선: O(n) 최악: O(n)
=> 배열의 모든 값을 순회해야하므로 둘이 같다.
(3) 배열의 모든 숫자를 더한다.
최선: O(n) 최악: O(n)
=> 더하기 위해서도 배열의 모든 원소를 순회해야 하므로 최선과 최악이 같다.
