C++로 이해하는 엔트린저 수(Entringer Number)와 구현 방법

엔트린저 수(Entringer Number)는 {1, 2, 3, …, n+1} 집합의 순열 중에서 K+1로 시작하며, 값이 감소와 증가를 번갈아 가며 갱신되는 순열의 개수를 나타내는 특수한 수입니다.

엔트린저 수는 다음과 같은 점화식으로 정의됩니다.

점화식

E(n, k) = E(n, k-1) + E(n-1, n-k)

기저 값(base case)은 다음과 같습니다.

E(0, 0) = 1
E(n, 0) = 0

위 점화식과 기저 조건을 활용하면 원하는 위치의 엔트린저 수를 계산할 수 있습니다.

계산 예시

N = 5, k = 3인 경우,

E(5, 3) = 14

풀이 과정을 보여주는 프로그램

아래는 재귀 함수를 사용해 엔트린저 수를 계산하는 C++ 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

int EntringerNumber(int n, int k)
{
    if (n == 0 && k == 0)
        return 1;
    if (k == 0)
        return 0;
    return EntringerNumber(n, k - 1) + EntringerNumber(n - 1, n - k);
}

int main() {
    int n = 5, k = 3;
    cout << "E(" << n << ", " << k << ")의 값 = " << EntringerNumber(n, k);
    return 0;
}

출력 결과

E(5, 3)의 값 = 14

성능 개선 팁

위 재귀 방식은 중복 계산이 많아 지수 시간 복잡도를 가질 수 있습니다. 실전에서는 메모이제이션(memoization) 또는 2차원 배열을 이용한 동적 계획법(DP)으로 점화식을 구현하면 O(n×k) 시간에 효율적으로 계산할 수 있습니다.