26년 1회차

총 20문항 · 객관식 · A4 약 1장

1 / 1

A4정답 포함← → 키 · 드래그로 넘김

9급 서울시 알고리즘 기출문제모두CBT · moducbt.com

26년 1회차

총 20문항 · 객관식 · 정답·해설 포함

문제 1

알고리즘의 시간복잡도 분석에 영향을 줄 수 있는 요인으로 옳은 것만을 <보기>에서 모두 고른 것은?

ㄱ. 프로그래밍 언어
ㄴ. 주요 연산의 시행 횟수
ㄷ. 입력의 크기
ㄹ. 프로그래머의 역량

1ㄱ, ㄴ

2ㄴ, ㄷ

3ㄱ, ㄷ, ㄹ

4ㄴ, ㄷ, ㄹ

문제 2

시간복잡도에 대한 점근적 표기법 중 가장 옳지 않은 것은?

f(n)=\Theta(g(n))

이면

f(n)=O(g(n))

이다.

f(n)=\Theta(g(n))

이면

f(n)=\Omega(g(n))

이다.

f(n)=O(g(n))

이면

f(n)\neq\Omega(g(n))

이다.

f(n)=O(g(n))

이고

g(n)=O(h(n))

이면

f(n)=O(h(n))

이다.

문제 3

분할 정복(divide-and-conquer) 기법에 대한 설명으로 가장 옳은 것은?

1문제를 더 이상 나눌 수 없을 때까지 작은 문제로 분할한 후, 그 결과를 결합하여 해결한다.

2문제를 해결할 때 항상 현재 단계에서 최적인 선택을 반복한다.

3이미 계산된 결과를 저장하여 동일한 계산을 반복하지 않도록 한다.

4모든 가능한 경우를 탐색하여 최적해를 찾는 방식이다.

문제 4

무방향 가중 그래프가 <보기>와 같이 주어져 있다. <보기>에서 간선 위의 수는 그 간선의 가중치를 의미한다. 이 그래프의 최소 신장 트리(MST, minimum spanning tree)를 구했을 때, 포함된 간선의 가중치의 합은?

132

234

338

442

문제 5

<보기>의 숫자 배열에 버블 정렬(bubble sort) 알고리즘을 사용하여 오름차순으로 정렬하려고 한다. 첫 번째 패스 이후 배열의 상태로 가장 옳은 것은?

7 1 3 5 2 4 9 6 8

11 2 3 4 5 6 7 8 9

21 3 5 2 4 7 6 8 9

31 7 3 5 2 4 6 9 8

47 1 3 5 2 4 9 8 6

문제 6

<보기>의 트리를 후위 순회(postorder traversal)한 경우 노드의 방문 순서로 가장 옳은 것은?

1A − B − D − G − H − E − C − F

2G − H − D − E − F − B − C − A

3G − H − D − E − B − F − C − A

4G − D − H − B − E − A − C − F

문제 7

<보기>의 의사코드(pseudo code)가 설명하는 정렬 알고리즘으로 가장 옳은 것은? (단, 입력은 크기가 n인 배열 A이고, 출력은 정렬된 배열 A이다.)

for i = 2 to n {
      key = A[i]
      j = i - 1

      while j > 0 and A[j] > key
            A[j + 1] = A[j]
            j = j - 1

      A[j + 1] = key
}

1삽입 정렬(insertion sort)

2선택 정렬(selection sort)

3병합 정렬(merge sort)

4퀵 정렬(quick sort)

문제 8

무방향 가중 그래프가 <보기>와 같이 주어져 있다. 그래프에서 간선 위의 수는 그 간선의 가중치를 의미한다. 이 그래프의 정점 A에서 다른 모든 정점까지의 최단 경로의 길이(가중치의 합)로 가장 옳은 것은?

1201

2206

3211

4216

문제 9

레드-블랙 트리(red-black tree)에 대한 설명으로 옳은 것만을 <보기>에서 모두 고른 것은?

ㄱ. 루트 노드는 항상 검은색이다.
ㄴ. 검은 노드는 검은 노드를 자식으로 가질 수 없다.
ㄷ. 어떤 노드에서 리프(NIL)까지 가는 모든 경로에는 같은 수의 빨간 노드가 존재한다.
ㄹ. 레드-블랙 트리는 완전 이진 트리(complete binary tree)이다.

1ㄱ

2ㄴ, ㄷ

3ㄱ, ㄷ, ㄹ

4ㄱ, ㄴ, ㄷ, ㄹ

문제 10

<보기>는 두 문자열

X

와

Y

가 주어졌을 때 최장 공통 부분 수열(LCS, longest common subsequence)의 길이를 구하는 알고리즘의 점화식이다.

c[i,j]

는 문자열

X_i

와

Y_j

의 LCS 길이라고 정의할 때, (가), (나)에 들어갈 내용으로 가장 옳은 것은? (단, LCS는 두 문자열에 공통으로 존재하는 가장 긴 부분 수열을 뜻한다. 이때, 문자의 연속성은 보장하지 않으며 순서는 유지하여야 한다.)

c[i,j]=\left\{\begin{array}{ll}0 & \text{if } i=0 \text{ or } j=0\\ \text{(가)} & \text{if } i,j>0 \text{ and } x[i]=y[j]\\ \text{(나)} & \text{if } i,j>0 \text{ and } x[i]\neq y[j]\end{array}\right\}

1(가)

c[i-1,j]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}

2(가)

c[i,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}+1

3(가)

c[i-1,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}

4(가)

c[i-1,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}+1

문제 11

<보기>는 정수 n을 입력하면 계산 결과를 출력(return)하는 알고리즘의 의사코드(pseudo code)이다. f(n)을 호출했을 때, 출력되는 값이 100보다 크게 되는 정수 n의 최솟값은?

f(n)
  if (n<1) return 1
  else return f(n-1) + f(n-3) + 1

210

311

412

문제 12

<보기> 그래프의 위상정렬(topological sort)의 결과로 가장 옳은 것은?

1A→B→E→D→C

2A→E→D→C→B

3A→B→C→E→D

4A→B→C→D→E

문제 13

이진 탐색 트리(BST, binary search tree)에 대한 설명으로 가장 옳지 않은 것은?

1중복 키를 허용하지 않는 경우, 모든 노드에 대해 왼쪽 서브트리의 키는 해당 노드의 키보다 작고, 오른쪽 서브트리의 키는 해당 노드의 키보다 크다.

2루트 노드는 항상 전체 원소의 중앙값이어야 한다.

3BST에서 중위 순회(inorder traversal)를 하면 키 값이 오름차순으로 출력된다.

4탐색 · 삽입 · 삭제 연산의 시간복잡도는 트리의 높이에 비례한다.

문제 14

<보기>는 문자열 탐색 알고리즘인 라빈-카프(Rabin-Karp) 알고리즘에 대한 설명이다. 옳은 설명을 모두 고른 것은?

ㄱ. 문자열 탐색을 위해 해시 함수를 사용한다.
ㄴ. 알고리즘의 효율성은 해시 함수 계산 비용을 줄이는 데에 있다.
ㄷ. 패턴의 해시값과 본문 부분 문자열의 해시값이 일치하더라도 실제 문자가 일치하는지 추가 확인이 필요하다.

1ㄱ

2ㄱ, ㄴ

3ㄴ, ㄷ

4ㄱ, ㄴ, ㄷ

문제 15

<보기>의 그래프에서 A부터 너비 우선 탐색(BFS, breadth first search)을 수행하는 경우, 정점의 방문 순서로 가장 옳은 것은? (단, 탐색되지 않은 이웃(neighbor)이 2개 이상 있는 경우 알파벳 순서로 탐색한다.)

1A − B − C − D − F − I − H − G − E

2A − B − E − G − C − F − H − D − I

3A − B − G − E − C − H − F − D − I

4A − B − C − D − F − E − G − H − I

문제 16

<보기>의 최소 힙(min heap)에서 루트 노드를 삭제한 경우, 최소 힙 조건을 만족하도록 연산을 거친 후의 구조로 가장 옳은 것은?

1[그림]

2[그림]

3[그림]

4[그림]

문제 17

해시 테이블의 충돌 문제 해결을 위한 방법 중 개방 주소법(open addressing)에 해당하지 않는 것은?

1선형 조사법(linear probing)

2체이닝(chaining)

3이차 조사법(quadratic probing)

4이중 해싱(double hashing)

문제 18

<보기>는 막대 자르기(rod cutting) 문제의 재귀적 의사코드(pseudo code)이다. 막대의 길이 정수

n

과 가격 배열

p

를 입력 받아, 막대를 잘랐을 때 가능한 이익의 최댓값을 구한다. 이때, (가)에 들어갈 내용으로 가장 옳은 것은? (단, 배열

p

의 길이는

n

이며,

p[i]

는 길이가

i

인 막대의 가격이다.)

CUT_ROD(p,n)
    if n==0
      return 0
    q=-∞
    for i=1 to n
      q=max{q,p[i]+      (가)      }
    return q

1CUT_ROD(p,i-1)

2CUT_ROD(p,i)

3CUT_ROD(p,i+1)

4CUT_ROD(p,n-i)

문제 19

정렬 알고리즘에 대한 설명 중 가장 옳지 않은 것은?

1선택 정렬(selection sort) 알고리즘은

n

개의 원소를 갖는 리스트를 정렬하는 경우, 총

n(n-1)/2

회의 비교연산이 진행된다.

2힙 정렬(heap sort) 알고리즘은 완전 이진 트리 형태의 자료구조 힙을 활용한다.

3합병 정렬(merge sort) 알고리즘은 동적 계획법(dynamic programming) 방식을 기반으로 동작한다.

4기수 정렬(radix sort) 알고리즘은 자릿수가

d

인 자연수

n

개로 구성된 리스트를 정렬할 때,

d=n

이라면

O(n^2)

의 시간복잡도를 갖는다.

문제 20

<보기>에서 설명하는 문제 부류에 속하지 않는 것으로 가장 옳은 것은?

• 현재 이 부류 문제에 대한 다항 시간의 알고리즘이 알려져 있지 않다.
• 이 부류의 문제 사이에는 다항 시간 환원(reduction)이 가능하다.
• 이 부류에 속하는 문제 중 어느 한 문제만 다항식 시간에 해결되면, 모든 다른 문제들이 다항 시간에 해결 가능하다.

1만족성(SAT) 문제

2부분 집합의 합(subset sum) 문제

30-1 배낭 결정(knapsack decision) 문제

4모든 쌍 최단 경로(all pairs shortest paths) 문제

9급 서울시 알고리즘 기출문제모두CBT · moducbt.com

26년 1회차

총 20문항 · 객관식 · 정답·해설 포함

문제 1

알고리즘의 시간복잡도 분석에 영향을 줄 수 있는 요인으로 옳은 것만을 <보기>에서 모두 고른 것은?

ㄱ. 프로그래밍 언어
ㄴ. 주요 연산의 시행 횟수
ㄷ. 입력의 크기
ㄹ. 프로그래머의 역량

1ㄱ, ㄴ

2ㄴ, ㄷ

3ㄱ, ㄷ, ㄹ

4ㄴ, ㄷ, ㄹ

문제 2

시간복잡도에 대한 점근적 표기법 중 가장 옳지 않은 것은?

f(n)=\Theta(g(n))

이면

f(n)=O(g(n))

이다.

f(n)=\Theta(g(n))

이면

f(n)=\Omega(g(n))

이다.

f(n)=O(g(n))

이면

f(n)\neq\Omega(g(n))

이다.

f(n)=O(g(n))

이고

g(n)=O(h(n))

이면

f(n)=O(h(n))

이다.

문제 3

분할 정복(divide-and-conquer) 기법에 대한 설명으로 가장 옳은 것은?

1문제를 더 이상 나눌 수 없을 때까지 작은 문제로 분할한 후, 그 결과를 결합하여 해결한다.

2문제를 해결할 때 항상 현재 단계에서 최적인 선택을 반복한다.

3이미 계산된 결과를 저장하여 동일한 계산을 반복하지 않도록 한다.

4모든 가능한 경우를 탐색하여 최적해를 찾는 방식이다.

문제 4

132

234

338

442

문제 5

<보기>의 숫자 배열에 버블 정렬(bubble sort) 알고리즘을 사용하여 오름차순으로 정렬하려고 한다. 첫 번째 패스 이후 배열의 상태로 가장 옳은 것은?

7 1 3 5 2 4 9 6 8

11 2 3 4 5 6 7 8 9

21 3 5 2 4 7 6 8 9

31 7 3 5 2 4 6 9 8

47 1 3 5 2 4 9 8 6

문제 6

<보기>의 트리를 후위 순회(postorder traversal)한 경우 노드의 방문 순서로 가장 옳은 것은?

1A − B − D − G − H − E − C − F

2G − H − D − E − F − B − C − A

3G − H − D − E − B − F − C − A

4G − D − H − B − E − A − C − F

문제 7

<보기>의 의사코드(pseudo code)가 설명하는 정렬 알고리즘으로 가장 옳은 것은? (단, 입력은 크기가 n인 배열 A이고, 출력은 정렬된 배열 A이다.)

for i = 2 to n {
      key = A[i]
      j = i - 1

      while j > 0 and A[j] > key
            A[j + 1] = A[j]
            j = j - 1

      A[j + 1] = key
}

1삽입 정렬(insertion sort)

2선택 정렬(selection sort)

3병합 정렬(merge sort)

4퀵 정렬(quick sort)

문제 8

1201

2206

3211

4216

문제 9

레드-블랙 트리(red-black tree)에 대한 설명으로 옳은 것만을 <보기>에서 모두 고른 것은?

1ㄱ

2ㄴ, ㄷ

3ㄱ, ㄷ, ㄹ

4ㄱ, ㄴ, ㄷ, ㄹ

문제 10

<보기>는 두 문자열

X

와

Y

가 주어졌을 때 최장 공통 부분 수열(LCS, longest common subsequence)의 길이를 구하는 알고리즘의 점화식이다.

c[i,j]

는 문자열

X_i

와

Y_j

c[i,j]=\left\{\begin{array}{ll}0 & \text{if } i=0 \text{ or } j=0\\ \text{(가)} & \text{if } i,j>0 \text{ and } x[i]=y[j]\\ \text{(나)} & \text{if } i,j>0 \text{ and } x[i]\neq y[j]\end{array}\right\}

1(가)

c[i-1,j]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}

2(가)

c[i,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}+1

3(가)

c[i-1,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}

4(가)

c[i-1,j-1]+1

(나)

\max\{c[i-1,j],c[i,j-1]\}+1

문제 11

f(n)
  if (n<1) return 1
  else return f(n-1) + f(n-3) + 1

210

311

412

문제 12

<보기> 그래프의 위상정렬(topological sort)의 결과로 가장 옳은 것은?

1A→B→E→D→C

2A→E→D→C→B

3A→B→C→E→D

4A→B→C→D→E

문제 13

이진 탐색 트리(BST, binary search tree)에 대한 설명으로 가장 옳지 않은 것은?

1중복 키를 허용하지 않는 경우, 모든 노드에 대해 왼쪽 서브트리의 키는 해당 노드의 키보다 작고, 오른쪽 서브트리의 키는 해당 노드의 키보다 크다.

2루트 노드는 항상 전체 원소의 중앙값이어야 한다.

3BST에서 중위 순회(inorder traversal)를 하면 키 값이 오름차순으로 출력된다.

4탐색 · 삽입 · 삭제 연산의 시간복잡도는 트리의 높이에 비례한다.

문제 14

<보기>는 문자열 탐색 알고리즘인 라빈-카프(Rabin-Karp) 알고리즘에 대한 설명이다. 옳은 설명을 모두 고른 것은?

1ㄱ

2ㄱ, ㄴ

3ㄴ, ㄷ

4ㄱ, ㄴ, ㄷ

문제 15

1A − B − C − D − F − I − H − G − E

2A − B − E − G − C − F − H − D − I

3A − B − G − E − C − H − F − D − I

4A − B − C − D − F − E − G − H − I

문제 16

<보기>의 최소 힙(min heap)에서 루트 노드를 삭제한 경우, 최소 힙 조건을 만족하도록 연산을 거친 후의 구조로 가장 옳은 것은?

1[그림]

2[그림]

3[그림]

4[그림]

문제 17

해시 테이블의 충돌 문제 해결을 위한 방법 중 개방 주소법(open addressing)에 해당하지 않는 것은?

1선형 조사법(linear probing)

2체이닝(chaining)

3이차 조사법(quadratic probing)

4이중 해싱(double hashing)

문제 18

<보기>는 막대 자르기(rod cutting) 문제의 재귀적 의사코드(pseudo code)이다. 막대의 길이 정수

n

과 가격 배열

p

를 입력 받아, 막대를 잘랐을 때 가능한 이익의 최댓값을 구한다. 이때, (가)에 들어갈 내용으로 가장 옳은 것은? (단, 배열

p

의 길이는

n

이며,

p[i]

는 길이가

i

인 막대의 가격이다.)

CUT_ROD(p,n)
    if n==0
      return 0
    q=-∞
    for i=1 to n
      q=max{q,p[i]+      (가)      }
    return q

1CUT_ROD(p,i-1)

2CUT_ROD(p,i)

3CUT_ROD(p,i+1)

4CUT_ROD(p,n-i)

문제 19

정렬 알고리즘에 대한 설명 중 가장 옳지 않은 것은?

1선택 정렬(selection sort) 알고리즘은

n

개의 원소를 갖는 리스트를 정렬하는 경우, 총

n(n-1)/2

회의 비교연산이 진행된다.

2힙 정렬(heap sort) 알고리즘은 완전 이진 트리 형태의 자료구조 힙을 활용한다.

3합병 정렬(merge sort) 알고리즘은 동적 계획법(dynamic programming) 방식을 기반으로 동작한다.

4기수 정렬(radix sort) 알고리즘은 자릿수가

d

인 자연수

n

개로 구성된 리스트를 정렬할 때,

d=n

이라면

O(n^2)

의 시간복잡도를 갖는다.

문제 20

<보기>에서 설명하는 문제 부류에 속하지 않는 것으로 가장 옳은 것은?

1만족성(SAT) 문제

2부분 집합의 합(subset sum) 문제

30-1 배낭 결정(knapsack decision) 문제

4모든 쌍 최단 경로(all pairs shortest paths) 문제