이 문제에서는 하나의 정수 N이 주어지며, n번째 에르미트 수(Hermite Number)를 구하는 프로그램을 작성하는 것이 목표입니다.
에르미트 수란?
에르미트 수는 변수가 없는 상태(인수가 0개)에서의 에르미트 다항식 값을 의미합니다. n번째 에르미트 수는 다음과 같은 재귀 관계식으로 정의됩니다.
HN = (-2) × (N − 1) × H(N−2)
초기값은 H₀ = 1, H₁ = 0입니다.
이 정의에 따른 에르미트 수열은 다음과 같습니다.
1, 0, −2, 0, 12, 0, −120, 0, 1680, 0 …
홀수 번째 항은 모두 0이고, 짝수 번째 항에만 실제 값이 존재한다는 특징을 확인할 수 있습니다.
문제 이해를 위한 예시
입력
N = 7
출력
0
입력
N = 6
출력
-120
방법 1: 재귀를 이용한 해결
가장 간단한 방법은 위에서 소개한 재귀 공식을 그대로 코드로 옮기는 것입니다. 함수가 자기 자신을 호출하는 방식으로 N번째 항을 구할 수 있습니다.
구현 예제
#include <iostream>
using namespace std;
int calcNHermiteNumber(int N) {
if (N == 0)
return 1;
if (N % 2 == 1)
return 0;
else
return -2 * (N - 1) * calcNHermiteNumber(N - 2);
}
int main() {
int N = 10;
cout<<"The "<<N<<"th hermite Number is "<<calcNHermiteNumber(N);
return 0;
}
출력
The 10th hermite Number is -30240
방법 2: 일반 공식을 이용한 효율적인 해결
재귀 호출은 입력이 커질수록 비효율적일 수 있습니다. 재귀 관계식을 전개하면 다음과 같은 일반 공식을 유도할 수 있습니다.
- N이 홀수인 경우: 에르미트 수는 항상 0입니다.
- N이 짝수인 경우: 아래 공식으로 계산됩니다.
HN = ((-1)N/2) × (2N/2) × (N−1)!!
여기서 (N−1)!!는 이중 계승(semi-factorial)으로, (N−1) × (N−3) × … × 3 × 1처럼 홀수들만 곱한 값입니다.
구현 예제
#include <iostream>
#include <math.h>
using namespace std;
int calcSemiFact(int n) {
int factVal = 1;
for (int i = 1; i <= n; i = i + 2) {
factVal *= i;
}
return factVal;
}
int calcNHermiteNumber(int n) {
if (n % 2 == 1)
return 0;
int HermiteNumber = (pow(2, n / 2)) * calcSemiFact(n - 1);
if ((n / 2) % 2 == 1)
HermiteNumber *= -1;
return HermiteNumber;
}
int main() {
int N = 10;
cout<<"The "<<N<<"th hermite Number is "<<calcNHermiteNumber(N);
return 0;
}
출력
The 10th hermite Number is -30240
마무리
에르미트 수는 홀수 위치에서 항상 0이라는 단순한 규칙을 가지고 있어, 이를 활용하면 불필요한 연산을 크게 줄일 수 있습니다. 작은 입력에는 재귀 방식도 충분하지만, 더 큰 N을 다룰 때는 반복문 기반의 일반 공식을 사용하는 것이 시간 복잡도와 스택 오버플로우 측면에서 훨씬 유리합니다.