시간복잡도
-
[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차] 자료구조론 제 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) 표기법으로 표현하시오. (단, 가능한 한..