알고리즘
-
[2019 5급 공무원 2차] 자료구조론 제 5문알고리즘 2020. 6. 24. 16:16
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 5문 제 5 문. 선택 트리(selection tree)는 완전 이진 트리(complete binary tree)를 사용하여 토너먼트 경기 방식을 통해 트리를 구축하는 자료구조로서 승자 트리(winner tree)와 패자 트리(loser tree)가 있다. 선택 트리를 사용하여 키 값이 가장 작은 원소를 선택한다고 할 때, 승자 트리에서는 형제 노드끼리 값을 비교하여 값이 작은 원소가 승자가 되어 부모 노드로 복사된 다음 토너먼트 경쟁을 계쏙하는 반면, 패자 트리에서는 키 값이 큰 패자는 부모 노드에 복사되고, 키 값이 작은 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경쟁을 계속 하는 형태로 트리를 구성한다. 따라서 승자 트리에서는..
-
[2019 5급 공무원 2차] 자료구조론 제 4문알고리즘 2020. 6. 22. 17:42
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 4문 제 4 문. 다음과 같은 순서로 데이터를 탐색 구조에 삽입할 때, 물음에 답하시오. (총 20점) 7,5,11,10,2,3,6,8,15,13 정답 ) 주어진 데이터를 삽입한 각 트리에 대한 결과이다. * 이진 탐색 트리 (Binary Search Tree) * 최소 힙 * AVL 트리 * 레드블랙 트리 (Red-Black Tree) 문제에서는 레드 링크를 이중 실선으로 표시하라 하였지만 편의상 실제 노드의 색으로 표현한 결과 트리이다. 2) n개의 원소가 삽입되어 있는 이진 탐색 트리, 최소 힙, AVL 트리, 레드블랙 트리에 새로운 원소를 삽입할 때, 최악의 경우의 시간복잡도를 빅오(Big-Oh)표기법으로 표현하시오. 정..
-
[2019 5급 공무원 2차] 자료구조론 제 3문알고리즘 2020. 6. 21. 19:16
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 3문 제 3 문. 다음은 어떤 프로젝트에서 수행해야 할 작업 간의 선행관계를 나타내는 AOV (activity on vertax) 네트워크이다. 이때 정점은 작업(activity)을 나타내며 방향 간선은 작업 간의 선행관계를 나타낸다. 물음에 답하시오. (총 20점) AOV네트워크 - Activity On Vertax- 정점 (Vertax) : 작업 간선 (Edge) : 선행 관계 정점 A, 정점 B가 있을 때 A->B 는 B라는 작업을 하기 위해서 A가 먼저 선행되야함을 뜻한다. 이러한 선행관계로 구성된 단방향 그래프 G를 AOV 네트워크라고 한다. 1) 다음의 선행관계에 대한 정의 중에서 수행 가능한 프로젝트를 표현하는 AOV 네트워크..
-
[2019 5급 공무원 2차] 자료구조론 제 2문알고리즘 2020. 6. 14. 17:32
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 2문 제 2 문. 크기가 13인 해시 테이블에서 다음과 같은 해시 함수가 주어지고 10개의 데이터를 차례대로 삽입한다고 할 때, 물음에 답하시오. ○ 해시 함수 : h(k) = k mod 13 ○ 데이터 : 38,14,10,12,3,26,8,7,5,18 1) 오버플로우(overflow) 해결을 위해 선형조사법(linear probing)을 사용하는 경우 해시 테이블을 보이시오. (4점) * 이상적인 Hash Table은 하나의 key값이 하나의 value만을 가지도록 하는게 가장 좋다. 하지만 Hash Table의 크기는 한정되어 있어서 특정 Inut 값의 해시 결과인 key값이 중복되는 경우(충돌, Overflow)가 존재하고 이를 해결..
-
[2019 5급 공무원 2차] 자료구조론 제 1문알고리즘 2020. 6. 12. 00:35
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 1문 제 1 문. 원소 개수가 n개인 집합의 멱집합(Powerset)은 격자구조(lattice)로 표현이 가능하다. 격자구조에서 각 정점은 각 부분집합이며, 두 부분집합 A,B가 A ⊂ B이고, A⊂C⊂B인 집합 C가 존재하지 않을 경우 두 정점 간에 간선이 존재한다. 예를 들어 집합 {1,2,3}에 대한 멱집합을 격자구조로 표현하면 다음과 같다. 물음에 답하시오. (총 20점) 1) 원소 개수가 n개인 집합에서 원소 개수가 k개인 모든 부분집합의 개수를 구하기 위한 int numSubsets(n,k) 함수에 대해 C언어 형식의 의사코드를 제시하고, 제시한 의사코드의 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하시오. (단, 가능한 한..
-
[56회 변리사 2차-4번] 이진트리 (Binary Tree)알고리즘 2020. 6. 3. 19:39
2019년 제 56회 변리사 2차 데이터 구조론 2교시 4번 문제 해설 이진 트리 (Binary Tree) 하나의 노드가 최대 두개의 자식 노드를 가지는 트리를 말한다. 이진 트리 개념 속 여러 용어가 있지만 중요한 몇가지 용어를 소개한다. 노드의 차수 (Degree): 노드의 서브트리 수 단말(Terminal) 노드: 리프(leaf) 노드라고하며 차수는 0 비단말 노드: 차수가 0이 아닌 노드 노드 레벨: 루트 (레벨 1) 트리의 차수: Max(노드의 차수) 트리의 높이 (Height , Depth) : Max(노드 레벨) 자식 (Child) ,형제 (Sibling) 선조 (Ancestor): 루트까지의 경로상에 있는 모든 노드 자손 (Descendants): 한 노드의 서브트리에 존재하는 모든 노드 ..
-
[56회 변리사 2차-3번] Heap Sort알고리즘 2020. 6. 2. 16:52
2019년 제 56회 변리사 2차 데이터 구조론 2교시 3번 문제 해설 Heap Sort (힙 정렬) 힙정렬을 하기 위해서는 데이터가 힙구조 상태여야한다. 따라서 힙정렬 전에 데이터를 먼저 Heapify Algorithm으로 힙구조를 만든다. (힙구조는 여러개 나올 수 있다.) 오름차순 정렬을 위해 Max Heap을 구성하여 Max Heap의 가장 끝에 해당하는 리프노드와 root를 Swap하면 가장 큰 값이 가장 끝에 위치하게 된다. 가장 끝에 가장 큰 값이 위치 했으므로 가장 끝의 위치를 N이라고 하면 N-1의 위치에 그 다음으로 가장 큰 값을 위치시키면 된다. 이후 부터 다시 Max Heap 만들고 리프와 루트의 Swap (N-1)번 작업하며 정렬하는 알고리즘이다. 참고 ↓ https://www..
-
[56회 변리사 2차-2번] 최소신장트리(MST)알고리즘 2020. 5. 28. 18:01
2019년 제 56회 변리사 2차 데이터 구조론 2교시 2번 문제 해설 MST (Minimum Spanning Tree) 그래프 G에서 모든 정점을 연결하여 갈수 있도록 하되, 최소의 간선개수와 최소의 가중치로 이루어진 트리를 말한다. (즉, 정점 개수 V , 간선 개수 V-1, 간선은 무방향) 1. 그래프 G에 관하여 다음 물음에 답하시오 => 정점(Vertax) 의 개수 8 => 따라서 MST를 만족하는 간선의 개수 (8-1) = 7 개를 선택하면 된다. => 이 그래프에서의 MST가 가지는총 가중치의 합은 10이다. => 즉, 가중치의 합이 10인 MST를 구하는 3가지 알고리즘을 해설 한다. (1) 그래프 G에 대해 프림 알고리즘 (Prim's Algorithm)으로 최소신장트리를 구하는 과정을 ..