[강의 퀴즈 해설] CS50 2019 Chapter 4. 알고리즘 Quiz

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

A1. O()

 

Q2. name과 number 두개의 멤버를 갖는 person이라는 새로운 자료형을 구조체로 정의하고자 합니다. 아래 코드의 괄호 안에 들어갈 코드로 알맞은 것은 무엇인가요?

A2. typedef struct, 맨 밑에 나오는 person을 구조체로 정의할때 typedef struct로 표현할 수 있다.

 

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

A3. O(n)

 

Q4. 5 6 7 3 2 과 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 버블 정렬을 왼쪽 처음부터 오른쪽 끝까지 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

A4. 5 6 3 2 7버블 정렬이란? 인접한 두 원소를 비교하여 교환하면서 정렬하는 알고리즘이다. 5 6 -> 정렬되어있으니까 그대로 둔다.6 7 -> 정렬되어있으니까 그대로 둔다.7 3 -> 3이 7보다 작으니까 3 7로 바꾼다.7 2 -> 2가 7보다 작으니가 2 7로 바꾼다.

 

Q5. 5 6 7 3 2 와 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 선택 정렬을 통해 교환을 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

A5. 2 6 7 3 5선택 정렬이란? 가장 작은 원소를 찾아 맨 앞의 원소랑 바꾼다.여기서는 2가 가장 작으니 맨 앞의 5와 바꿔주면 된다.

 

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

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

 

Q7. 아래 코드는 '#'으로 피라미드를 쌓는 코드입니다. draw()와 같이 함수 안에서 함수 자기 자신을 호출하는 방식을 무엇이라고 할까요?

A7. 재귀(recursive), 함수 자기 자신을 호출하는 것은 재귀이다. 

 

Q8. 아래 코드와 같이 피라미드 쌓기를 재귀적으로 작성한 코드에서, h 값으로 3이 입력되었을 때 draw 함수는 총 몇 번 호출될까요? ( parameter로 3을 받은 draw 함수 최초 호출은 제외합니다.) 

A8. 3, 최초 호출은 제외하고 카운트를 해야한다. 

draw(3) 호출 (제외) -> draw(2) -> draw(1) -> draw(0) 

이렇게 총 3번이다. 

 

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

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

 

Q10. 알고리즘의 실행 시간의 상한을 비교하기 위해 Big-O 표기법을 사용합니다. 다음 Big-O 표기법 중 빠른 순서대로 올바르게 정렬한 것은 무엇인가요?

A10. O(1) – O(log n) – O(n) – O(n^2), 괄호 안의 변수가 작을 수록 빠르다.