C++로 집합의 반사 관계 개수 구하기

이 글에서는 집합 위에서 정의할 수 있는 반사 관계(reflexive relation)의 개수를 구하는 방법을 설명합니다. 이 문제에서는 자연수 n이 주어지며, n개의 원소를 가진 집합에 대해 반사 관계가 총 몇 개 존재하는지 구해야 합니다.

반사 관계란?

집합 A 위의 관계 R에서 모든 원소 a ∈ A에 대해 (a, a) ∈ R을 만족할 때, 이 관계를 반사 관계라고 합니다. 즉, 집합의 모든 원소가 자기 자신과 반드시 관계를 가져야 한다는 뜻입니다. 예를 들어 보겠습니다.

입력 : x = 1
출력 : 1
설명 : 집합 = { 1 }, A × A 위의 반사 관계 :
{ ( 1, 1 ) }

입력 : x = 2
출력 : 4
설명 : 집합 = { 1, 2 }, A × A 위의 반사 관계 :
    { ( 1, 1 ), ( 2, 2 ) }
    { ( 1, 1 ), ( 2, 2 ), ( 1, 2 ) }
    { ( 1, 1 ), ( 2, 2 ), ( 1, 2 ), ( 2, 1 ) }
    { ( 1, 1 ), ( 2, 2 ), ( 2, 1 ) }

따라서 관계 R이 다음 조건을 만족하면 반사 관계입니다. (a, a) ∈ R ∀ a ∈ A

해결 접근 방법

n개의 원소를 가진 집합 위의 반사 관계 개수는 공식 2^n²−n으로 구할 수 있습니다. 그 이유는 다음과 같습니다. n × n개의 순서쌍 중 대각선 성분 (a, a)는 반사성 때문에 반드시 포함되어야 하고(n개), 나머지 n² − n개의 비대각 성분은 각각 포함하거나 포함하지 않는 두 가지 선택이 가능합니다. 따라서 전체 경우의 수는 2^n²−n이 됩니다.

예제 코드

#include <iostream>
using namespace std;
int countReflexive(int n){
    int ans = 1 << (n*n - n);
    return ans;
}
int main(){
    int n;
    cin >> n; // std::cin으로 사용자에게서 n 입력받기
    int result = countReflexive(n); // 반사 관계의 개수를 계산하는 함수 호출
    cout << "집합 위의 반사 관계 개수: " << result; // 결과 출력
    return 0;
}

실행 결과

집합 위의 반사 관계 개수: 1

프로그램 설명

이 프로그램은 사용자로부터 n을 입력받아 공식 2^n²−n에 대입하기만 하면 되므로 이해하기 매우 간단합니다. 공식 계산에는 왼쪽 시프트 연산자(<<)를 사용했는데, 1 << k가 곧 2^k와 같기 때문에 거듭제곱을 효율적으로 계산할 수 있습니다. 이 코드의 시간 복잡도는 O(1)로 상수 시간 안에 실행됩니다. 다만 n이 커지면 지수 값이 int 타입의 표현 범위를 초과해 오버플로가 발생할 수 있으므로, 큰 입력에는 long long 같은 더 넓은 범위의 자료형을 사용하는 것이 좋습니다.

결론

이 글에서는 집합 위의 반사 관계 개수를 구하는 문제를 다루었습니다. 수학자들이 유도한 공식 2^n²−n을 활용하는 간단한 접근 방식을 살펴보았고, 이를 C++ 코드로 구현하여 O(1)의 시간 복잡도로 해답을 얻었습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다.