알고리즘 QUIZ

GYUBIN ·2022년 5월 7일

TIL cs50

CS50 2019

목록 보기

9/12

CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.

1. 알고리즘

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

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

Big O 는 알고리즘 실행 시간의 상한을 나타낸다.

2. 자료형

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

(          )
{
	string name;
    string number;
}
person;

typedef struct
function struct
construct
function

3. 알고리즘

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

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

선형 검색은 리스트의 모든 원소를 확인해야 하므로 Big-O 는 O(n) 이다.

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

선택 정렬을 한 번만 수행하게 되면 가장 작은 숫자와 0번 째 숫자가 교환된다.

6. 알고리즘

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

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

실행시간의 상한은 Big O, 하한은 Big Ω 이다.
4가지 알고리즘은 아래와 같은 실행시간을 가진다.

선형 검색: O(n), Ω(1)
이진 검색: O(log n), Ω(1)
버블 정렬: O(n^2), Ω(n^2)
선택 정렬: O(n^2), Ω(n^2)

7. 함수

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

void draw(int h)
{
	if (h == 0)
    {
    	return;
    }
    draw(h - 1);
    
    for (int i = 0; i < h; i++)
    {
    	printf("#");
    }
    printf("\n");
}

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

함수가 본인 스스로를 호출해서 사용하는 것을 재귀라고 한다

8. 알고리즘 실행 시간의 단위

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

void draw(int h)
{
	if (h == 0)
    {
    	return;
    }
    draw(h - 1);
    
    for (int i = 0; i < h; i++)
    {
    	printf("#");
    }
    printf("\n");
}

1
2
3
4

9. 정렬

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

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

병합 정렬의 Big Ω 는 Ω(n log n)나누고 정렬하여 병합( Ω(log n) * Ω(n) ), 선택 정렬과 버블 정렬의 Big Ω 는 Ω(n^2) 이다.