다음 정수 열에서 연속 부분합의 최댓값은?

1. 1

   5

2. 2

   8

3. 3

   10

4. 4

   15

해설

이진 탐색(binary search) 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 1

   탐색 범위가 절반씩 줄어든다.

2. 2

   탐색할 데이터는 순서 없이 저장되어 있다.

3. 3

   시간 복잡도는 O(logn)이다.

4. 4

   1,000개의 데이터가 존재하는 경우, 최대 10회의 탐색으로 완료된다.

해설

동적 계획법(dynamic programming)으로 설계된 알고리즘의 동작 방식에 대한 설명으로 옳지 않은 것은?

1. 1

   큰 문제를 작은 문제로 나눌 수 있어야 한다.

2. 2

   작은 문제들이 반복해서 사용되며, 이 작은 문제들의 결괏값을 저장해 두고 활용한다.

3. 3

   상향식(bottom-up) 접근 방식 또는 하향식(top-down) 접근 방식으로 구현할 수 있다.

4. 4

   메모하기(memoization) 방법을 활용하여 연산과 탐색이 증가하고 실행속도가 저하된다.

해설

다음 정렬 알고리즘 중에서 동일한 최악 시간 복잡도를 가진 것만을 모두 고르면?

1. 1

   ㄱ, ㄴ, ㄷ

2. 2

   ㄱ, ㄴ, ㄹ

3. 3

   ㄱ, ㄷ, ㄹ

4. 4

   ㄴ, ㄷ, ㄹ

해설

그림과 같은 과정을 포함하여 정렬을 실행하는 알고리즘은?

1. 1

   퀵 정렬

2. 2

   셸 정렬(shell sort)

3. 3

   기수 정렬(radix sort)

4. 4

   병합 정렬(merge sort)

해설

다음과 같은 배열 A에서 A[0]부터 삽입 연산을 차례대로 적용하여 이진 탐색 트리 T를 생성한 후, T를 전위(preorder) 순회 방법으로 방문한 값들을 배열 B에 B[0]부터 순차적으로 저장한 결과는?

1. 1

   B[]＝{10, 20, 30, 40}

2. 2

   B[]＝{10, 30, 20, 40}

3. 3

   B[]＝{40, 20, 10, 30}

4. 4

   B[]＝{40, 30, 20, 10}

해설

30억 개의 정수를 갖는 배열에서 20개의 정수를 제외한 나머지가 모두 정렬되어 있다면, 이 배열을 가장 빠르게 정렬할 수 있는 알고리즘은?

1. 1

   퀵 정렬

2. 2

   선택 정렬

3. 3

   병합 정렬

4. 4

   삽입 정렬

해설

알고리즘의 시간 복잡도에 대한 설명으로 옳은 것은?

1. 1

   널리 사용되는 것은 최악 시간 복잡도이다.

2. 2

   모든 알고리즘은 최악 시간 복잡도와 평균 시간 복잡도가 다르다.

3. 3

   최악의 경우 실행 시간은 모든 입력에 대한 실행 시간의 하한을 제공한다.

4. 4

   최선의 경우 실행 시간은 모든 입력에 대한 실행 시간의 상한을 제공한다.

해설

다항적 시간 복잡도를 갖는 탐욕(greedy) 알고리즘으로 최적의 해를 구할 수 없는 것은?

1. 1

   부분 배낭(fractional knapsack) 문제

2. 2

   한 정점에서 다른 정점으로의 최단 경로 탐색 문제

3. 3

   이진 트리의 최대합 경로 찾기 문제

4. 4

   최소 신장 트리(MST, Minimum Spanning Tree) 생성 문제

해설

해시(hash) 함수가 이고 키값이 15, 11, 5, 13, 22, 21 순서로 저장된 해시 테이블의 결과가 다음과 같은 경우에 사용된 충돌 해결 기법은?

1. 1

   체이닝(chaining)

2. 2

   선형 조사법(linear probing)

3. 3

   분기 한정법(branch and bound)

4. 4

   이차 조사법(quadratic probing)

해설