https://www.boostcourse.org/cs112
Q1. 알고리즘(단일선택)
알고리즘의 성능 및 시간 복잡도를 표현하는 표기법 중 하나로, 최악의 경우일때(상한)를 나타내는 것은 다음 중 무엇인가요?
① θ()
② φ()
③ O()
④ Ω()
→ 상한은 O(), 하한은 Ω() ∴ ③번
Q2. 자료형(단일선택)
name과 number 두개의 멤버를 갖는 person이라는 새로운 자료형을 구조체로 정의하고자 합니다. 아래 코드의 괄호 안에 들어갈 코드로 알맞은 것은 무엇인가요?
① typedef struct
② construct
③ function struct
④ function
→ ①번
Q3. 알고리즘(단일선택)
전화번호부 책에서 '이펭수'를 찾는 작업을 선형 검색으로 수행하게 될 경우 Big-O 는 어떻게 될까요?
① O(n^2)
② O(log n)
③ O(n)
④ O(1)
→ ③번
Q4. 정렬(단일선택)
5 6 7 3 2 과 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 버블 정렬을 왼쪽 처음부터 오른쪽 끝까지 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?
① 5 6 2 3 7
② 5 6 7 2 3
③ 2 3 5 6 7
④ 5 6 3 2 7
→ 5 6 3 2 7 ∴ ④번
Q5. 선택 정렬(단일선택)
5 6 7 3 2 와 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 선택 정렬을 통해 교환을 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?
① 2 5 6 7 3
② 2 3 5 6 7
③ 5 6 7 2 3
④ 2 6 7 3 5
→ 2 6 7 3 5 ∴ ④번
Q6. 알고리즘(단일선택)
선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요? (단, 하한이 같은 경우 상한이 빠른 순으로 나열합니다)
① 이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬
② 선형 검색 - 이진 검색 - 선택 정렬 - 버블 정렬
③ 버블 정렬 - 선택 정렬 - 선형 검색 - 이진 검색
④ 선택 정렬 - 버블 정렬 - 선형 검색 - 이진 검색
→ ①번
Q7. 함수(단일선택)
아래 코드는 '#'으로 피라미드를 쌓는 코드입니다. draw()와 같이 함수 안에서 함수 자기 자신을 호출하는 방식을 무엇이라고 할까요?
① 재귀(recursive)
② 검색(search)
③ 정렬(sort)
④ 반복(repeat)
→ ①번
Q8. 알고리즘 실행 시간의 단위(단일선택)
아래 코드와 같이 피라미드 쌓기를 재귀적으로 작성한 코드에서, h 값으로 3이 입력되었을 때 draw 함수는 총 몇 번 호출될까요? ( parameter로 3을 받은 draw 함수 최초 호출은 제외합니다.)
① 3
② 2
③ 1
④ 4
→ ①번
Q9. 정렬(단일선택)
병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?
① 선택 정렬 - 병합 정렬 - 버블 정렬
② 버블 정렬 - 병합 정렬 - 선택 정렬
③ 버블 정렬 - 선택 정렬 - 병합 정렬
④ 병합 정렬 - 선택 정렬 - 버블 정렬
→ ③번
Q10. 알고리즘 실행 시간의 표기법(단일선택)
알고리즘의 실행 시간의 상한을 비교하기 위해 Big-O 표기법을 사용합니다. 다음 Big-O 표기법 중 빠른 순서대로 올바르게 정렬한 것은 무엇인가요?
① O(log n) – O(1) – O(n) – O(n^2)
② O(log n) – O(n log n) – O(n) – O(n^2)
③ O(1) – O(n log n) – O(n) – O(n^2)
④ O(1) – O(log n) – O(n) – O(n^2)
→ ④번
채점결과
오답노트
Q9. 정렬(단일선택)
병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?
① 선택 정렬 - 병합 정렬 - 버블 정렬
② 버블 정렬 - 병합 정렬 - 선택 정렬
③ 버블 정렬 - 선택 정렬 - 병합 정렬
④ 병합 정렬 - 선택 정렬 - 버블 정렬
→ 선택이랑 병합이 헷갈렸는데 선택 정렬은 Ω(n^2) 이고 병합 정렬은 Ω(nlogn)이다. ∴ ②번
시간복잡도 너무 어렵다,,
