C++로 구현하는 오일러 수(Eulerian Number): 개념부터 재귀 코드까지

오일러 수(Eulerian Number)란?

수학에서 오일러 수(Eulerian Number)는 특수한 형태의 조합 수입니다. 오일러 수는 1부터 n까지의 숫자로 만든 순열(permutation) 가운데, 인접한 두 원소를 비교했을 때 '다음 원소가 이전 원소보다 큰' 지점, 즉 오름차움(ascent)이 정확히 m번 나타나는 순열의 개수를 의미합니다.

오일러 수는 일반적으로 다음과 같이 표기합니다.

A(n, m) — 1부터 n까지의 숫자로 만든 순열 중에서 오름차움이 m개인 순열의 개수

문제 정의

이 문제에서는 두 개의 수 n과 m이 주어집니다. 우리가 구해야 할 값은 주어진 조건을 만족하는 순열의 개수, 즉 오일러 수 A(n, m)입니다.

예제로 문제 이해하기

입력: n = 4, m = 2

출력: 11

설명:

1부터 4까지의 숫자로 만들 수 있는 모든 순열은 다음과 같습니다.

1 2 3 4    1 2 4 3    1 3 2 4    1 3 4 2    1 4 2 3    1 4 3 2
2 1 3 4    2 1 4 3    2 3 1 4    2 3 4 1    2 4 1 3    2 4 3 1
3 1 2 4    3 1 4 2    3 2 1 4    3 2 4 1    3 4 1 2    3 4 2 1
4 1 2 3    4 1 3 2    4 2 1 3    4 2 3 1    4 3 1 2    4 3 2 1

총 24개의 순열 중에서 오름차움이 정확히 2개인 순열은 11개입니다. 따라서 답은 11이 됩니다.

풀이 접근 방법

오일러 수를 구할 때는 아래와 같은 재귀 공식(점화식)을 활용할 수 있습니다.

A(n, m) = 0                     (m ≥ n 또는 n = 0인 경우)
A(n, m) = 1                     (m = 0인 경우)
A(n, m) = (n − m)·A(n−1, m−1) + (m + 1)·A(n−1, m)    (그 외의 경우)

이 점화식은 문제를 더 작은 부분 문제로 나누어 해결하는 재귀 호출 방식으로 자연스럽게 구현할 수 있습니다. 재귀 깊이가 깊어질 수 있는 입력에는 메모이제이션이나 반복문 기반의 동적 프로그래밍으로 성능을 개선할 수도 있습니다.

C++ 구현 코드

다음은 위 풀이 방식을 C++로 구현한 예제입니다.

#include <iostream>
using namespace std;

int countEulerianNumber(int n, int m)
{
    if (m >= n || n == 0)
        return 0;
    if (m == 0)
        return 1;
    return (((n - m) * countEulerianNumber(n - 1, m - 1)) + ((m + 1) * countEulerianNumber(n - 1, m)));
}

int main() {
    int n = 5, m = 3;
    cout<<"The number of Eulerian permutations is "<<countEulerianNumber(n, m);
    return 0;
}

실행 결과

The number of Eulerian permutations is 26

n = 5, m = 3으로 실행하면 오일러 수가 26으로 계산되는 것을 확인할 수 있습니다. 이처럼 점화식 하나만 제대로 이해하면 복잡해 보이는 순열 계산 문제도 간결한 재귀 코드로 손쉽게 해결할 수 있습니다.