[부스트코스]알고리즘 퀴즈 9

Q>

1. 알고리즘의 성능 및 시간 복잡도를 표현하는 표기법 중 하나로, 최악의 경우일때(상한)를 나타내는 것은 다음 중 무엇인가요?

 

• O()
• Ω()
• θ()
• φ()

2. name과 number 두개의 멤버를 갖는 person이라는 새로운 자료형을 구조체로 정의하고자 합니다.

아래 코드의 괄호 안에 들어갈 코드로 알맞은 것은 무엇인가요?

 

• typedef struct
• function struct
• construct
• function

3. 전화번호부 책에서 '이펭수'를 찾는 작업을 선형 검색으로 수행하게 될 경우 Big-O 는 어떻게 될까요?

 

• O(1)
• O(log n)
• O(n)
• O(n^2)

4. 5 6 7 3 2 과 같은 숫자 리스트가 주어졌습니다.

오름차순 정렬을 위해 버블 정렬을 왼쪽 처음부터 오른쪽 끝까지 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

 

• 5 6 3 2 7
• 2 3 5 6 7
• 5 6 7 2 3
• 5 6 2 3 7

5. 5 6 7 3 2 와 같은 숫자 리스트가 주어졌습니다.

오름차순 정렬을 위해 선택 정렬을 통해 교환을 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

 

• 2 3 5 6 7
• 5 6 7 2 3
• 2 6 7 3 5
• 2 5 6 7 3

6. 선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요? (단, 하한이 같은 경우 상한이 빠른 순으로 나열합니다)

 

• 선택 정렬 - 버블 정렬 - 선형 검색 - 이진 검색
• 버블 정렬 - 선택 정렬 - 선형 검색 - 이진 검색
• 선형 검색 - 이진 검색 - 선택 정렬 - 버블 정렬
• 이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬

7. 아래 코드는 '#'으로 피라미드를 쌓는 코드입니다.

draw()와 같이 함수 안에서 함수 자기 자신을 호출하는 방식을 무엇이라고 할까요?

 

• 반복(repeat)
• 정렬(sort)
• 재귀(recursive)
• 검색(search)

8. 아래 코드와 같이 피라미드 쌓기를 재귀적으로 작성한 코드에서, h 값으로 3이 입력되었을 때 draw 함수는 총 몇 번 호출될까요?

 

• 1
• 2
• 3
• 4

9. 병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?

 

• 선택 정렬 - 병합 정렬 - 버블 정렬
• 버블 정렬 - 병합 정렬 - 선택 정렬
• 버블 정렬 - 선택 정렬 - 병합 정렬
• 병합 정렬 - 선택 정렬 - 버블 정렬

10. 알고리즘의 실행 시간의 상한을 비교하기 위해 Big-O 표기법을 사용합니다.

다음 Big-O 표기법 중 빠른 순서대로 올바르게 정렬한 것은 무엇인가요?

 

• O(log n) – O(n log n) – O(n) – O(n^2)
• O(log n) – O(1) – O(n) – O(n^2)
• O(1) – O(log n) – O(n) – O(n^2)
• O(1) – O(n log n) – O(n) – O(n^2)

A>

1. O()

 

2. typedef struct

 

3. O(n)

 

4. 5 6 3 2 7

 

5. 2 6 7 3 5

 

6. 이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬

 

7. 재귀(recursive)

 

8. 3

 

9. 버블 정렬 - 병합 정렬 - 선택 정렬

 

10. O(1) – O(log n) – O(n) – O(n^2)

 

https://www.boostcourse.org/cs112/

모두를 위한 컴퓨터 과학 (CS50 2019)