알고리즘 2018년도 기말 기출문제 풀이 - 방송대, 방송통신대학교 알고리즘

알고리즘 2018

1번. 교재 및 강의에서 다루어지지 않은 알고리즘

1. 기하 알고리즘
2. 정렬 알고리즘 - 버블, 선택, 삽입, 셸, 합병, 퀵, 힙, 계수, 기수
3. 유전 알고리즘 - 외판원 문제의 근삿값 구하기
4. 욕심쟁이 알고리즘 - 동전 거스름돈, 배낭, 최소신장트리, 최단경로, 작업스케줄링, 작업선택, 허프만 코딩

정답: 1번

2번. 주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은?

1. 모든 명령은 컴퓨터에서 수행 가능해야 한다.
2. 각 명령은 단순하고 명확해야 한다.
3. 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다.
4. 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다. → 외부 입력이 반드시 존재할 필요는 없다.

정답 : 4번

3번. 최대 개수의 노드를 갖는 높이 4인 이진 트리에서 단말 노드의 개수는?

2^(4-1) = 8

정답: 8개

4번. 알고리즘의 시간 복잡도는 무엇의 함수로 표현하는가?

정답: 입력 데이터의 크기

5번. 다음 O-표기 중에서 가장 효율적인 성능을 나타내는 것은?

1. O(logn)
2. O(nlogn)
3. O(n^2)
4. O(2^n)

logn < nlogn < n^2 < 2^n

(상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수)

정답: 1번

6번. 분할정복에 대한 설명으로 거리가 먼 것은

1. 분할된 작은 문제는 서로 독립적이다
2. 하향식 접근 방법을 사용한다.
3. 분할, 정복, 결합의 처리 과정을 거친다.
4. 점화식을 이용해서 보다 큰 문제의 해를 구한다. → 점화식을 이용하는 것은 ‘동적 프로그래밍’ 이다.

정답: 4

7번. 다음과 같은 데이터에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후 왼쪽 부분배열의 첫 번째 원소는? (단, 피벗은 맨 왼쪽 원소이고, 오름차순으로 정렬한다.)

빨간색: Left

파란색: Right

1. 30 45 20 15 40 25 35 10
2. 30 10 20 15 40 25 35 45
3. 30 10 20 15 25 40 35 45

3번에서 right의 인덱스 < left의 인덱스

따라서 pivot과 25를 교환함

정답: 25

8번. 퀵 정렬의 최악의 시간 복잡도에 해당하는 점화식은?

퀵 정렬의 최악의 시간 복잡도가 발생하는 상황:

데이터가 정렬된 경우, 데이터가 역순으로 정렬된 경우

데이터가 혼쪽으로 쏠리는 분할이 발생하여 최악의 시간 복잡도가 발생

→ T(0) + T(n-1) 만큼의 분할이 지속적으로 발생

정답: T(n) = T(n-1) + O(n), T(1) = O(1)

9번. 중간값들의 중간값을 사용하는 선택 문제에서 각 그룹은 몇 개의 원소로 구성되는가?

정답: 5개

10번. 다음 중 동적 프로그래밍 방법을 적용한 알고리즘은?

1. 모든 정점 간의 최단 경로 구하는 알고리즘 : 플로이드 알고리즘
2. 합병 정렬: 분할 정복
3. 최솟값과 최댓값을 모두 찾는 알고리즘
4. 작업 선택 문제 : 욕심쟁이 알고리즘

정답: 1번

11번. 연쇄 행렬 곱셈 문제에서 다음과 같이 6개의 행렬을 곱한다고 하자. 이때 C(1,2)의 값은?

행렬의 곱셈에 필요한 연산 수는 i * j * k

5 * 2 * 3 = 30

정답: 30

12번. 다음 그래프에 대해서 모든 정점 간의 최단 경로를 구하려고 한다. 4에서 2로, 3을 거쳐간 값은?

4 → 1 : 3

1 → 3 : 2

3 → 2 : -1

정답: 4

13번. 동적 프로그래밍 방법으로 해결 가능한 저울 문제에 대한 설명으로 올바른 것은?

1. 추의 무게는 정수이어야 한다.
2. 최적화 문제이다.
3. 양팔 저울의 어느 쪽에나 추를 올릴 수 있다.
4. 저울로 달려는 무게에는 아무런 제약이 없다.

정답: 1번

14번. 동전 거스름돈 문제에 대한 설명으로 올바른 것은?

1. 동전의 액면가가 임의로 주어지는 경우에도 욕심쟁이 방법으로 해결할 수 있다. → 큰 동전이 더 작은 동전들로 나누어 떨어지지 않는 경우 욕심쟁이 방법을 사용할 수 없다.
2. 동전의 종류가 n개면 시간 복잡도는 O(n^2)이다. → O(n)
3. 동전의 액면가가 큰 것부터 욕심을 부려 최대한 사용해서 거스름돈을 만든다.
4. 동전의 종류가 500원, 100원, 50원, 10원이면 거스름돈 750원에 대한 최적해는 3개이다. → 500, 100, 100, 50 : 4개

정답: 3번

15번. 다음 중 최소 신장 트리를 구하는 알고리즘은?

1. 크루스칼 알고리즘: 최소 신장 트리
2. 플로이드 알고리즘: 최단경로
3. 데이크스트라 알고리즘: 최단경로
4. KMP 알고리즘: 문자열

정답: 크루스칼 알고리즘

16번. 다음 작업에 대한 작업 스케줄링 문제의 최적해를 구하려고 한다. 가장 먼저 기계에 할당하는 작업은?

시작하는 시간이 가장 빠른 작업을 기계에 할당한다.

정답: t5

17번. 텍스트에 abcdbcdcdd를 허프만 코딩으로 인코딩하였을 때 가장 짧은 코드가 부여되는 문자는?

사용이 많이 될수록 짧은 코드가 부여된다.

정답: d

18번. 비교 기반의 정렬 알고리즘이 아닌것은?

기수 정렬은 분포를 이용한 정렬 방식이다.

정답: 기수 정렬

19번. 다음 데이터에 대해서 왼쪽에서 오른쪽으로 진행하는 버블 정렬의 하나의 단계를 수행한 후의 데이터를 바르게 나열한 것은?

버블 정렬은 인접한 두 값을 비교하여 정렬을 수행해나가는 알고리즘이다.

20 60 10 70 80 30 50 40

20 60 10 70 30 80 50 40

20 60 10 70 30 50 80 40

20 60 10 70 30 50 40 80

정답: 20 60 10 70 30 50 40 80

20번. 오름차순으로 정렬하는 선택 정렬에 대한 설명으로 적절하지 못한 것은?

1. 데이터의 입력 상태에 따라 성능이 달라진다. → 언제나 동일한 시간복잡도 O(n^2)를 가진다.
2. 제자리 정렬 알고리즘이다.
3. 주어진 데이터 중에서 가장 작은 값부터 골라서 차례대로 나열한다.
4. 안정적이지 않은 정렬 알고리즘이다.

정답: 1번

21번. 삽입 징럴열 적용할 때 가장 좋은 성능을 나타내는 입력 데이터의 상태는?

삽입 정렬은 거의 정렬된 상태에서 가장 성능이 좋다. → O(n)

정답: 3번(10, 20, 30, 40, 50, 60)

22번. 삽입 정렬의 단점을 보완한 정렬 알고리즘은?

삽입 정렬은 위치를 찾기 위해 한 번에 한 자리씩만 이동하여 데이터의 이동이 불필요하게 발생하는 문제가 있다. 셸 정렬은 데이터가 삽입될 위치에서 멀리 떨어져 있어도 바로 왼쪽의 이웃한 데이터와의 비교를 통해 한번에 한 자리씩만 이동

정답: 셸 정렬

23번. 평균적인 성능이 O(nlogn)인 안정적인 정렬 알고리즘은?

안정적인 nlogn 정렬 알고리즘은 합병정렬만 다루었다.

퀵 정렬과 힙 정렬은 안정적인 정렬 알고리즘이 아니다.

정답: 합병 정렬

24번. 비교 기반 알고리즘 중에서 정렬 과정에서 입력 크기에 비례하는 만큼의 추가적인 저장 공간을 요구하는 것은?

합병정렬은 배열을 더 이상 나눌 수 없을 때 까지 반으로 나눈 뒤 합치며 정렬하기 때문에 입력 크기에 비례하는 추가 저장공간이 요구된다.

정답: 합병 정렬

25번. 다음은 초기 힙을 배열로 표현한 것이다. 이 배열에 대해 오름차순으로 정렬하는 힙 정렬의 두 번째 단계를 한 번 수행한 후의 배열의 상태를 올바르게 표현한 것은?

80 60 70 40 20 30 50 10

1. 80과 10 교환
2. 재구축

정답: 70 60 50 40 20 30 10 80

26번. 주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방법에 대한 설명으로 적절한 것은?

1. 선형 시간의 성능을 갖는다.
2. 안정적이지 않은 정렬 알고리즘이다. → 안정적인 정렬 알고리즘이다.
3. 제자리 정렬 알고리즘이다. → 제자리 정렬이 아니다. 각 수의 누적값을 구하기 위해 키 값에 비례하는 추가 공간이 필요하다.
4. 비교 기반의 알고리즘이다. → 분포를 이용한 정렬 알고리즘이다.

27번. 이진 탐색 트리에서 최악의 탐색 성능을 갖는 경우의 트리의 높이는?

모든 노드에서 자식이 1개 이하인 경우(경사트리) 최악의 탐색 성능을 갖는다. 따라서 높이는 노드의 갯수 n과 동일하다.

정답: n

28번. 이진 탐색 트리에서 노드 35를 삭제하려고 한다. 삭제되는 노드 35 자리에 위치하는 노드는?

삭제될 노드의 자식 노드가 2개 이상인 경우, 삭제될 노드의 후속자 노드를 선택한다. 후속자 노드의 선택은 왼쪽 서브 트리의 가장 오른쪽 노드로 정하거나, 오른쪽 서브 트리의 가장 왼쪽 노드로 정하면 된다. (교재에서는 오른쪽 서브 트리의 가장 왼쪽 노드를 선택한다. 양쪽 서브트리가 다 있는 경우 오른쪽 서브트리를 선택하자)

정답: 40

29번. 흑적 트리의 설명으로 적절한 것은?

1. 루트 노드는 적색이다. → 루트 노드와 리프 노드는 흑색이다.
2. 모든 리프 노드의 레벨은 동등하다. → 다를 수도 있다.
3. 어떤 노드가 적색이면 부모 노드는 항상 흑색이다.
4. 임의의 노드에서 리프 노드까지의 경로 상에 존재하는 적색 노드의 개수는 동일하다. → 적색 노드가 아닌 흑색 노드의 개수가 동일하다.

30번. t=2인 B-트리에서 70을 삽입하는 과정에서 부모 노드로 보내지는 키값은 무엇인가?

t가 2이기 때문에, 2t-1인 노드를 만났을 때 키를 분할한다. 이때 해당 노드의 가운데 있던 값을 부모 노드로 보내진다.

70은 루트 노드(30, 50)의 두 값보다 크기 때문에 우측 서브트리로 보내지고, 우측 서브트리는 3개의 값을 가지고 있기 때문에 80을 부모노드로 올려준다.

3번

31번. 다음 중 충돌 해결 방법이 아닌 것은?

충돌 해결 방법

• 개방 해싱(연쇄법)
• 폐쇠 해싱(개방 주소법): 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

1. 제산 잔여법
2. 이중 해싱
3. 이차 탐사
4. 선형 탐사

정답: 1번

32번. 다음 중 NP-완전 문제가 아닌 것은?

1. 무방향 그래프에서 모든 정점을 한 번씩만 지나가는 사이클의 존재 여부를 확인하는 문제 → 외판원 문제
2. 하나의 정점에서 다른 모든 정점으로의 가장 짧은 경로를 구하는 문제 → 다익스트라 알고리즘
3. 정규곱형으로 주어진 논리식을 참으로 만들 수 있는 지 판단하는 문제 → CNF 만족성 문제
4. n개의 양의 정수가 주어졌을 때, 각 집한에 포함된 수의 합이 동일하도록 n개의 정수를 두 개의 집합으로 나눌 수 있는지 판정하는 문제 → 파티션 문제

정답: 2번

33번. 어떤 문제 A가 NP-완전 문제라는 설명으로 적합한 것은?

클래스 NP의 모든 문제가 문제 A로 다항식 시간 변환되며 A가 클래스 NP에 속하는 경우

정답: 2번

34번. 다음 설명에 대한 유전 알고리즘의 연산은?

• 부모의 형질을 나누어 갖는 연산이다.
• 다른 최적화 방법과 구별짓는 연산이다.

교차 : 부모 염색체들을 교차점을 기준으로 부모들의 성질을 나누어 갖는 연산

정답: 교차

35번. 외판원 문제에 가장 적합한 염색체 인코딩 방법은?

n개의 정점을 1부터 n까지의 숫자로 보고 이를 순열로 인코딩한다.

정답: 순열 인코딩