2024 국가직 9급 알고리즘 문제 정답 - 2024.3.23.

 

240323 국가 9급 알고리즘-가정답(2024-03-23 / 293.0KB / 145회)

 

240323 국가 9급 알고리즘-가정답(2024-03-23 / 741.0KB / 24회)

 

 2024년도 국가공무원 9급 공채 필기시험 알고리즘 책형 1쪽 알고리즘 1. 다음은 빅오() 표기법에 해당하는 설명이다. (가), (나)에 들어갈 관계연산자를 바르게 연결한 것은? 어떤 양의 상수 와 이 존재하여 모든  (가) 에 대하여  (나) ∙을 만족하면 은 에 속한다. (가) (나) ① ≥ ≥ ② ≤ ≤ ③ ≤ ≥ ④ ≥ ≤ 2. 안정 정렬(stable sort) 알고리즘에 해당하지 않는 것은? ① 퀵 정렬(quick sort) ② 버블 정렬(bubble sort) ③ 삽입 정렬(insertion sort) ④ 병합 정렬(merge sort) 3. 다음과 같은 총 20 kg의 분할 가능한 금속 분말을 17 kg의 무게까지 허용 가능한 배낭에 넣으려 할 때, 그리디(greedy) 알고리즘으로 얻을 수 있는 최대 이익은? 금속 분말 이름 A B C 무게 10 kg 6 kg 4 kg 이익 200원 300원 400원 ① 600원 ② 750원 ③ 840원 ④ 900원 4. 입력 크기 에 대한 수행 횟수를 점근적 표기법으로 표현했을 때 옳지 않은 것은? ①    →    ②    →    ③ loglog → log ④   log →   log 5. 다음 이진트리(binary tree)가 이진탐색트리(binary search tree)의 조건을 만족하려면 제거되어야 할 단말 노드(leaf node)의 최소 개수는? ① 1 ② 2 ③ 3 ④ 4 6. × 행렬 와 × 행렬 에 대하여 행렬 곱셈을 하고자 한다. 다음과 같은 행렬  의 각 원소를 구하는 공식을 이용하여 행렬 곱셈 결과인 행렬  를 만들 때 시간복잡도(time complexity)는? (단,  ≤ ,  ≤   이다)          ①    ②    ③    ④ log 7. 힙(heap)과 힙 정렬에 대한 설명으로 옳은 것만을 모두 고르면? (단, 힙은 이진트리이고, 은 원소의 개수를 나타낸다) ㄱ. 힙은 완전이진트리(complete binary tree) 구조를 가진다. ㄴ. 힙은 배열로 구현하기에 적합하지 않다. ㄷ. 힙에 하나의 노드를 추가하는 데 걸리는 시간은 log이다. ㄹ. 힙 정렬의 수행시간은 log이다. ① ㄱ, ㄴ ② ㄱ, ㄹ ③ ㄴ, ㄷ ④ ㄱ, ㄷ, ㄹ 2024년도 국가공무원 9급 공채 필기시험 알고리즘 책형 2쪽 8. 입력 크기가 인 정렬 알고리즘에 대한 시간복잡도가 바르게 연결 되지 않은 것은? 정렬 알고리즘 최악의 경우 평균적인 경우 최선의 경우 ① 삽입 정렬(insertion sort)        ② 선택 정렬(selection sort)       log ③ 퀵 정렬    log log ④ 병합 정렬 log log log 9. 다음은 문자들에 대한 빈도수를 나타낸다. 이 문자들에 대한 허프만 코드(Huffman code)를 생성할 경우에 가장 긴 코드를 가진 문자의 비트수는? 문자 a b c d e f 빈도수 1 9 18 48 11 12 ① 2 ② 3 ③ 4 ④ 5 10. 다음 파이썬 코드의 시간복잡도는? (단, 은 1보다 큰 정수이다) def abc(n) : if n == 1 : return 1 else : return n * abc(n - 1) ①  ② log ③  ④    11. 다음 그래프에서 생성이 가능한 신장 트리(spanning tree)의 최대 개수는? ① 4 ② 8 ③ 16 ④ 32 12. 위상 정렬(topological sort)을 적용할 때 모든 정점을 포함하는 결과가 생성될 수 없는 그래프는? ① ② ③ ④ 13. 다음 설명에 해당하는 알고리즘은? ○ 모든 쌍 최단 거리(all pairs shortest path)를 구하는 알고리즘 이다. ○ 음수의 가중치를 가진 간선(edge)이 있어도 수행될 수 있다. ○ 동적 계획법(dynamic programming)의 원리를 이용한다. ○ 시간복잡도는   이다. (단, 은 정점의 수이다) ① 프림(Prim) 알고리즘 ② 플로이드－워셜(Floyd-Warshall) 알고리즘 ③ 다익스트라(Dijkstra) 알고리즘 ④ KMP(Knuth-Morris-Pratt) 알고리즘 2024년도 국가공무원 9급 공채 필기시험 알고리즘 책형 3쪽 14. 다음 C언어로 작성된 함수의 입력값으로 13이 입력될 경우 출력되는 결과는? void foo(int n) { if(n != 0){ foo(n/2); printf("%d", n%2); } } ① 1010 ② 1011 ③ 1100 ④ 1101 15. 텍스트 문자열 01001에 대하여 패턴 문자열 001을 찾기 위해 브루트－포스(brute-force) 문자열 검색 알고리즘을 사용할 경우, 문자를 비교한 총 횟수는? (단, 패턴 문자열이 한번 검색되면 더 이상 검색하지 않는다) ① 1 ② 3 ③ 5 ④ 6 16. 다음 중 그리디 알고리즘에 해당하는 것만을 모두 고르면? ㄱ. 라빈－카프(Rabin-Karp) 알고리즘 ㄴ. 병합 정렬 알고리즘 ㄷ. 다익스트라 알고리즘 ㄹ. 플로이드－워셜 알고리즘 ① ㄷ ② ㄱ, ㄴ ③ ㄱ, ㄷ ④ ㄱ, ㄷ, ㄹ 17. 퀵 정렬 시 시간복잡도가 최악의 경우가 되는 것으로 가장 적절한 것은? ① 피벗(pivot)을 최대값으로 정한다. ② 피벗을 랜덤(random)하게 정한다. ③ 피벗을 중간값(median)으로 정한다. ④ 피벗을 파티션(partition)의 중간에 위치한 값으로 정한다. 18. 분할 정복(divide-conquer) 문제 해결 기법을 이용하여 토너먼트 방식으로 64개의 축구팀 중 1등을 결정하기 위해 치르게 되는 최소의 경기 횟수는? (단, 모든 경기는 팀별 1 : 1 방식으로 진행되며 무승부 및 기권은 없다) ① 61 ② 62 ③ 63 ④ 64 19. 다음 설명의 (가)에 들어갈 용어로 옳은 것은? (단, P ≠ NP이다) 어떤 문제 A가 다음을 모두 만족하면 (가) 이다. ○ 문제 A는 NP에 속한다. ○ 모든 NP 문제들은 다항식 시간에 문제 A로 변환할 수 있다. ① P 문제 ② NP 문제 ③ NP－하드(NP-hard) 문제 ④ NP－완전(NP-complete) 문제 20. 다음 의사코드(pseudo-code)로 표현된 알고리즘의 수행시간을  으로 나타낼 때, 의 계산식과 의 점근적 복잡도로 옳은 것은? (단, 은 1보다 큰 정수이고 는 양의 상수이다) algo(n) { if (n ≤ 1) return 0; return 1 + algo(n / 2); } ①      ,  ②      , log ③     ,  ④     , log