세상... 직장과 병행하는 분들은 진도를 다 따라잡으시는지 궁금하다.. 이번 일요일에 출석수업이 잡히게 되었다 강의를 정리하며 블로그에 작성을 하지만 정리할 틈도없이 회사일도 바쁘게 흘러감에 따라 시간을 내 공부를 못하고 출근길에 인터넷 강의를 들으며 하고있다.. 쉽지않네요 블로그 글 보시는 분들 모두 이번 출석시험 좋은 결과 있으시길 바라며 모든 저작권은 방통대에 있습니다.
문제별로 접은글로 달아 두었습니다 한번 풀어보시고 해설 바로 보시면 될 것 같습니다!
잘못 작성 하였거나, 잘 안풀리는거 있음 댓글 달아주세요!
31 알고리즘 생성 단계 중에서 시간 복잡도 및 공간 복잡도를 계산하는 단계는?
1. 정확성 분석
2. 알고리즘 기술
3. 효율성 분석
4. 알고리즘 설계
31. 알고리즘 생성 단계 중에서 시간 복잡도 및 공간 복잡도를 계산하는 단계는?
해설: 알고리즘 생성 과정에서 시간 복잡도와 공간 복잡도를 분석하는 단계는 효율성 분석 단계입니다. 이 단계에서는 알고리즘의 수행 시간과 메모리 사용량을 평가하여 효율성을 판단합니다. 정확성 분석은 알고리즘이 올바른 결과를 도출하는지를 확인하는 단계이고, 알고리즘 기술은 pseudo-code나 코드로 작성하는 단계, 알고리즘 설계는 문제를 해결하기 위한 전략을 구상하는 단계입니다.
정답: 3. 효율성 분석
32 선형 자료구조 중에서 데이터에 대한 임의 접근을 제공하는 것은?
1. 큐
2. 배열
3. 연결 리스트
4. 그래프
32. 선형 자료구조 중에서 데이터에 대한 임의 접근을 제공하는 것은?
해설: 임의 접근(random access)은 특정 인덱스의 데이터를 O(1) 시간에 접근할 수 있는 것을 의미합니다. 배열은 메모리 상에서 연속적으로 저장되어 있어 인덱스를 통해 즉시 접근 가능합니다. 반면, 큐와 연결 리스트는 순차적으로 데이터를 탐색해야 하며, 그래프는 비선형 자료구조입니다.
정답: 2. 배열
33. 다음 트리에 대한 설명 중 틀린 것은?
- 트리의 차수는 3이다.
- 노드의 차수가 0인 노드의 개수는 7이다.
- 노드 D의 후손 노드의 개수는 노드 L의 조상 노드의 개수보다 많다
- 트리의 레벨은 4인다
33번 정답과 해설
트리 구조:
- 루트 노드: A
- A의 자식: B, C, D
- B의 자식: E, F
- C의 자식: 없음
- D의 자식: G, H, I
- E의 자식: J
- F의 자식: K, L
- G의 자식: M
- H의 자식: N
- I, J, K, L, M, N의 자식: 없음
해설:
각 선택지를 검토해보겠습니다.
(1) 트리의 차수는 3이다.
- 각 노드의 차수(자식 노드의 개수):
- A: 3개 (B, C, D)
- B: 2개 (E, F)
- D: 3개 (G, H, I)
- F: 2개 (K, L)
- 나머지: 1개 또는 0개
- 트리의 차수는 최대 차수이므로 3입니다. (참)
(2) 노드의 차수가 0인 노드의 개수는 7이다.
- 차수가 0인 노드(단말 노드): C, I, J, K, L, M, N
- 총 7개입니다. (참)
(3) 노드 D의 후손 노드의 개수는 노드 I의 조상 노드의 개수보다 많다.
- 노드 D의 후손: G, H, I, M, N (5개)
- 노드 I의 조상: D, A (2개)
- 5 > 2이므로 참입니다. (참)
(4) 트리의 레벨은 4이다.
- 레벨 0: A
- 레벨 1: B, C, D
- 레벨 2: E, F, G, H, I
- 레벨 3: J, K, L, M, N
- 최대 레벨이 3이므로 트리의 높이는 3입니다. (거짓)
따라서 틀린 것은 ④번입니다.
정답: ④ 트리의 레벨은 4이다.
34 전 이진트리에서 루트 노드를 포함한 비단말 노드가 3개인 경우 단말 노드의 개수는?
1. 2
2. 3
3. 4
4. 6
34번 정답: 3. 4
해설: 전 이진트리에서 비단말 노드가 3개이면, 각 비단말 노드는 정확히 2개의 자식을 가집니다. 전 이진트리의 성질에 따라 단말 노드의 개수 = 비단말 노드의 개수 + 1 = 3 + 1 = 4개입니다.
35 알고리즘의 시간 복잡도에 대한 설명으로 틀린 것은?
1. 입력 데이터의 상태에 따라 달라진다
2. 입력 크기에 대한 함수로 표현한다.
3. 알고리즘에서 기본 명령의 수행 횟수의 합으로 나타낸다.
4. 일반적으로 평균 수행시간을 평가 척도로 사용한다.
35. 알고리즘의 시간 복잡도에 대한 설명으로 틀린 것은?
해설: 시간 복잡도는 입력 크기에 대한 함수로 표현되며, 기본 명령의 수행 횟수로 나타냅니다. 입력 데이터의 상태에 따라 최악, 평균, 최선 경우로 나뉘어 분석할 수 있습니다. 그러나 일반적으로 시간 복잡도는 최악의 수행시간을 평가 척도로 사용하며, 평균 수행시간은 특정 상황에서만 고려됩니다. 따라서 4번 설명이 틀렸습니다.
정답: 4. 일반적으로 평균 수행시간을 평가 척도로 사용한다.
36 점근 성능의 표기법 중에서 최악의 수행시간만을 나타낼 때 적합한 것은?
1. big-oh
2. big-omega
3. bit-theta
4. bit-phi
36. 점근 성능의 표기법 중에서 최악의 수행시간만을 나타낼 때 적합한 것은?
해설: 점근 표기법 중 Big-O는 알고리즘의 최악의 경우 상한을 나타냅니다. Big-Omega는 최선의 경우 하한, Big-Theta는 상한과 하한이 동일한 경우를 나타냅니다. Bit-Phi는 표준 표기법이 아닙니다. 따라서 최악의 수행시간을 나타낼 때는 Big-O가 적합합니다.
정답: 1. big-oh
37 분할정복 방법의 분할 과정에서 입력 크기 n인 문제가 일정하지 않은 크기의 두개의 작은 문제로 분할되는 알고리즘은?
1. 합병 정렬
2. 이진 탐색
3. 퀵 정렬
4. 동전 거스름돈 문제
37번 정답: 3. 퀵 정렬
해설: 퀵 정렬은 피벗을 기준으로 분할할 때, 피벗의 위치에 따라 두 부분의 크기가 일정하지 않을 수 있습니다. 합병 정렬과 이진 탐색은 항상 절반으로 균등하게 분할됩니다.
38 다음과 같이 주어진 데이터에 대해 적절한 처리를 거친 후 이진 탐색을 적용하였을때 접근 시간이 가장 빠른 데이터는?
list = [60, 25, 40, 35 50, 55, 20, 45, 30]
1. 20
2. 30
3. 40
4. 50
38번 정답: 3. 40
해설: 이진 탐색을 위해 먼저 정렬하면 [20, 25, 30, 35, 40, 45, 50, 55, 60]이 됩니다. 이진 탐색에서 가장 빠르게 접근할 수 있는 것은 중간값인 40입니다(첫 번째 비교에서 찾을 수 있음).
39 분할 정복 방법을 적용한 알고리즘 중에서 결합 단계를 거쳐야만 하는 것은?
1. 퀵정렬
2. 합병 정렬
3. 이진 탐색을
4. 분할함수를 이용한 선택 문제
39. 분할 정복 방법을 적용한 알고리즘 중에서 결합 단계를 거쳐야만 하는 것은?
해설: 분할 정복 알고리즘은 분할, 정복, 결합 단계로 구성됩니다. 합병 정렬은 분할된 부분 리스트를 정렬 후 결합(merge) 단계를 거쳐야 최종 정렬된 리스트를 얻습니다. 퀵 정렬은 결합 단계가 없으며, 이진 탐색과 선택 문제는 결과를 결합하지 않습니다.
정답: 2. 합병 정렬
40 차원이 각각 3x2, 2x4, 4x1인 세 개의 행렬 m1, m2, m3을 연쇄적으로 곱하는 데 필요한 최소의 기본 곱셈 횟수는?
1. 14
2. 20
3. 24
4. 36
40번 정답: 1. 14
해설: 행렬 연쇄 곱셈 문제입니다.
(M1×M2)×M3: (3×2×4) + (3×4×1) = 24 + 12 = 36
M1×(M2×M3): (2×4×1) + (3×2×1) = 8 + 6 = 14
최소값은 14입니다.
41 다음 중 동적 프로그래밍을 적용한 알고리즘은?
1. 데이크스트라 알고리즘
2. 프림 알고리즘
3. 플로이드 알고리즘
4. 크루스칼 알고리즘
41. 다음 중 동적 프로그래밍을 적용한 알고리즘은?
해설: 동적 프로그래밍은 하위 문제의 결과를 저장하여 중복 계산을 피하는 방법입니다. 플로이드 알고리즘(최단 경로 문제)은 동적 프로그래밍을 사용해 모든 정점 쌍 간의 최단 경로를 구합니다. 데이크스트라, 프림, 크루스칼 알고리즘은 욕심쟁이 방법에 기반합니다.
정답: 3. 플로이드 알고리즘
42 그래프G-(V,E)에 대한 플로이드 알고리즘의 설명으로 적절하지 못한 것은?
1. 시간복잡도는 O(|V|^3) 이다.
2. 단일 출발점에서 다른 모든 정점으로의 최단 경로를 구한다
3. 간선의 인접 행렬 표현을 활용한다.
4. 점화식을 이용하여 주어진 문제의 해를 구한다.
42번 정답: 2. 단일 출발점에서 다른 모든 정점으로의 최단 경로를 구한다
해설: 플로이드 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다. 단일 출발점 최단 경로는 데이크스트라 알고리즘입니다.
43 욕심쟁이 방법에 대한 설명으로 적절하지 못한 것은?
1. 각 단계에서 여러 최적해를 고려한 후 다음 단계로 넘어간다.
2. 최적화 문제 해결에 주로 사용된다.
3. 동전의 액면가가 임의로 주어지는 동전 거스름돈 문제에는 적용할 수 없다.
4. 적체적인 최적해르 구하지 못할 수도 있다.
43. 욕심쟁이 방법에 대한 설명으로 적절하지 못한 것은?
해설: 욕심쟁이 방법(Greedy Method)은 각 단계에서 최적해를 선택하며, 최적화 문제에 주로 사용됩니다. 그러나 동전의 액면가가 임의로 주어지면 최적해를 보장하지 못할 수 있으며, 전역적인 최적해를 항상 구하지 못할 수 있습니다. 하지만 각 단계에서 여러 최적해를 고려하지 않고 단일 최적 선택을 하므로 1번 설명이 틀렸습니다.
정답: 1. 각 단계에서 여러 최적해를 고려한 후 다음 단계로 넘어간다.
44. 다음 중 욕심쟁이 방법으로 해결 가능한 문제는?
1. 음의 가중치를 갖는 간선이 없는 데이크스트라 알고리즘
2. 오름차순으로 정렬하는 퀵 정렬 알고리즘
3. 추의 무게와 물체의 무게가 모두 정수인 저울 문제
4. 가중치의 합이 음수인 사이클이 존재하지 않는 플로이드 알고리즘
44. 다음 중 욕심쟁이 방법으로 해결 가능한 문제는?
해설: 욕심쟁이 방법은 각 단계에서 지역적으로 최적의 선택을 통해 전역 최적해를 구하는 문제에 적합합니다. 음의 가중치가 없는 그래프에서 데이크스트라 알고리즘은 최단 경로를 구하기 위해 욕심쟁이 방법을 사용합니다. 퀵 정렬은 분할 정복, 플로이드 알고리즘은 동적 프로그래밍, 저울 문제는 일반적으로 완전 탐색이나 동적 프로그래밍으로 해결됩니다.
정답: 1. 음의 가중치를 갖는 간선이 없는 데이크스트라 알고리즘
45. 허프만 코딩에 대한 설명으로 적잘하지 못한 것은?
1. 가변 길이 변환 코드를 사용한다.
2. 특정 텍스트에 대한 허프만 트리는 유일하다.
3. 허프만 코딩은 접두부 코드이다.
4. 허프만 트리는 전 이진트리이다.
45. 허프만 코딩에 대한 설명으로 적절하지 못한 것은?
해설: 허프만 코딩은 가변 길이 접두부 코드를 생성하며, 전 이진트리를 사용합니다. 그러나 특정 텍스트에 대한 허프만 트리는 빈도에 따라 달라질 수 있어 유일하지 않을 수 있습니다(빈도가 동일한 경우 다른 트리가 생성될 수 있음). 따라서 2번 설명이 틀렸습니다.
정답: 2. 특정 텍스트에 대한 허프만 트리는 유일하다.
'방송통신대학교 > 알고리즘' 카테고리의 다른 글
| 8강 그래프 (1) - 방통대, 알고리즘 (1) | 2025.06.07 |
|---|---|
| 7장 탐색 (2)- 방통대, 알고리즘 (0) | 2025.06.06 |
| 6장 레드 블랙 트리- 방통대, 알고리즘 (0) | 2025.06.05 |
| 2장 알고리즘 소개(2) - 방통대, 알고리즘 (1) | 2025.05.26 |
| 1장 알고리즘 소개 (1) - 방통대, 알고리즘 (0) | 2025.05.25 |
