[2019 5급 공무원 2차] 자료구조론 제 1문

 

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) 표기법으로 표현하시오. (단, 가능한 한 효율적인 구현을 제시한다) (10점)

 

해설 )

C언어로 구현한 Code

 

 

 
#include <stdio.h>
 
int numSubset(int n, int k){
    if(k==0){
        return 1;
    }
    int sum = 0;
    for(int i=n;i>=1;i--) sum+=numSubset(i-1,k-1);
    
    return sum;
}
int main()
{
    int result = numSubset(5,3);
    printf("%d",result);
    return 0;
}
 

 

 

n개의 원소를 가진 집합의 부분집합 개수는 다음과 같다.

 

 

 

 

 

따라서 위에 작성된 코드는 재귀호출로 인한 최악의 시간복잡도는 다음으로 정의된다.

 

 

하지만 n개의 집합중 k개의 부분집합의 개수를 구하는 것을 효율적으로 구하기 위해 확률 통계의 조합 개념을 적용하면 다음과 같이 일반화 될 수 있다.

 

 

부분집합을 구하기 위한 개수로의 연산을 getnCr(n,k)라는 Fuction을 통해 다음과 같이 만든다.

​

 

 

 
#include <stdio.h>
int getnCr(int n, int k) {
        int result=1;
        for(int i=n;i>=(n-k+1);i--) result*=i;
        for(int i=k;i>=1;i--) result/=i;
        return result;
    }
int numSubset(int n, int k){
    if(k==0){
        return 1;
    }
    int sum = 0;
    for(int i=n;i>=1;i--) sum+=numSubset(i-1,k-1);
    
    return sum;
}
int main()
{
    int result = numSubset(5,3);
    printf("%d",result);
    
    
    result = getnCr(5,3);
    return 0;
}
 

도출된 일반식에 의해 getnCr(n,k)의 시간복잡도는 최종적으로 다음과 같다.

 

2) 원소 개수가 n개인 집합의 멱집합을 표현하는 격자구조가 있다고 하자. 이때 해당 격자구조에 존재하는 모든 간선의 개수를 구하는 int numEdges(n) 함수에 대해 C언어 형식의 의사코드를 제시하고, 제시한 의사코드의 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하시오. (단, 가능한 한 효율적인 구현을 제시한다.) (10점)

 

 

해설 )

​

Hasse Diagram of PowerSet

 

출처 : https://demonstrations.wolfram.com/HasseDiagramOfPowerSets/

Hasse Diagram of Power Sets - Wolfram Demonstrations Project

 

위 문제와 같이 효율적으로 격자구조에 존재하는 모든 간선의 개수를 구하는 일반식에 대한 도출은 다음과 같다.

 

출처 : https://math.stackexchange.com/questions/1391673/number-of-edges-in-the-hasse-diagram-for-the-subseteq-relation-on-the-set-m

Number of edges in the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,...,n\}$

 

C코드로 구현한 코드

 

 
#include <stdio.h>
int numEdges(int n) {
        int result = 1;
        for(int i=1;i<=(n-1);i++) result*=2;
        result*=n;
        return result;
}
int main()
{
    int result = numEdges(3);
    printf("%d",result);
    return 0;
}