2장 알고리즘

 

https://www.happycampus.com/exam-doc/27878006/

2장 3장 연습문제 과제 알기 쉬운 알고리즘 step-by-step으로 알고리즘 완전이해 시험자료

 

2장 3장 문제 풀이는 여기를 참고 부탁드립니다.

 

 

2장 연습문제 알기 쉬운 알고리즘 step-by-step으로 알고리즘 완전이해

https://game-chanda.tistory.com/41

-1장

 

 

 

 

1.다음의 괄호 안에 알맞은 단어를 채워 넣어라.
 
(1) 알고리즘이란(문제)를 해결하는(단계적)절차 또는 방법이다.
(2) 알고리즘의 일반적인 특성에는(정확성),수행성,(유한성),효율성이있다.
(3) 알고리즘은 일반적으로 (의사코드)형태로 표현된다.

(4) 알고리즘의 효율성은 주로(시간 복잡도)가 사용된다.

(5) 알고리즘이 수행하는(기본적인 연산)횟수를 (입력)크기에 대한 함수로표현한것을 시간복잡도라고 한다.

(6) 알고리즘의 복잡도 표현 방법에는(최악)경우 분석,(평균)경우 분석,(최선)경우 분석이있다.

(7) 입력 크기가 무한대로 커질 떄의 복잡도를 간단히 표현하기 위해 사용하는 표기법을(점근적)표기법이라고한다.

(8) O-표기는 점근적(상한)을 나타낸다.

(9) Ω-표기는 점극적(하한)을 나타낸다.

(10)Δέλτα 델타, 영어: Delta는 동일한(증가율)을 나타낸다.

2.다음은 알고리즘에 관한 설명이다. 다음중 옳지 않은 것은은?

풀이: 
1. 알고리즘은 주어진 입력에 대해 올바른 해를 주어야한다.
정확성
2.알고리즘의 각 단계는 컴퓨터에서 수행 가능하여야 한다.
수행성
3. 알고리즘은 유한 시간 내에 종료 되어야 한다.
유한성
4.알고리즘은 효율적일수록 그 가치가 높다.
효울성
5. 답없음 

 

답: 5번
 
3. 다음 중 알고리즘으로 해결할 수 없는 것은?

1,가장 작은 숫자와 가장 큰숫자를 찾는 것

2. 여러 점들 중에서 가장 가까운 두점을 찾는 것

3. 가장 맛있는 라면 끊이기

4. 최단 경로 찾기
답: 3번

4. 다음은 알고리즘의 시간 복잡도에 관한 설명이다.다음 중 옳은 것은?
답:  4번
풀이: 

문제의 하한을 연구하는데 매우 중요한 자료

5.다음은 시간복잡도의 분석에 관한 것이다. 다음 중 옳지 않은 것은?
답: 4번
풀이:
중간  경우는 없다
최고 최저 평균경우 라고 부른다.

728x90

6.다음은 점근적 표기에 관한 것이다. 다음 중 옳지 않은 것은?
답: 4번
풀이:
증가율차이는 없다

 

7.만일 어떤 알고리즘의 수행시간이

일떄 , 이를 O-표기로 옳게 나타낸것은?

답: 3번

문제는 빅오메가 라고 적혀있지만 문제가 잘못된거같다.

빅오 라고 바꿔주자. 

3번이 답인 이유는 사칙연산을 해주면 n^3logn이 나오게 된다.

8.다음에서 log(n!)에 대한 가장 적절한 점근적 표기는?

답: 3번

풀이:
n!은 n의 팩토리얼로 n! = n * (n-1) * (n-2) * ... * 2 * 1입니다. 이를 풀어쓰면 n! = n * (n-1)!입니다.

 

여기서 log((n-1)!)을 계산하기 위해서는 다시 log(n-1) + log((n-2)!)을 계산해야 합니다. 이를 반복하면 log(n!) = log(n) + log(n-1) + ... + log(2) + log(1)이 됩니다.

이를 풀어쓰면 log(n!) = Σi=1~n(log(i))이 됩니다.

따라서 n!의 로그 값은 i=1부터 n까지 로그(i)의 합으로 표현할 수 있습니다. 이를 이용하여 n!의 로그 값을 계산할 때는 n에 대한 for 루프를 돌며 로그(i) 값을 더하는 과정이 필요합니다.

따라서 시간 복잡도는 O(n)이 되며, 로그를 씌우면 O(nlogn)이 됩니다.\

빅오메가도 똑같이(nlogn) 이다.

 

9.다음중 맞는것은?

답: 답이없다. 5번이 정답

 

10.다음중 맞는것은?

n제곱과 o(n세제곱)은 같은표현이다. 근데 n제곱이라고 쓴다.

답: 1번

 

12.다음 중 함수가 n이 커질수록 가장 빨리 증가 하는것은?

 

답 4번 

풀이 : 1 2 3 5 4순서

 

13.다음 3개의 점근적 표기에 대해 옳게 설명한것은?

(가) n^3

(나) 정답

(다)n^3

 

답:2번

14. 다음 중 점근적 표기 관계가 옳은 것을 모두 고르라
답: 1 3  
5번 설명:
https://velog.io/@nathan29849/Python-Algorithm-class-log-n-%EA%B3%BC-n-%EB%B9%84%EA%B5%90
결과적으로 log n이 더효율이 좋다

 

15.어느 알고리즘의 수행시간이 o(n^2)이다. 입력크기 n=k일때 이 알고리즘을 실제로 어떤 컴퓨터에서 수행시켜보니 40초가 걸렸다.

(1) 입력 크기가 2배이면,즉 n=2k일때 이 알고리즘을 같은 컴퓨터에서 수행시켜 보면 몇초가 걸리는가?

   k^2=40

(2k)^2=4k^2  

4x40= 160초

답:4번

 

(2)  n=2k일때 알고리즘을 2배 빠른 컴퓨터에서 수행 시켜보면 몇초가 걸리는가? 

160/2 = 80초

답 : 4번

 

(3)

16~17

 

 

18. 다음은 순환 관계를 각각o-표기로 표현한 것이다. 다음 중 옳지 않은 것은?

답: 2번 둘다 n이다.

T(n)=O(n)

 

19.다음 함수에 대하여 답하라

 

hello 3 

hello 4 4 

hello 2

총 13번

답: 4번

 

21.다음 중첩 for-루프에 대해 답하라

(1) 답 4번

(2) 답 3번 n을 4로 잡고 풀어보면 답나옴

 

22.다음 중첩 for-루프에 대해 답하라

(1) 답:2번

(2) 답:2번 nlogn

 

23. 다음의 while-루프에 대해 답하라. 단i/2는 나눗셈 후 몫의 정수만을 취한다

(1) i가 0보다 작아지기 떄문에 hello 는 3번 나옴 답 3번

(2) 답:2번 printf문은 루프가 1회 수행 될때마다 i가 반으로 줄어들기 때문에 

예를 들어 n=8이라면 i가 8 4 2 1일떄 즉 4회 hello가 출력 log(n)

 

24.다음 함수에 대하여 답하라

(1) 파보나치 수열이다. 하지만 잘보면 여기는 f(0) 이 1이다

1 2 3 5니까 답은 5가된다. 

(2) 트리의 높이 만큼 시간 복잡도를 가지기 때문에 2^n승