이 글에서는 바움-스위트 수열(Baum–Sweet Sequence)의 개념과 이를 C++로 구현하는 방법을 살펴봅니다. 바움-스위트 수열은 0과 1로만 이루어진 이진 수열로, 자연수 n을 이진수로 나타냈을 때 연속된 0이 홀수 개 포함되어 있으면 n번째 항은 0, 그렇지 않으면 1이 됩니다.
바움-스위트 수열의 정의
자연수 n이 주어졌을 때, 바움-스위트 수열의 n번째 항을 구하는 것이 목표입니다. 이를 위해서는 n의 이진 표현에서 길이가 홀수인 연속된 0 블록이 존재하는지 확인해야 합니다.
예를 들어 n = 4라고 가정해 보겠습니다. 4를 이진수로 표현하면 100이며, 연속된 0이 두 개(짝수) 있으므로 해당 항의 값은 1이 됩니다.
참고로 바움-스위트 수열의 초반 항은 다음과 같습니다.
b(0) ~ b(9): 1, 1, 0, 1, 1, 0, 0, 1, 1, 0
알고리즘
바움-스위트 수열의 n번째 항을 구하는 절차는 다음과 같습니다.
- n을 이진수로 변환하여 비트 배열 seq에 저장합니다.
- 결괏값 baum을 1로 초기화합니다.
- 비트열의 유효 길이 len을 계산합니다.
- i = 0부터 len까지 순회하면서 다음을 반복합니다.
- seq[i]가 0이면, 그 뒤에 연속된 0의 개수 count를 셉니다.
- count가 홀수이면 baum을 0으로 갱신합니다.
- 모든 비트를 확인한 후 baum 값을 반환합니다.
C++ 구현 예제
아래 코드는 C++의 bitset과 __builtin_clz() 함수를 활용하여 바움-스위트 수열의 n번째 항을 계산합니다.
#include <bits/stdc++.h>
using namespace std;
int BaumSweetSeqTerm(int n) {
bitset<32> sequence(n); // n의 비트 표현 저장
int len = 32 - __builtin_clz(n);
// __builtin_clz()는 최상위 1 앞에 있는 0의 개수를 반환
int baum = 1; // 바움 수열의 n번째 항
for (int i = 0; i < len;) {
int j = i + 1;
if (sequence[i] == 0) {
int count = 1;
for (j = i + 1; j < len; j++) {
if (sequence[j] == 0) // 연속된 0의 개수 카운트
count++;
else
break;
}
if (count % 2 == 1) // 홀수/짝수 판별
baum = 0;
}
i = j;
}
return baum;
}
int main() {
int n = 4;
cout << BaumSweetSeqTerm(n);
}
코드 설명
bitset<32>는 정수 n을 32비트 이진 형태로 저장합니다.__builtin_clz(n)은 최상위 비트(MSB) 쪽의 선행 0 개수를 반환하므로, 이를 이용해 실제 비트 길이 len을 구할 수 있습니다.- 연속된 0 블록을 발견하면 내부 반복문으로 개수를 세고, 블록 전체를 한 번에 건너뛰어(
i = j) 불필요한 중복 검사를 피합니다. - 길이가 홀수인 0 블록이 하나라도 존재하면 baum이 0으로 설정됩니다.
실행 결과
1
n = 4의 이진 표현은 100이고, 연속된 0의 개수가 2개(짝수)이므로 결과로 1이 출력됩니다.
시간 복잡도
이 알고리즘은 비트열을 선형으로 한 번 순회하므로 시간 복잡도는 O(log n)입니다. n의 비트 길이에 비례하기 때문에 매우 효율적입니다.
마무리
바움-스위트 수열은 이진수의 성질을 활용한 흥미로운 수열로, 비트 조작(bit manipulation) 기법을 연습하기에 좋은 예제입니다. bitset과 내장 함수를 적절히 활용하면 간결하고 효율적인 코드를 작성할 수 있습니다.