다음 그래프에서 생성이 가능한 신장 트리(spanning tree)의 최대 개수는?

1. 1

   4

2. 2

   8

3. 3

   16

4. 4

   32

해설

위상 정렬(topological sort)을 적용할 때 모든 정점을 포함하는 결과가 생성될 수 없는 그래프는?

1. 1

   

2. 2

   

3. 3

   

4. 4

   

해설

다음 설명에 해당하는 알고리즘은?

1. 1

   프림(Prim) 알고리즘

2. 2

   플로이드－워셜(Floyd-Warshall) 알고리즘

3. 3

   다익스트라(Dijkstra) 알고리즘

4. 4

   KMP(Knuth-Morris-Pratt) 알고리즘

해설

다음 C언어로 작성된 함수의 입력값으로 13이 입력될 경우 출력되는 결과는?

1. 1

   1010

2. 2

   1011

3. 3

   1100

4. 4

   1101

해설

텍스트 문자열 01001에 대하여 패턴 문자열 001을 찾기 위해 브루트－포스(brute-force) 문자열 검색 알고리즘을 사용할 경우, 문자를 비교한 총 횟수는? (단, 패턴 문자열이 한번 검색되면 더 이상 검색하지 않는다)

1. 1

   1

2. 2

   3

3. 3

   5

4. 4

   6

해설

다음 중 그리디 알고리즘에 해당하는 것만을 모두 고르면?

1. 1

   ㄷ

2. 2

   ㄱ, ㄴ

3. 3

   ㄱ, ㄷ

4. 4

   ㄱ, ㄷ, ㄹ

해설

퀵 정렬 시 시간복잡도가 최악의 경우가 되는 것으로 가장 적절한 것은?

1. 1

   피벗(pivot)을 최대값으로 정한다.

2. 2

   피벗을 랜덤(random)하게 정한다.

3. 3

   피벗을 중간값(median)으로 정한다.

4. 4

   피벗을 파티션(partition)의 중간에 위치한 값으로 정한다.

해설

분할 정복(divide-conquer) 문제 해결 기법을 이용하여 토너먼트 방식으로 64개의 축구팀 중 1등을 결정하기 위해 치르게 되는 최소의 경기 횟수는? (단, 모든 경기는 팀별 1:1 방식으로 진행되며 무승부 및 기권은 없다)

1. 1

   61

2. 2

   62

3. 3

   63

4. 4

   64

해설

다음 설명의 (가)에 들어갈 용어로 옳은 것은? (단, P≠NP이다)

1. 1

   P 문제

2. 2

   NP 문제

3. 3

   NP－하드(NP-hard) 문제

4. 4

   NP－완전(NP-complete) 문제

해설

1. 1

   

2. 2

   

3. 3

   

4. 4

   

해설