knou_algorithm_quiz.md

알고리즘 기출문제

기말고사

2019

[!quiz] 문제 (1) 이론적으로 문제 해결이라는 관점에서 반드시 만족하지 않아도 되는 알고리즘의 조건은?

1. 유효성
2. 명확성
3. 효율성
4. 유한성

[!warning]- answer 답 : 3 풀이 : 알고리즘은 반드시 입출력 (0개 이상의 외부 입력과 하나 이상의 출력), 명확성 (각 명령은 모호하지 않고 단순 명확함), 유한성 (한정된 수의 단계를 거친 후에는 반드시 종료함), 유효성 (모든 명령은 컴퓨터에서 수행 가능함) 조건을 만족해야 함. 다시 정의하면, 알고리즘은 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령들을 순서적으로 구성한 것임. 하지만 알고리즘이 존재하는 문제일지라도 컴퓨터로 해결하는데 현실적으로 처리 결과를 기다릴 수 없을 정도의 상당히 긴 처리 시간을 요구하는 문제도 있음 - 따라서, 알고리즘은 효율성을 보장하지 않고, 반드시 만족하지 않아도 됨.

[!quiz] 문제 (2) 연결 리스트의 특정 노드에서 선행 노드와 후행 노드에 대한 접근이 모두 가능한 것은?

1. 단일 원형 연결 리스트
2. 이중 연결 리스트
3. 단일 연결 리스트
4. 순차 연결 리스트

[!warning]- answer 답 : 2 풀이 : 이중 연결 리스트에 각 노드는 3개의 필드를 가짐 - 선행 노드 링크, 데이터, 후행 노드 링크;

[!quiz] 문제 (3) 다음 빈 칸에 알맞은 용어는? ![[Pasted image 20230611111358.png|500]]

1. 경로
2. 차수
3. 연결
4. 사이클

[!warning]- answer 답 : 1 풀이 :

[!quiz] 문제 (4) 알고리즘의 대표적인 설계 기법으로 거리가 먼 것은?

1. 동적 프로그래밍 방법
2. 욕심쟁이 방법
3. 상각분석 방법
4. 분할정복 방법

[!warning]- answer 답 : 3 풀이 :

[!quiz] 문제 (5) 입력 크기 $n$ 에 대한 알고리즘 수행시간 $f(n) = 5n^3 + 10n^2 + 8n + 200$ 을 점근 성능으로 올바르게 나타낸 것은?

1. $O(1)$
2. $O(n)$
3. $O(n^2)$
4. $O(n^3)$

[!warning]- answer 답 : 4 풀이 :

[!quiz] 문제 (6) 단위 연산의 수행시간이 $1ns$ ($10^{-9}$ 초)인 컴퓨터에서 $10^9$ 개의 데이터를 처리하는데 가장 오랜 시간이 걸리는 알고리즘의 성능을 나타내는 점화식은?

1. $T(n) = 2T(\frac{n}{2}) + \Theta(n)$, $T(1) = \Theta(1)$
2. $T(n) = T(n-1) + \Theta(1)$, $T(1) = \Theta(1)$
3. $T(n) = T(\frac{n}{2}) + \Theta(1)$, $T(1) = \Theta(1)$
4. $T(n) = T(n-1) + \Theta(n)$, $T(1) = \Theta(1)$

[!warning]- answer 답 : 1 풀이 :

[!quiz] 문제 (7) 분할정복 방법을 적용한 알고리즘 중에서 입력 크기 $n$ 에 대한 성능이 가장 우수한 것은?

1. 퀵 정렬
2. 이진 탐색
3. 배낭 문제
4. 합병 정렬

[!warning]- answer 답 : 2 풀이 :

• 이진 탐색 성능 : $T(n) = T(\frac{n}{2}) + \Theta(1) \rightarrow O(log n)$
• 합병 정렬 성능 : $T(n) = 2T(\frac{n}{2}) + \Theta(n) \rightarrow O(n log n)$
• 퀵 정렬 성능 : 최악 $T(n) = T(n-1) + \Theta(n) \rightarrow O(n^2)$ , 최선 $T(n) = 2T(\frac{n/2}) + \Theta(n) \rightarrow O(n log n)$, 평균 $O(n log n)$
• 배낭 문제는 분할정복 알고리즘이 아님.

[!quiz] 문제 (8) 분할정복 방법에서 각 순환 호출시마다 거치는 작업 단계가 아닌 것은?

1. 정렬
2. 정복
3. 분할
4. 결합

[!warning]- answer 답 : 1 풀이 : 분할정복 방법은 주어진 문제를 여러 개의 작은 문제로 분할하고, 문제가 더 이상 분할되지 않을 정도로 충분히 작다면 작은 문제의 해를 구하며 (정복), 이후에 작은 문제들의 해를 결합하여 원래 문제의 해를 구함. 결합 단계가 없는 알고리즘도 있긴 있음. 하지만 여기서 답은 정렬임. 이거 좀 애매모호 한 듯?? 퀵 정렬은 순환 할 때마다 정렬하는게 아닌가??

[!quiz] 문제 (9) 다음과 같은 데이터에 대해서 퀵 정렬의 분할 함수 $Partition()$ 을 한 번 적용한 후 왼쪽 부분배열에 존재하는 데이터의 개수는? (단, 피벗은 맨 왼쪽 원소이고, 오름차순으로 정렬한다.) ![[Pasted image 20230611112644.png|500]]

1. 2
2. 4
3. 6
4. 8

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (10) 퀵 정렬에서 최악의 성능이 발생하지 않는 경우는? (단, 피벗은 맨 왼쪽 원소이다.)

1. 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
2. 피벗이 항상 부분배열에서 최솟값이 되는 경우
3. 입력 데이터가 정렬되어 있는 경우
4. 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우

[!warning]- answer 답 : 1 풀이 :

[!quiz] 문제 (11) 다음과 입력 크기 $38$ 인 배열의 원소를 $7$ 개의 그룹 ($G_{1}$ ~ $G_{7}$) 으로 구성한 모습이다. 최악 $O(n)$ 으로 $i$ 번째로 작은 원소를 찾기 위한 선택 문제에서 피벗 (중간값들의 중간값) 으로 선택되는 원소는? ![[Pasted image 20230611113048.png|300]]

1. 27
2. 36
3. 43
4. 50

[!warning]- answer 답 : 풀이 : 문제를 이해할 수 없음.

[!quiz] 문제 (12) 동적 프로그래밍 방법에 대한 설명으로 적당하지 못한 것은?

1. 모든 정점 간의 최단 경로 문제와 스트링 편집 거리 문제에 적용된다.
2. 상향식 접근 방법이다.
3. 최적성의 원리가 만족되는 문제에만 적용할 수 있다.
4. 소문제들은 서로 독립적이다.

[!warning]- answer 답 : 4 풀이 : 동적 프로그래밍 방법은 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법이다. 이때 소문제들이 서로 독립일 필요는 없다 - 분할정복 방법에서는 분할된 작은 문제들이 서로 독립적이어서 한번 사용한 소문제의 해는 더 이상 필요하지 않지만, 동적 프로그래밍 방법에서는 한 번 사용한 소문제의 해가 다음에 또 사용될 수 있으므로 이 해를 테이블에 저장해 두고 필요할 때마다 바로 사용한다.

[!quiz] 문제 (13) 피보나치 수열 $f(n)$ 에서 $f(7)$ 은 얼마인가? (단, $f(0) = 0$, $f(1) = 1$) 이다.)

1. 8
2. 11
3. 13
4. 21

[!warning]- answer 답 : 3 풀이 : $f(n) = f(n-1) + f(n-2)$, $f(0), .., f(7) = 0, 1, 1, 2, 3, 5, 8, 13$

[!quiz] 문제 (14) 동적 프로그래밍 방법을 적용하여 $n$ 개의 행렬에 대한 연쇄적 곱셈 문제를 해결하는 알고리즘의 시간 복잡도는?

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

[!warning]- answer 답 : 4 풀이 : 연쇄 행렬 곱셈 문제는 n 개의 행렬을 곱하는 방식 중 최소의 기본 곱셈 횟수를 가진 행렬의 곱셈 순서를 구하는 것이다. 알고리즘의 시간 복잡도는 $O(n^3)$ 이다.

[!quiz] 문제 (15) 다음은 플로이드 알고리즘을 간략히 정리한 것이다. 이 알고리즘의 성능 표현으로 올바른 것은? ![[Pasted image 20230611113618.png|300]]

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

[!warning]- answer 답 : 4 풀이 : 플로이드 알고리즘은 모든 정점 간의 최단 경로를 구하는 대표적인 알고리즘이다. 플로이드 알고리즘은 초기화, 그리고 최단 경로 생성으로 이루어진다 - 초기화는 인접 행렬의 크기만큼 시간이 걸리므로 입력 정점의 개수의 제곱에 비례하되, 최다 경로 생성은 입력 정점의 개수에 비례한 삼중 루프로 구성되어 있다. 따라서, 알고리즘의 시간 복잡도는 $O(n^3)$ 이다 ($|V|=n$).

[!quiz] 문제 (16) 다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하였을 때 얻게 되는 최대 이익은? (단, 물체를 쪼갤 수 있다.) ![[Pasted image 20230611131507.png|500]]

1. 35
2. 38
3. 42
4. 49

[!warning]- answer 답 : 3 풀이 : 물체를 한개씩만 넣는다는 가정하에, 이익 20 (무게 5) + 이익 15 (무게 3) + 이익 7 (무게 2) = 42

[!quiz] 문제 (17) 욕심쟁이 방법을 적용하여 최소 신장 트리를 구하는 알고리즘으로만 나열된 것은?

1. 크루스칼 알고리즘, 플로이드 알고리즘
2. 프림 알고리즘, 크루스칼 알고리즘
3. 데이크스트라 알고리즘, 프림 알고리즘
4. 플로이드 알고리즘, 데이크스트라 알고리즘

[!warning]- answer 답 : 2 풀이 :

• 신장 트리 (Spanning Tree) 란 주어진 그래프에서 모든 정점을 포함하는 연결된 트리로, 그래프의 정점이 n 개이면 신장 트리에는 사이클이 존재하지 않으므로 정확히 (n-1) 개의 간선이 존재한다. 최소 신장 트리 (Minimum Spanning Tree) 는 간선 (u, v) 마다 가중치 w(u, v) 를 가진 연결된 가중 무방향 그래프 G = (V, E) 에 대해서 가능한 모든 신장 트리 중 트리에 모든 간선 가중치의 합이 최소인 신장 트리를 뜻한다.
• 크루스칼 알고리즘은 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 (욕심쟁이) 하나씩 사이클을 만들지 않는 간선을 추가시켜 최소 신장 트리를 만드는 방식이다.
• 프림 알고리즘은 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가면서 최소 신장 트리를 구하는 방법이다.

[!quiz] 문제 (18) 주어진 그래프에 대한 최소 신장 트리의 가중치의 합은? ![[Pasted image 20230611114012.png|150]]

1. 15
2. 16
3. 17
4. 18

[!warning]- answer 답 : 2 풀이 : 크루스칼 알고리즘 방식으로 풀면 1 + 2 + 3 + 4 + 6 이 나옴

[!quiz] 문제 (19) 욕심쟁이 방법을 적용한 작업 선택 문제에서 기계에 가장 먼저 할당되는 작업은? ![[Pasted image 20230611114118.png|500]]

1. $t_{1}$
2. $t_{4}$
3. $t_{6}$
4. $t_{7}$

[!warning]- answer 답 : 1 풀이 : 작업 스케줄링 (Task Scheduling) 문제는 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제이다. $T$ 를 기계에서 수행되는 $n$ 개의 작업 $t_1, t_2, \cdots, t_n$ 으로 이루어진 집합이라고 할때, 각 작업 $t_i$ 는 시작하는 시간 $s_i$ 과 끝나는 시간 $f_i$ 으로 이루어진 쌍으로 표시된다 $t_i(s_i, f_i)$ . 욕심쟁이 방법으로 해결하면 각 단계에서 시작 시간이 바른 작업이 우선적으로 선택해서, 충돌이 발생하지 않으면 해당 기계에 배정하고, 충돌되면 새 기계에 할당한다 - 이러한 과정을 반복하면 전체적인 최적해를 구할 수 있다.

[!quiz] 문제 (20) 정렬 방식의 관점에서 나머지와 다른 하나의 정렬 알고리즘은?

1. 버블 정렬
2. 셸 정렬
3. 힙 정렬
4. 계수 정렬

[!warning]- answer 답 : 4 풀이 :

• 정렬(sort)은 여러 데이터로 구성된 리스트에서 값의 크기 순서에 따라 데이터를 재배치하는 것이다.
• 정렬은 4 가지 개념으로 알아볼 수 있다 - 내부 정렬, 외부 정렬, 안정적 정렬, 제자리 정렬.
• 내부 정렬은 데이터를 주기억장치에 저장한 후 정렬하는 방식이고, 외부 정렬은 데이터를 보조기억장치에 저장한 채 그중 일부만 반복적으로 주기억장치로 읽으 들여서 정렬하는 방식이다.
• 정렬 알고리즘이 '안정적'이라는 것은 동일한 값을 갖는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지됨을 의미한다.
• 정렬 알고리즘에 할당되는 저장공간이 오버헤드가 없이 입력 데이터를 저장한 공간만 사용하는 경우 '제자리(in-place)' 정렬이라 한다.
• 비교 기반 정렬 알고리즘으로 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 그리고 힙 정렬이 있다.
• 값을 비교하지 않고 데이터 분포에 기반한 방식의 정렬 알고리즘으로 계수 정렬과 기수 정렬 등이 있다.

[!quiz] 문제 (21) 안정적인 정렬 알고리즘은?

1. 버블 정렬
2. 힙 정렬
3. 퀵 정렬
4. 셸 정렬

[!warning]- answer 답 : 풀이 :

• 버블 정렬은 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복해서 정렬하는 방식이다. 비교되는 두 값이 동일한 경우 자리를 바꾸지 않기 때문에 안정적이라 할 수 있다.
• 힙 정렬은

[!quiz] 문제 (22) 주어진 데이터에 대해 버블 정렬을 적용하여 오름차순으로 정렬할 때 인접한 두 데이터 간의 자리바꿈이 발생하는 총 횟수는? ![[Pasted image 20230611114319.png|500]]

1. 8
2. 10
3. 12
4. 15

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (23) 정렬되지 않은 데이터 중에서 가장 작은 값을 골라서, 이 값과 미정렬 데이터 부분의 첫 번째 원소와 교환하는 방식의 정렬 알고리즘은? (단, 오름차순으로 정렬한다)

1. 삽입 정렬
2. 셸 정렬
3. 선택 정렬
4. 버블 정렬

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (24) 삽입 정렬에 대한 설명으로 적절하지 못한 것은?

1. 입력이 거의 정렬된 경우 빠른 수행 시간 O(n) 을 갖는다.
2. 안정적인 정렬 알고리즘이다.
3. 셸 정렬의 단점을 보완한 방법이다.
4. 제자리 정렬 알고리즘이다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (25) 수행시간이 O(nlogn) 이지만 제자리 정렬 알고리즘이 아닌 것은?

1. 셸 정렬
2. 합병 정렬
3. 퀵 정렬
4. 힙 정렬

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (26) 합병 정렬과 퀵 정렬에 대한 공통적인 설명으로 올바른 것은?

1. 평균의 경우 O(nlogn) , 최악의 경우 O(n^2) 의 성능을 갖는다.
2. 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지된다.
3. 입력 데이터를 저장하는 공간 이외에 상수 개를 초과하는 추가적인 저장 공간이 필요하다.
4. 분할정복 방법이 적용되었다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (27) 주어진 데이터를 오름차순으로 힙 정렬하기 위해 초기 힙을 구성하였다. 이때 루트 노드에 존재하는 데이터는? ![[Pasted image 20230611114820.png|500]]

1. 7
2. 15
3. 40
4. 88

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (28) 기수 정렬에 대한 설명으로 올바른 것은?

1. 비교 기반의 정렬 알고리즘이다.
2. 입력 원소의 값의 자릿수가 상수일 때 유용하다.
3. 제자리 정렬 알고리즘이다.
4. 시간 복잡도 O(n^2) 을 갖는다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (29) 순차 탐색에 대한 설명으로 틀린 것은?

1. 무순서 데이터에 비해 정렬된 데이터에 대해 보다 효과적인 탐색이 가능하다.
2. 모든 데이터 리스트에 적용 가능하다.
3. n 개의 데이터에 대한 최대 비교 횟수는 n 번이다.
4. 데이터가 많은 경우에는 적합하지 못한 방법이다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (30) 이진 탐색에 대한 설명으로 적절하지 못한 것은?

1. 최악의 경우의 탐색 성능은 O(logn) 이다.
2. 정렬된 리스트에 대해서만 적용 가능하다.
3. 삽입과 삭제가 빈번한 경우에는 적합하지 않다.
4. 연결 리스트로 구현하면 보다 효과적인 탐색이 가능하다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (31) 흑적 트리에 대한 설명으로 적절한 것은?

1. 루트 노드는 흑색이거나 적색이다.
2. 임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 적색 노드가 존재한다.
3. 흑색 노드가 연달아 나타날 수 없다.
4. 이진 탐색 트리의 형태를 갖는 균형 탐색 트리이다.

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (32) 모든 리프 노드의 레벨이 동일한 트리는?

1. 흑적 트리
2. 이진 탐색 트리
3. 완전 이진 트리
4. B-트리

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (33) 탐색 방법 중에서 최악의 경우의 성능이 나머지와 다른 하나는?

1. 이진 탐색
2. 흑적 트리
3. 이진 탐색 트리
4. B-트리

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (34) 데이터들이 연속된 위치를 점유하여 클러스터를 형성하고 이것이 점점 커지는 현상으로 인해 평균 탐색 시간의 증가를 초래하는 충돌 해결 방법은?

1. 선형 탐사
2. 이중 해싱
3. 이차 탐사
4. 연쇄법

[!warning]- answer 답 : 풀이 :

[!quiz] 문제 (35) NP-완전 문제의 근사 알고리즘이다. 이를 통해 해결할 수 있는 문제는? ![[Pasted image 20230611115458.png|500]]

1. 버텍스 커버 문제
2. 외판원 문제
3. CNF-만족성 문제
4. 클리크 판정 문제

[!warning]- answer 답 : 풀이 :

출석대체시험

2019

[!quiz] 알고리즘 생성 단계 중에서 시간 복잡도 및 공간 복잡도를 계산하는 단계는?

1. 정확성 분석
2. 알고리즘 기술
3. 효율성 분석
4. 알고리즘 설계

[!warning]- answer 답 : (3) 풀이 : 알고리즘의 효율성은 필요한 수행 시간과 공간(메모리)에 따라 계산된다.

[!quiz] 선형 자료구조 중에서 데이터에 대한 임의 접근을 제공하는 것은?

1. 큐
2. 배열
3. 연결 리스트
4. 그래프

[!warning]- answer 답 : (2) 풀이 : 배열은 인덱스-원소값 쌍의 집합으로, 하나의 인덱스가 주어지면 이와 연관된 원소값이 결정되는 대응 관계를 갖는다. 따라서, 배열은 인덱스를 이용해서 빠른 임의 접근이 가능하다.

[!quiz] 다음 트리에 대한 설명 중 틀린 것은? ![[Pasted image 20230527092519.png]]

1. 트리의 차수는 3이다.
2. 노드의 차수가 0인 노드의 개수는 7이다.
3. 노드 D의 후손 노드의 개수는 노드 L의 조상 노드의 개수보다 많다.
4. 트리의 레벨은 4이다.

[!warning]- answer 답 : (4) 풀이 : 노드의 레벨은 있지만 트리의 레벨이란 없다. 트리의 높이/깊이는 4 이다.

[!quiz] 전 이진 트리(full binary tree)에서 루트 노드를 포함한 비단말 노드가 3개인 경우 단말 노드의 개수는?

1. 2
2. 3
3. 4
4. 6

[!warning]- answer 답 : (3) 풀이 : 전 이진 트리의 비단말 노드의 개수는 언제나 단말 노드의 개수보다 1개 적다 ($n_{0}-1$). 반대로, 단말 노드는 비단말 노드보다 1개 많다. 교과서 16 페이지 참고.

[!quiz] 알고리즘의 시간 복잡도에 대한 설명으로 틀린 것은?

1. 입력 데이터의 상태에 따라 달라진다.
2. 입력 크기에 대한 함수로 표현한다.
3. 알고리즘에서 기본 명령의 수행 횟수의 합으로 나타낸다.
4. 일반적으로 평균 수행 시간을 평가 척도로 사용한다.

[!warning]- answer 답 : (4) 풀이 : 수행 시간은 기본 명령의 수행 횟수의 합으로 나타내되, 일반적으로 다양한 상태의 데이터로 알고리즘의 수행 시간을 계산하여 그 중 최악의 수행 시간이 평가 척도로 사용된다.

[!quiz] 점근 성능의 표기법 중에서 최악의 수행 시간만 나타낼 때 적합한 것은?

1. $O$ ("big-oh")
2. $\Omega$ ("big-omega")
3. $\Theta$ ("big-theta")
4. $\Phi$ ("big-phi")

[!warning]- answer 답 : (1) 풀이 : #todo 교과서에서 제대로 설명되지 않음. 일반적으로 사용되는게 O 표기법이니 이것이 답!

[!quiz] 분할정복 방법의 분할 과정에서 입력 크기 n인 문제가 일정하기 않은 크기의 두 개의 작은 문제로 분할되는 알고리즘은?

1. 합병 정렬
2. 이진 탐색
3. 퀵 정렬
4. 동전 거스름돈 문제

[!warning]- answer 답 : (3) 풀이 : 퀵 정렬은 피벗(pivot)을 기준으로 주어진 배열을 두 개의 부분배열로 분할한다. 피벗은 랜덤하게 선택되기 때문에 부분배열의 크기가 일정하지 않다.

[!quiz] 다음과 같이 주어진 데이터에 대해 적절한 처리를 거친 후 이진 탐색을 적용하였을 때 접근 시간이 가장 빠른 데이터는? $60\ 25\ 40\ 35\ 50\ 55\ 20\ 45\ 30$

1. 20
2. 30
3. 40
4. 50

[!warning]- answer 답 : (3) 풀이 : 이진 탐색은 원하는 값과 중앙값을 비교하여 중앙값 리턴 또는 왼쪽/오른쪽 부분배열을 대상으로 탐색을 순환하는 알고리즘이다. 주어진 데이터 그대로 보면 중앙값인 $50$ 에 대한 접근 시간이 가장 빠르지만, 데이터를 정렬하면 중앙값은 $40$ 이 된다.

[!quiz] 분할정복 방법을 적용한 알고리즘 중에서 결합 단계를 거쳐야만 하는 것은?

1. 퀵 정렬
2. 합병 정렬
3. 이진 탐색
4. 분할함수를 이용한 선택 문제

[!warning]- answer 답 : (2) 풀이 : 합병 정렬(merge sort)은 입력 데이터를 2개의 부분배열로 분리하며 각 부분배열을 또 다시 분리함을 반복하고, 더 이상 분리될 수 없을 때 다시 결합하면서 값들을 비교하는 방식으로 하는 알고리즘이다.

[!quiz] 차원이 각각 $3 \times 2$, $2 \times 4$, $4 \times 1$ 인 세 개의 행렬 $M_{1}$, $M_{2}$, $M_{3}$ 을 연쇄적으로 곱하는 데 필요한 최소의 기본 곱셈 횟수는?

1. 14
2. 20
3. 24
4. 36

[!warning]- answer 답 : (1) 풀이 : 교과서.. 참고해봤자?

[!quiz] 다음 중 동적 프로그래밍을 적용한 알고리즘은?

1. 데이크스트라 알고리즘
2. 프림 알고리즘
3. 플로이드 알고리즘
4. 크루스칼 알고리즘

[!warning]- answer 답 : (3) 풀이 : 동적 프로그래밍 방법은 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법이다. 특히 최적성의 원리(Principle of Optimality)가 반드시 성립하는 최적화 문제가 동적 프로그래밍 방법의 대상이 된다. 플로이드 알고리즘은 모든 정점에서 모든 정점으로 단계적으로 범위를 늘려 가면서 모든 정점 간의 최단 경로를 구하는 알고리즘이다. #todo 좀 더 알아봐야 할듯.. 교과서는 좀 개같다.

[!quiz] 그래프 G=(V,E) 에 대한 플로이드 알고리즘의 설명으로 적절하지 못한 것은?

1. 시간 복잡도는 O(|V|^3) 이다.
2. 단일 출발점에서 다른 모든 정점으로의 최단 경로를 구한다.
3. 간선의 인접 행렬 표현을 활용한다.
4. 점화식을 이용하여 주어진 문제의 해를 구한다.

[!warning]- answer 답 : (2) 풀이 : 정답표에 2번이 답변이라고 되어있는데, 모호성이 있는지 모든 답 인정해준다고 표시됨. 일단 플로이드 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 한꺼번에 구하는 알고리즘이다. 근데 어떻게 보면 2번이 틀린 것은 아닌듯.

[!quiz] 욕심쟁이 방법에 대한 설명으로 적절하지 못한 것은?

1. 각 단계에서 여러 최적해를 고려한 후 다음 단계로 넘어간다.
2. 최적화 문제 해결에 주로 사용된다.
3. 동전의 액면가가 임의로 주어지는 동전 거스름돈 문제에는 적용할 수 없다.
4. 전체적인 최적해를 구하지 못할 수도 있다.

[!warning]- answer 답 : (1) 풀이 : 욕심쟁이 방법은 언제나 현재 주어진 옵션 중에서 최선을 선택한다는 것이 메인 특성이다.

[!quiz] 다음 중 욕심쟁이 방법으로 해결 가능한 문제는?

1. 음의 가중치를 갖는 간선이 없는 데이크스트라 알고리즘
2. 오름차순으로 정렬하는 퀵 정렬 알고리즘
3. 추의 무게와 물체의 무게가 모두 정수인 저울 문제
4. 가중치의 합이 음수인 사이클이 존재하지 않는 플로이드 알고리즘

[!warning]- answer 답 : (1) 풀이 : 도대체 어떤 병신이 이런 문제를 만드는 거지?

[!quiz] 허프만 코딩에 대해 설명으로 적절하지 못한 것은?

1. 가변 길이 변환 코드를 사용한다.
2. 특정 텍스트에 대한 허프만 트리는 유일하다.
3. 허프만 코딩은 접두부 코드이다.
4. 허프만 트리는 전 이진트리이다.

[!warning]- answer 답 : (2) 풀이 :

• 허프만 코딩(Huffman coding) 은 문자의 빈도 또는 확률 정보를 이용하는 통계적 압축 방법이다.
• 인코딩 과정은 1) 주어진 텍스트에서 각 문자의 출현 빈도수를 계산하고, 2) 각 문자의 빈도수를 기준으로 허프만 트리를 생성하여 각 문자에 이진 코드를 부여한 후, 3) 각 문자를 부여된 이진 코드로 변환함으로서 압축된 텍스트를 생성한다.
• 허프만 트리 생성 과정은 1) 각 문자가 하나의 노드로 구성된 개별적인 트리로 표현하며, 각 노드를 빈도수로 표시, 2) 빈도수가 작은 두 트리의 빈도수의 합을 가진 부모 노드를 생성함으로 보다 큰 트리를 만들고, 3) 합친 트리의 좌우 두 간선은 각각 0과 1로 표시, 4) 루트 노드 값을 기준으로 계속 트리들을 합쳐가길 반복.

2009

[!quiz] 그래프에서 정점 $v1$ 에서 $vn$ 까지의 ( )라는 것은 간선으로 연결된 정점들의 순차열 $v1, v2, ⋯, vn$ 이다. 빈 칸에 들어갈 알맞은 용어는 무엇인가?

1. 차수
2. 길이
3. 경로
4. 깊이

[!warning]- answer 답 : (3) 경로 풀이 : 경로 정의

[!quiz] 다음과 같은 이진 트리를 무엇이라고 하는가? ![[Pasted image 20230527084343.png|200]]

1. 전 이진 트리
2. 포화 이진 트리
3. 완전 이진 트리
4. 경사 이진 트리

[!warning]- answer 답 : (1) 전 이진 트리 풀이 : 전 이진 트리 (Full Binary Tree)는 모든 노드의 차수가 $0$ 또는 $2$ 인 이진 트리이다.

[!quiz] 배낭 문제에 가장 효과적으로 적용될 수 있는 알고리즘 설계기법은?

1. 분할 정복 방법
2. 상각 분석 방법
3. 동적 프로그래밍 기법
4. 욕심쟁이 방법

[!warning]- answer 답 : (4) 욕심쟁이 방법 풀이 :

• 배낭 문제는 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제이다.
• 배낭 문제의 최적 해(Optimal Solution) 는 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 담는 것이다.
• 욕심쟁이 방법은 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인(Local) 최적해를 선택함으로써 전체적인(Global) 최적해를 구하는 방법이다.
• 물체를 쪼개서 넣을 수 있다는 가정하에 욕심쟁이 방법이 배낭 문제에 가장 효과적이다.

참고 : 4장

다음 그래프가 의미하는 점근적 표기법에 해당하는 것은 어느 것인가? ![[Pasted image 20230527084940.png|200]]

1. f(n)=O(g(n))
2. f(n)=Ω(g(n))
3. f(n)=o(g(n))
4. f(n)=Θ(g(n))

답 :