C++로 스턴의 이원 수열(Stern's Diatomic Series)의 n번째 항 구하기

이 글에서는 스턴의 이원 수열(Stern's Diatomic Series)에서 n번째 항을 구하는 방법을 알아봅니다. 이 수열은 다음과 같이 진행됩니다.

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ...

이 수열은 퓨스크(fusc) 함수라고도 불리며, 각 항은 다음과 같은 점화식으로 정의할 수 있습니다.

점화식 정의

• n이 짝수일 때: p(n) = p(n / 2)
• n이 홀수일 때: p(n) = p((n − 1) / 2) + p((n + 1) / 2)
• 기저 사례: p(0) = 0, p(1) = 1

동적 계획법(Dynamic Programming) 활용하기

단순히 재귀 함수로 구현하면 같은 값이 여러 번 중복 계산되어 비효율적입니다. 따라서 동적 계획법을 사용하면 계산량을 크게 줄일 수 있습니다.

구현 방법은 다음과 같습니다.

1. 먼저 기저 사례인 p(0)과 p(1)을 테이블에 저장합니다.
2. 인덱스 i = 2부터 n까지 반복하면서 위의 점화식에 따라 p(i)를 순차적으로 계산하고 저장합니다.
3. 최종적으로 table[n]을 반환하면 원하는 n번째 항을 얻을 수 있습니다.

이 방식의 시간 복잡도와 공간 복잡도는 모두 O(n)으로, 재귀 방식보다 훨씬 효율적입니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int findTerm(int n) {
    int table[n+1];
    table[0] = 0;
    table[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0)
            table[i] = table[i / 2];
        else
            table[i] = table[(i - 1) / 2] + table[(i + 1) / 2];
    }
    return table[n];
}
int main() {
    cout << 3 << " rd term is: " << findTerm(3) << endl;
    cout << 15 << " th term is: " << findTerm(15) << endl;
    cout << 20 << " th term is: " << findTerm(20) << endl;
}

실행 결과

3 rd term is: 2
15 th term is: 4
20 th term is: 3

결과 분석

실행 결과를 보면 3번째 항은 2, 15번째 항은 4, 20번째 항은 3으로 계산되었습니다. 이는 앞서 살펴본 수열 0, 1, 1, 2, 1, 3, 2, 3, ..., 4, ... 의 해당 위치 값들과 정확히 일치합니다.

이처럼 동적 계획법을 활용하면 스턴의 이원 수열의 임의의 n번째 항을 선형 시간 안에 효율적으로 구할 수 있습니다.